## 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