Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

On the Erdős-Szekeres convex polygon problem


Author: Andrew Suk
Journal: J. Amer. Math. Soc. 30 (2017), 1047-1053
MSC (2010): Primary 52C10; Secondary 05D10
DOI: https://doi.org/10.1090/jams/869
Published electronically: September 30, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1007/PL00009350
  • [2] Peter Brass, William Moser, and János Pach, Research problems in discrete geometry, Springer, New York, 2005. MR 2163782
  • [3] 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, https://doi.org/10.1007/PL00009353
  • [4] R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161-166. MR 0032578
  • [5] 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, https://doi.org/10.1112/S0025579314000072
  • [6] 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, https://doi.org/10.1007/978-3-642-60408-9_3
  • [7] P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463-470. MR 1556929
  • [8] 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/1961), 53-62. MR 0133735
  • [9] 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, https://doi.org/10.1112/plms/pds018
  • [10] Alfredo Hubard, Luis Montejano, Emiliano Mora, and Andrew Suk, Order types of convex bodies, Order 28 (2011), no. 1, 121-130. MR 2774044, https://doi.org/10.1007/s11083-010-9156-2
  • [11] 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, https://doi.org/10.1016/S0166-218X(00)00234-1
  • [12] 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, https://doi.org/10.1007/s00454-003-0009-4
  • [13] 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, https://doi.org/10.1007/PL00009358
  • [14] Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299
  • [15] 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 (electronic). MR 1779413, https://doi.org/10.1090/S0273-0979-00-00877-6
  • [16] 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, https://doi.org/10.1016/j.aim.2014.06.008
  • [17] 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, https://doi.org/10.1007/s00454-016-9791-5
  • [18] Sergey Norin and Yelena Yuditsky, Erdős-Szekeres Without Induction, Discrete Comput. Geom. 55 (2016), no. 4, 963-971. MR 3505337, https://doi.org/10.1007/s00454-016-9778-2
  • [19] 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, https://doi.org/10.1007/PL00009360
  • [20] Attila Pór and Pavel Valtr, The partitioned version of the Erdős-Szekeres theorem, Discrete Comput. Geom. 28 (2002), no. 4, 625637. Discrete and computational geometry and graph drawing (Columbia, SC, 2001). MR 1949905, https://doi.org/10.1007/s00454-002-2894-1
  • [21] Andrew Suk, A note on order-type homogeneous point sets, Mathematika 60 (2014), no. 1, 37-42. MR 3164517, https://doi.org/10.1112/S0025579313000247
  • [22] 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
  • [23] 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, https://doi.org/10.1007/PL00009363

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 52C10, 05D10

Retrieve articles in all journals with MSC (2010): 52C10, 05D10


Additional Information

Andrew Suk
Affiliation: University of Illinois, Chicago, Illinois 60607
Email: suk@uic.edu

DOI: https://doi.org/10.1090/jams/869
Received by editor(s): May 3, 2016
Received by editor(s) in revised form: August 26, 2016
Published electronically: September 30, 2016
Additional Notes: The author is supported by NSF grant DMS-1500153.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society