DIMACS TR: 97-31
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
DIMACS Home Page