×

zbMATH — the first resource for mathematics

The Erdős-Szekeres problem. (English) Zbl 1356.52008
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].

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)
PDF BibTeX XML Cite
Full Text: DOI