DIMACS TR: 97-31

Note on the Erdos-Szekeres theorem

Authors: Geza Toth and Pavel Valtr


Let $g(n)$ denote the least integer such that among any $g(n)$ points in general position in the plane there are always $n$ in convex position. In 1935 P. Erd\H os and G. Szekeres showed that $g(n)$ exists and $2^{n-2}+1\le g(n)\le {2n-4\choose n-2}+1$. Recently, the upper bound has been slightly improved by Chung and Graham and by Kleitman and Pachter. In this note we further improve the upper bound to $$g(n)\le {2n-5\choose n-2}+2.$$

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-31.ps.gz
DIMACS Home Page