## Note on the Erdos-Szekeres theorem

### Authors: Geza Toth and Pavel Valtr

ABSTRACT

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