On the Erdos-Szekeres convex polygon problem

Abstract

Let $ES(n)$ be the smallest integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. In their seminal 1935 paper, Erdos and Szekeres showed that $ES(n)\le \left(\genfrac{}{}{0ex}{}{2n-4}{n-2}\right)+1=4^{n-o(n)}$. In 1960, they showed that $ES(n)\ge 2^{n-2}+1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdos-Szekeres conjecture by showing that $ES(n)=2^{n+o(n)}$.