Erdős-Szekeres without induction (Q309659): Difference between revisions

Let \(\mathrm{ES}(n)\) denote the least natural number, such that every set of \(\mathrm{ES}(n)\) points in general position in the plane contains \(n\) points in convex position. \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463--470 (1935; Zbl 0012.27010); Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 3--4, 53--62 (1961; Zbl 0103.15502)] proved \(2^{n-2} +1 \leq\mathrm{ES}(n)\leq {2n-4\choose n-2}+1\) and conjectured that the lower bound is tight. The paper under review proves \(\limsup_{n\rightarrow \infty} \frac{\mathrm{ES}(n)}{{2n-4 \choose n-2}} \leq 7/16\), the current best asymptotic upper bound. Unlike earlier upper bounds to the Erdős-Szekeres problem, the proof does not use induction. \textit{H. N. Mojarrad} and \textit{G. Vlachos} [Discrete Comput. Geom. 56, No. 1, 165--180 (2016; Zbl 1351.52017)] reached the same asymptotic upper bound, with a slightly stronger bound.