Problem 107

Erdős Problem #107 [status: falsifiable; formalized: yes]. Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$. Current best: Erd\H{o}s and Szekeres proved the bounds$$2^{n-2}+1\leq f(n)\leq \binom{2n-4}{n-2}+1.$$([ErSz60] and [ErSz35] respectively). There were several improvements of the upper bound, but all of the form $4^{(1+o(1))n}$, until Suk [Su17] proved$$f(n) \leq 2^{(1+o(1))n}.$$The current best bound is due to Holmsen, Mojarrad, Pach, and Tardos [HMPT20], who prove$$f(n) \leq 2^{n+O(\sqrt{n\log n})}.$$In [Er97e] Erd\H{o}s clarifies that the \500 is for a proof, and only offers \100 for a disproof. Prize: $500. OEIS: A000051. Tags: convex, geometry.