## On the Erdős-Szekeres convex polygon problem

HTML articles powered by AMS MathViewer

- by Andrew Suk PDF
- J. Amer. Math. Soc.
**30**(2017), 1047-1053 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

## Additional Information

**Andrew Suk**- Affiliation: University of Illinois, Chicago, Illinois 60607
- Email: suk@uic.edu
- 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.
- © Copyright 2016 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**30**(2017), 1047-1053 - MSC (2010): Primary 52C10; Secondary 05D10
- DOI: https://doi.org/10.1090/jams/869
- MathSciNet review: 3671936