×

zbMATH — the first resource for mathematics

On the Erdős-Szekeres convex polygon problem. (English) Zbl 1370.52032
P. Erdős and G. Szekeres [Compos. Math. 2, 463–470 (1935; Zbl 0012.27010)] showed that for every positive integer \(n\) there is a least positive integer \(\mathrm{ES}(n)\) such that among any \(ES(n)\) points in the plane, such that no 3 are collinear, some \(n\) points are the vertices of a convex \(n\)-gon. They gave two proofs, one of them was Ramsey theoretic, while the other was a geometric argument, using cups and caps, providing \(\mathrm{ES}(n)\leq \binom{2n-4}{n-2}\). Later they returned to this problem: P. Erdős and G. Szekeres [Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 3–4, 53–62 (1961; Zbl 0103.15502)] showed \(\mathrm{ES}(n)\geq 2^{n-2}+1\) and made a conjecture that \(\mathrm{ES}(n)= 2^{n-2}+1\). A number of improvements have been made on the upper bound, but they at most gained a constant multiplicative factor.
The paper under review shows \(\mathrm{ES}(n)=2^{n+o(n)}\), a breakthrough result, providing the logarithmic asymptotics for \(\mathrm{ES}(n)\). The result hinges on some results of A. Pór and P. Valtr [Discrete Comput. Geom. 28, No. 4, 625–637 (2002; Zbl 1019.52011)] regarding cups and caps. The error term in the exponent was originally \(6n^{2/3}\log n\), which was reduced by Gábor Tardos to \(O\sqrt{n\log n})\).

MSC:
52C10 Erdős problems and related topics of discrete geometry
05D10 Ramsey theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] B\'ar\'any, I.; Valtr, P., A positive fraction Erd\H os-Szekeres theorem, Discrete Comput. Geom., 19, 3, Special Issue, 335\textendash 342 pp., (1998) · Zbl 0914.52007
[2] Brass, Peter; Moser, William; Pach, J\'anos, Research problems in discrete geometry, xii+499 pp., (2005), Springer, New York · Zbl 1086.52001
[3] Chung, F. R. K.; Graham, R. L., Forced convex \(n\)-gons in the plane, Discrete Comput. Geom., 19, 3, Special Issue, 367\textendash 371 pp., (1998) · Zbl 0908.52004
[4] Dilworth, R. P., A decomposition theorem for partially ordered sets, Ann. of Math. (2), 51, 161\textendash 166 pp., (1950) · Zbl 0038.02003
[5] Dobbins, Michael Gene; Holmsen, Andreas; Hubard, Alfredo, The Erd\H os-Szekeres problem for non-crossing convex sets, Mathematika, 60, 2, 463\textendash 484 pp., (2014) · Zbl 1298.52019
[6] Erd\H os, Paul, Some of my favorite problems and results. The mathematics of Paul Erd\H os, I, Algorithms Combin. 13, 47\textendash 67 pp., (1997), Springer, Berlin
[7] Erd\"os, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463\textendash 470 pp., (1935) · Zbl 0012.27010
[8] Erd\H os, P.; Szekeres, G., On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. E\`‘otv\'’os Sect. Math., 3-4, 53\textendash 62 pp., (1960/1961) · Zbl 0103.15502
[9] Fox, Jacob; Pach, J\'anos; Sudakov, Benny; Suk, Andrew, Erd\H os-Szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. (3), 105, 5, 953\textendash 982 pp., (2012) · Zbl 1254.05114
[10] Hubard, Alfredo; Montejano, Luis; Mora, Emiliano; Suk, Andrew, Order types of convex bodies, Order, 28, 1, 121\textendash 130 pp., (2011) · Zbl 1235.52004
[11] K\'arolyi, Gyula, Ramsey-remainder for convex sets and the Erd\H os-Szekeres theorem, Discrete Appl. Math., 109, 1-2, 163\textendash 175 pp., (2001) · Zbl 0974.52014
[12] K\'arolyi, Gyula; Valtr, Pavel, Point configurations in \(d\)-space without large subsets in convex position, Discrete Comput. Geom., 30, 2, 277\textendash 286 pp., (2003) · Zbl 1051.52012
[13] Kleitman, D.; Pachter, L., Finding convex sets among points in the plane, Discrete Comput. Geom., 19, 3, Special Issue, 405\textendash 410 pp., (1998) · Zbl 0908.52005
[14] Matou\v sek, Ji\v r\'\i , Lectures on discrete geometry, Graduate Texts in Mathematics 212, xvi+481 pp., (2002), Springer-Verlag, New York · Zbl 0999.52006
[15] Morris, W.; Soltan, V., The Erd\H os-Szekeres problem on points in convex position\textemdash a survey, Bull. Amer. Math. Soc. (N.S.), 37, 4, 437\textendash 458 (electronic) pp., (2000) · Zbl 0958.52018
[16] Moshkovitz, Guy; Shapira, Asaf, Ramsey theory, integer partitions and a new proof of the Erd\H os-Szekeres theorem, Adv. Math., 262, 1107\textendash 1129 pp., (2014) · Zbl 1295.05255
[17] Mojarrad, Hossein Nassajian; Vlachos, Georgios, An Improved Upper Bound for the Erd\H os-Szekeres Conjecture, Discrete Comput. Geom., 56, 1, 165\textendash 180 pp., (2016) · Zbl 1351.52017
[18] Norin, Sergey; Yuditsky, Yelena, Erd\H os-Szekeres Without Induction, Discrete Comput. Geom., 55, 4, 963\textendash 971 pp., (2016) · Zbl 1351.52018
[19] Pach, J.; Solymosi, J., Canonical theorems for convex sets, Discrete Comput. Geom., 19, 3, Special Issue, 427\textendash 435 pp., (1998) · Zbl 0905.52001
[20] P\'or, Attila; Valtr, Pavel, The partitioned version of the Erd\H os-Szekeres theorem, Discrete Comput. Geom., 28, 4, 625637 pp., (2002) · Zbl 1019.52011
[21] Suk, Andrew, A note on order-type homogeneous point sets, Mathematika, 60, 1, 37\textendash 42 pp., (2014) · Zbl 1301.05353
[22] T\'oth, G\'eza; Valtr, Pavel, The Erd\H os-Szekeres theorem: upper bounds and related results. Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ. 52, 557\textendash 568 pp., (2005), Cambridge Univ. Press, Cambridge · Zbl 1090.52014
[23] T\'oth, G.; Valtr, P., Note on the Erd\H os-Szekeres theorem, Discrete Comput. Geom., 19, 3, Special Issue, 457\textendash 459 pp., (1998) · Zbl 0903.52006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.