The Erdős-Szekeres problem. (English) Zbl 1356.52008

Morris, Walter; Soltan, Valeriu

Nash, John Forbes jun. (ed.) et al., Open problems in mathematics. Cham: Springer (ISBN 978-3-319-32160-8/hbk; 978-3-319-32162-2/ebook). 351-375 (2016).

In 1932, Esther Klein conjectured that for every \(n\), there is an \(N(n)\), such that among \(N(n)\) points in the plane, if no 3 of them are collinear, one finds \(n\) vertices of a convex \(n\)-gon. P. Erdős and G. Szekeres [Compos. Math. 2, 463–470 (1935; Zbl 0012.27010); Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 3–4, 53–62 (1961; Zbl 0103.15502)] proved \(2^{n-2} +1 \leq N(n) \leq {2n-4\choose n-2}+1\) and conjectured that the lower bound is tight for all \(n\geq 3\). By now this conjecture has been proved up to \(n=6\). A. Suk [“On the Erdős-Szekeres convex polygon problem”, Preprint, arXiv:1604.08657] recently proved for \(N(n)\) the conjectured logarithmic asymptotics. The survey under review discusses the history of the problem, and variants of the problem to find an empty convex \(n\)-gon or to find higher dimensional extensions.
For the entire collection see [Zbl 1351.00027].

Reviewer: László A. Székely (Columbia)

MSC:

52C10	Erdős problems and related topics of discrete geometry
52A10	Convex sets in \(2\) dimensions (including convex curves)
52A20	Convex sets in \(n\) dimensions (including convex hypersurfaces)

Keywords:

Erdős-Szekeres problem; convex polygons; Ramsey theory; empty convex polygons; convex polytopes; empty convex polytopes