An improved upper bound for the Erdős-Szekeres conjecture

Abstract

Let $ES(n)$ denote the minimum natural number such that every set of $ES(n)$ points in general position in the plane contains $n$ points in convex position. In 1935, Erdős and Szekeres proved that $ES(n)\le \left(\genfrac{}{}{0ex}{}{2n-4}{n-2}\right)+1$. In 1961, they obtained the lower bound $2^{n-2}+1\le ES(n)$, which they conjectured to be optimal. In this paper, we prove that $$ES(n)\le \left(\genfrac{}{}{0ex}{}{2n-5}{n-2}\right)-\left(\genfrac{}{}{0ex}{}{2n-8}{n-3}\right)+2\approx \frac{7}{16}\left(\genfrac{}{}{0ex}{}{2n-4}{n-2}\right).$$

15 pages, 10 figures. Accepted to Discrete & Computational Geometry (DCG). This second version is a result of the merger of the first version (arXiv:1510.06255v1) and the paper (arXiv:1505.07549)