Forced Convex n -Gons in the Plane

In a seminal paper from 1935, Erdős and Szekeres showed that for each n there exists a least value g(n) such that any subset of g(n) points in the plane in general position must always contain the vertices of a convex n -gon. In particular, they obtained the bounds \(2^{n-2} + 1 \le g(n) \le {{2n-4}\choose{n-2}} +1,\) which have stood unchanged since then. In this paper we remove the +1 from the upper bound for n ≥ 4 . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p367.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader>

Authors and Affiliations

1. University of Pennsylvania, Philadelphia, PA 19104, USA chung@math.upenn.edu , , , , , , US

   F. R. K. Chung

2. AT &T Labs—Research, Murray Hill, NJ 07974, USA, , , , , , US

   R. L. Graham

Received January 1, 1997, and in revised form June 6, 1997.

Reprints and permissions