On the Erdős-Szekeres convex polygon problem

Suk, Andrew

doi:10.1090/jams/869

On the Erdős-Szekeres convex polygon problem
HTML articles powered by AMS MathViewer

by Andrew Suk;

J. Amer. Math. Soc. 30 (2017), 1047-1053

DOI: https://doi.org/10.1090/jams/869

Published electronically: September 30, 2016

PDF | Request permission

Abstract:

Let $ES(n)$ be the smallest integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that $ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that $ES(n) =2^{n +o(n)}$.

References

I. Bárány and P. Valtr, A positive fraction Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 335–342. Dedicated to the memory of Paul Erdős. MR 1608874, DOI 10.1007/PL00009350
Peter Brass, William Moser, and János Pach, Research problems in discrete geometry, Springer, New York, 2005. MR 2163782
F. R. K. Chung and R. L. Graham, Forced convex $n$-gons in the plane, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 367–371. Dedicated to the memory of Paul Erdős. MR 1608877, DOI 10.1007/PL00009353
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 32578, DOI 10.2307/1969503
Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard, The Erdős-Szekeres problem for non-crossing convex sets, Mathematika 60 (2014), no. 2, 463–484. MR 3229499, DOI 10.1112/S0025579314000072
Paul Erdős, Some of my favorite problems and results, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 47–67. MR 1425174, DOI 10.1007/978-3-642-60408-9_{3}
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
P. Erdős and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3(4) (1960/61), 53–62. MR 133735
Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk, Erdős-Szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. (3) 105 (2012), no. 5, 953–982. MR 2997043, DOI 10.1112/plms/pds018
Alfredo Hubard, Luis Montejano, Emiliano Mora, and Andrew Suk, Order types of convex bodies, Order 28 (2011), no. 1, 121–130. MR 2774044, DOI 10.1007/s11083-010-9156-2
Gyula Károlyi, Ramsey-remainder for convex sets and the Erdős-Szekeres theorem, Discrete Appl. Math. 109 (2001), no. 1-2, 163–175. 14th European Workshop on Computational Geometry CG’98 (Barcelona). MR 1804741, DOI 10.1016/S0166-218X(00)00234-1
Gyula Károlyi and Pavel Valtr, Point configurations in $d$-space without large subsets in convex position, Discrete Comput. Geom. 30 (2003), no. 2, 277–286. U.S.-Hungarian Workshops on Discrete Geometry and Convexity (Budapest, 1999/Auburn, AL, 2000). MR 2007965, DOI 10.1007/s00454-003-0009-4
D. Kleitman and L. Pachter, Finding convex sets among points in the plane, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 405–410. Dedicated to the memory of Paul Erdős. MR 1608882, DOI 10.1007/PL00009358
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
W. Morris and V. Soltan, The Erdős-Szekeres problem on points in convex position—a survey, Bull. Amer. Math. Soc. (N.S.) 37 (2000), no. 4, 437–458. MR 1779413, DOI 10.1090/S0273-0979-00-00877-6
Guy Moshkovitz and Asaf Shapira, Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem, Adv. Math. 262 (2014), 1107–1129. MR 3228450, DOI 10.1016/j.aim.2014.06.008
Hossein Nassajian Mojarrad and Georgios Vlachos, An improved upper bound for the Erdős-Szekeres conjecture, Discrete Comput. Geom. 56 (2016), no. 1, 165–180. MR 3509035, DOI 10.1007/s00454-016-9791-5
Sergey Norin and Yelena Yuditsky, Erdős-Szekeres without induction, Discrete Comput. Geom. 55 (2016), no. 4, 963–971. MR 3505337, DOI 10.1007/s00454-016-9778-2
J. Pach and J. Solymosi, Canonical theorems for convex sets, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 427–435. Dedicated to the memory of Paul Erdős. MR 1608884, DOI 10.1007/PL00009360
Attila Pór and Pavel Valtr, The partitioned version of the Erdős-Szekeres theorem, Discrete Comput. Geom. 28 (2002), no. 4, 625–637. Discrete and computational geometry and graph drawing (Columbia, SC, 2001). MR 1949905, DOI 10.1007/s00454-002-2894-1
Andrew Suk, A note on order-type homogeneous point sets, Mathematika 60 (2014), no. 1, 37–42. MR 3164517, DOI 10.1112/S0025579313000247
Géza Tóth and Pavel Valtr, The Erdős-Szekeres theorem: upper bounds and related results, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 557–568. MR 2178339
G. Tóth and P. Valtr, Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 457–459. Dedicated to the memory of Paul Erdős. MR 1615130, DOI 10.1007/PL00009363