On the Erdős-Szekeres convex polygon problem

Suk, Andrew ¹

¹ University of Illinois, Chicago, Illinois 60607

Journal of the American Mathematical Society, Tome 30 (2017) no. 4, pp. 1047-1053

Résumé

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)}$.

Détail

DOI : 10.1090/jams/869

Bibliographie

[1] Bárány, I., Valtr, P. A positive fraction Erdős-Szekeres theorem Discrete Comput. Geom. 1998 335 342

[2] Brass, Peter, Moser, William, Pach, János Research problems in discrete geometry 2005

[3] Chung, F. R. K., Graham, R. L. Forced convex 𝑛-gons in the plane Discrete Comput. Geom. 1998 367 371

[4] Dilworth, R. P. A decomposition theorem for partially ordered sets Ann. of Math. (2) 1950 161 166

[5] Dobbins, Michael Gene, Holmsen, Andreas, Hubard, Alfredo The Erdős-Szekeres problem for non-crossing convex sets Mathematika 2014 463 484

[6] Erdős, Paul Some of my favorite problems and results 1997 47 67

[7] Erdös, P., Szekeres, G. A combinatorial problem in geometry Compositio Math. 1935 463 470

[8] Erdős, P., Szekeres, G. On some extremum problems in elementary geometry Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 1960/61 53 62

[9] Fox, Jacob, Pach, János, Sudakov, Benny, Suk, Andrew Erdős-Szekeres-type theorems for monotone paths and convex bodies Proc. Lond. Math. Soc. (3) 2012 953 982

[10] Hubard, Alfredo, Montejano, Luis, Mora, Emiliano, Suk, Andrew Order types of convex bodies Order 2011 121 130

[11] Károlyi, Gyula Ramsey-remainder for convex sets and the Erdős-Szekeres theorem Discrete Appl. Math. 2001 163 175

[12] Károlyi, Gyula, Valtr, Pavel Point configurations in 𝑑-space without large subsets in convex position Discrete Comput. Geom. 2003 277 286

[13] Kleitman, D., Pachter, L. Finding convex sets among points in the plane Discrete Comput. Geom. 1998 405 410

[14] Matoušek, Jiří Lectures on discrete geometry 2002

[15] Morris, W., Soltan, V. The Erdős-Szekeres problem on points in convex position—a survey Bull. Amer. Math. Soc. (N.S.) 2000 437 458

[16] Moshkovitz, Guy, Shapira, Asaf Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem Adv. Math. 2014 1107 1129

[17] Mojarrad, Hossein Nassajian, Vlachos, Georgios An improved upper bound for the Erdős-Szekeres conjecture Discrete Comput. Geom. 2016 165 180

[18] Norin, Sergey, Yuditsky, Yelena Erdős-Szekeres without induction Discrete Comput. Geom. 2016 963 971

[19] Pach, J., Solymosi, J. Canonical theorems for convex sets Discrete Comput. Geom. 1998 427 435

[20] Pór, Attila, Valtr, Pavel The partitioned version of the Erdős-Szekeres theorem Discrete Comput. Geom. 2002 625 637

[21] Suk, Andrew A note on order-type homogeneous point sets Mathematika 2014 37 42

[22] Tóth, Géza, Valtr, Pavel The Erdős-Szekeres theorem: upper bounds and related results 2005 557 568

[23] Tóth, G., Valtr, P. Note on the Erdős-Szekeres theorem Discrete Comput. Geom. 1998 457 459