On a conjecture of Erdős and Szekeres

Abstract

Let f(n) denote the smallest positive integer such that every set of $f(n)$ points in general position in the Euclidean plane contains a convex n-gon. In a seminal paper published in 1935, Erdős and Szekeres proved that f(n) exists and provided an upper bound. In 1961, they also proved a lower bound, which they conjectured is optimal. Their bounds are: $2^{n-2}+1\le f(n)\le \left(\genfrac{}{}{0ex}{}{2n-4}{n-2}\right)+1$. Since then, the upper bound has been improved by rougly a factor of 2, to $f(n)\le \left(\genfrac{}{}{0ex}{}{2n-5}{n-2}\right)+1$. In the current paper, we further improve the upper bound by proving that: $$\underset{n\to \infty }{\mathrm{limsup}}\frac{f(n)}{\left(\genfrac{}{}{0ex}{}{2n-5}{n-2}\right)}\le \frac{29}{32}$$

8 pages