×

zbMATH — the first resource for mathematics

The Erdős-Szekeres problem on points in convex position – a survey. (English) Zbl 0958.52018
Summary: In 1935, P. Erdős and G. Szekeres [Compos. Math. 2, 463-470 (1935; Zbl 0012.27010)] proved that for any integer \(n \geq 3\) there exists a smallest positive integer \(N(n)\) such that any set of at least \(N(n)\) points in general position in the plane contains \(n\) points that are the vertices of a convex \(n\)-gon. They also posed the problem to determine the value of \(N(n)\) and conjectured that \(N(n) = 2^{n-2} +1\) for all \(n \geq 3\).
Despite the efforts of many mathematicians, the Erdős-Szekeres problem is still far from being solved. This paper surveys the known results and questions related to the Erdős-Szekeres problem in the plane and higher dimensions, as well as its generalizations for the cases of families of convex bodies and the abstract convexity setting.

MSC:
52C10 Erdős problems and related topics of discrete geometry
52-02 Research exposition (monographs, survey articles) pertaining to convex and discrete geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon, M. Katchalski, and W. R. Pulleyblank, The maximum size of a convex polygon in a restricted set of points in the plane, Discrete Comput. Geom. 4 (1989), no. 3, 245 – 251. · Zbl 0719.52007 · doi:10.1007/BF02187725 · doi.org
[2] R. V. Ambarcumjan, Convex subclusters of point clusters in the plane, Akad. Nauk Armjan. SSR Dokl. 43 (1966), no. 1, 12 – 14 (Russian, with Armenian summary).
[3] AVIS D., RAPPAPORT D., Computing the largest empty convex subsets of a set of points, Proc. First ACM Symp. Comput. Geom. Baltimore, 1985, pp. 161-167.
[4] Imre Bárány and Zoltán Füredi, Empty simplices in Euclidean space, Canad. Math. Bull. 30 (1987), no. 4, 436 – 445. · Zbl 0639.52006 · doi:10.4153/CMB-1987-064-1 · doi.org
[5] 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. · Zbl 0914.52007 · doi:10.1007/PL00009350 · doi.org
[6] A. Bialostocki, P. Dierker, and B. Voxman, Some notes on the Erdős-Szekeres theorem, Discrete Math. 91 (1991), no. 3, 231 – 238. · Zbl 0769.52014 · doi:10.1016/0012-365X(90)90232-7 · doi.org
[7] T. Bisztriczky and G. Fejes Tóth, A generalization of the Erdős-Szekeres convex \?-gon theorem, J. Reine Angew. Math. 395 (1989), 167 – 170. · Zbl 0654.52003 · doi:10.1515/crll.1989.395.167 · doi.org
[8] T. Bisztriczky and G. Fejes Tóth, Nine convex sets determine a pentagon with convex sets as vertices, Geom. Dedicata 31 (1989), no. 1, 89 – 104. · Zbl 0677.52003 · doi:10.1007/BF00184161 · doi.org
[9] T. Bisztriczky and G. Fejes Tóth, Convexly independent sets, Combinatorica 10 (1990), no. 2, 195 – 202. · Zbl 0717.52003 · doi:10.1007/BF02123010 · doi.org
[10] Tibor Bisztriczky and Heiko Harborth, On empty convex polytopes, J. Geom. 52 (1995), no. 1-2, 25 – 29. · Zbl 0818.52008 · doi:10.1007/BF01406823 · doi.org
[11] T. Bisztriczky and V. Soltan, Some Erdős-Szekeres type results about points in space, Monatsh. Math. 118 (1994), no. 1-2, 33 – 40. · Zbl 0811.52005 · doi:10.1007/BF01305772 · doi.org
[12] W. E. Bonnice, On convex polygons determined by a finite planar set, Amer. Math. Monthly 81 (1974), 749 – 752. · Zbl 0295.52002 · doi:10.2307/2319566 · doi.org
[13] Peter B. Borwein, On monochromatic triangles, J. Combin. Theory Ser. A 37 (1984), no. 2, 200 – 204. · Zbl 0545.52007 · doi:10.1016/0097-3165(84)90072-4 · doi.org
[14] CARATHÉODORY C., Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo 32 (1911), 193-217. · JFM 42.0429.01
[15] Yair Caro, On the generalized Erdős-Szekeres conjecture — a new upper bound, Discrete Math. 160 (1996), no. 1-3, 229 – 233. · Zbl 0868.52006 · doi:10.1016/0012-365X(95)00162-P · doi.org
[16] F. R. K. Chung and R. L. Graham, Forced convex \?-gons in the plane, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 367 – 371. Dedicated to the memory of Paul Erdős. · Zbl 0908.52004 · doi:10.1007/PL00009353 · doi.org
[17] Fan Chung and Ron Graham, Erdős on graphs, A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems. · Zbl 0890.05049
[18] V. Chvátal and G. Klincsek, Finding largest convex subsets, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. II, 1980, pp. 453 – 460. · Zbl 0474.52004
[19] W. A. Coppel, Foundations of convex geometry, Australian Mathematical Society Lecture Series, vol. 12, Cambridge University Press, Cambridge, 1998. · Zbl 0901.52001
[20] Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy, Unsolved problems in geometry, Problem Books in Mathematics, Springer-Verlag, New York, 1991. Unsolved Problems in Intuitive Mathematics, II. Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy, Unsolved problems in geometry, Problem Books in Mathematics, Springer-Verlag, New York, 1994. Corrected reprint of the 1991 original [ MR1107516 (92c:52001)]; Unsolved Problems in Intuitive Mathematics, II. · Zbl 0748.52001
[21] Ludwig Danzer, Branko Grünbaum, and Victor Klee, Helly’s theorem and its relatives, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 101 – 180. · Zbl 0132.17401
[22] David P. Dobkin, Herbert Edelsbrunner, and Mark H. Overmars, Searching for empty convex polygons, Algorithmica 5 (1990), no. 4, 561 – 571. · Zbl 0697.68034 · doi:10.1007/BF01840404 · doi.org
[23] DUMITRESCU A., Planar point sets with few empty convex polygons, Studia Sci. Math. Hungar. 36 (2000), to appear. · Zbl 0980.52007
[24] Paul H. Edelman and Robert E. Jamison, The theory of convex geometries, Geom. Dedicata 19 (1985), no. 3, 247 – 270. · Zbl 0577.52001 · doi:10.1007/BF00149365 · doi.org
[25] Paul Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221 – 254. Paul Erdős, The art of counting: Selected writings, The MIT Press, Cambridge, Mass.-London, 1973. Edited by Joel Spencer and with a dedication by Richard Rado; Mathematicians of Our Time, Vol. 5.
[26] Paul Erdős, On some problems of elementary and combinatorial geometry, Ann. Mat. Pura Appl. (4) 103 (1975), 99 – 108. · Zbl 0303.52006 · doi:10.1007/BF02414146 · doi.org
[27] P. Erdős, Some more problems on elementary geometry, Austral. Math. Soc. Gaz. 5 (1978), no. 2, 52 – 54. · Zbl 0417.52002
[28] Paul Erdős, Combinatorial problems in geometry and number theory, Relations between combinatorics and other parts of mathematics (Proc. Sympos. Pure Math., Ohio State Univ., Columbus, Ohio, 1978) Proc. Sympos. Pure Math., XXXIV, Amer. Math. Soc., Providence, R.I., 1979, pp. 149 – 162.
[29] P. Erdős, Some combinational problems in geometry, Geometry and differential geometry (Proc. Conf., Univ. Haifa, Haifa, 1979), Lecture Notes in Math., vol. 792, Springer, Berlin, 1980, pp. 46 – 53.
[30] 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. · Zbl 0871.11004 · doi:10.1007/978-3-642-60408-9_3 · doi.org
[31] Paul Erdős and George Purdy, Extremal problems in combinatorial geometry, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 809 – 874. · Zbl 0852.52009
[32] Paul Erdős, The art of counting: Selected writings, The MIT Press, Cambridge, Mass.-London, 1973. Edited by Joel Spencer and with a dedication by Richard Rado; Mathematicians of Our Time, Vol. 5. Ira Gessel and Gian-Carlo Rota , Classic papers in combinatorics, Birkhäuser Boston, Inc., Boston, MA, 1987.
[33] 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. Paul Erdős, The art of counting: Selected writings, The MIT Press, Cambridge, Mass.-London, 1973. Edited by Joel Spencer and with a dedication by Richard Rado; Mathematicians of Our Time, Vol. 5.
[34] Paul Erdős, Zsolt Tuza, and Pavel Valtr, Ramsey-remainder, European J. Combin. 17 (1996), no. 6, 519 – 532. · Zbl 0858.05073 · doi:10.1006/eujc.1996.0045 · doi.org
[35] Gábor Fejes Tóth, Recent progress on packing and covering, Advances in discrete and computational geometry (South Hadley, MA, 1996) Contemp. Math., vol. 223, Amer. Math. Soc., Providence, RI, 1999, pp. 145 – 162. · Zbl 0928.52010 · doi:10.1090/conm/223/03136 · doi.org
[36] Jacob E. Goodman and Richard Pollack, A combinatorial perspective on some problems in geometry, Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981), 1981, pp. 383 – 394. · Zbl 0495.05012
[37] Jacob E. Goodman and Richard Pollack, A theorem of ordered duality, Geom. Dedicata 12 (1982), no. 1, 63 – 74. · Zbl 0494.51002 · doi:10.1007/BF00147331 · doi.org
[38] R. L. Graham and J. Nešetřil, Ramsey theory in the work of Paul Erdős, The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Springer, Berlin, 1997, pp. 193 – 209. · Zbl 0863.05077 · doi:10.1007/978-3-642-60406-5_16 · doi.org
[39] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. · Zbl 0705.05061
[40] Branko Grünbaum, Convex polytopes, With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. · Zbl 0152.20602
[41] HADWIGER H., DEBRUNNER H., Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene, Enseign. Math. 1 (1955), 56-89.
[42] H. Hadwiger and H. Debrunner, Kombinatorische Geometrie in der Ebene, Monographies de ”L’Enseignement Mathématique”, No. 2, Institut de Mathématiques, Université, Genève, 1960 (German). Hugo Hadwiger and Hans Debrunner, Combinatorial geometry in the plane, Translated by Victor Klee. With a new chapter and other additional material supplied by the translator, Holt, Rinehart and Winston, New York, 1964.
[43] Heiko Harborth, Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. 33 (1978), no. 5, 116 – 118 (German). · Zbl 0397.52005
[44] Heiko Harborth and Meinhard Möller, The Esther Klein problem in the projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171 – 179. · Zbl 0807.51008
[45] HOFFMAN P., The Man Who Loved Only Numbers, Hyperion, New York, 1998. CMP 99:07 · Zbl 0917.01035
[46] J. D. Horton, Sets with no empty convex 7-gons, Canad. Math. Bull. 26 (1983), no. 4, 482 – 484. · Zbl 0521.52010 · doi:10.4153/CMB-1983-077-8 · doi.org
[47] HOSONO K., URABE M., On the number of disjoint convex quadrilaterals for a given point set in the plane, Comput. Geom. Theory and Applications, submitted. · Zbl 0990.68171
[48] Robert E. Jamison-Waldner, Partition numbers for trees and ordered sets, Pacific J. Math. 96 (1981), no. 1, 115 – 140. · Zbl 0482.52010
[49] Scott Johnson, A new proof of the Erdős-Szekeres convex \?-gon result, J. Combin. Theory Ser. A 42 (1986), no. 2, 318 – 319. · Zbl 0591.52005 · doi:10.1016/0097-3165(86)90106-8 · doi.org
[50] J. D. Kalbfleisch, J. G. Kalbfleisch, and R. G. Stanton, A combinatorial problem on convex \?-gons, Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1970) Louisiana State Univ., Baton Rouge, La., 1970, pp. 180 – 188. · Zbl 0223.52009
[51] J. G. Kalbfleisch and R. G. Stanton, On the maximum number of coplanar points containing no convex \?-gons, Utilitas Math. 47 (1995), 235 – 245. · Zbl 0836.52004
[52] KAROLYI G., Ramsey-remainder for convex sets and the Erdos-Szekeres Theorem, Discr. Appl. Math., to appear.
[53] KAROLYI G., PACH J., TOTH G., A modular version of the Erdos-Szekeres Theorem, in preparation.
[54] KAROLYI G., VALTR P., Sets in \(R^d\)without large convex subsets, in preparation.
[55] M. Katchalski and A. Meir, On empty triangles determined by points in the plane, Acta Math. Hungar. 51 (1988), no. 3-4, 323 – 328. · Zbl 0655.52007 · doi:10.1007/BF01903339 · doi.org
[56] Victor Klee and Stan Wagon, Old and new unsolved problems in plane geometry and number theory, The Dolciani Mathematical Expositions, vol. 11, Mathematical Association of America, Washington, DC, 1991. · Zbl 0784.51002
[57] 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. · Zbl 0908.52005 · doi:10.1007/PL00009358 · doi.org
[58] Bernhard Korte and László Lovász, Greedoids — a structural framework for the greedy algorithm, Progress in combinatorial optimization (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1984, pp. 221 – 243. · Zbl 0547.05025
[59] Bernhard Korte, László Lovász, and Rainer Schrader, Greedoids, Algorithms and Combinatorics, vol. 4, Springer-Verlag, Berlin, 1991. · Zbl 0733.05023
[60] M. Lewin, A new proof of a theorem of Erdős and Szekeres, Math. Gaz. 60 (1976), no. 412, 136 – 138. · Zbl 0362.05043 · doi:10.2307/3616247 · doi.org
[61] L. Lovász, Combinatorial problems and exercises, North-Holland Publishing Co., Amsterdam-New York, 1979. · Zbl 0439.05001
[62] MORRIS W.D., Convex dimension of locally planar convex geometries, Discrete Comput. Geom., to appear. · Zbl 0970.52001
[63] Theodore S. Motzkin, Cooperative classes of finite sets in one and more dimensions, J. Combinatorial Theory 3 (1967), 244 – 251. · Zbl 0203.01403
[64] Theodore S. Motzkin and P. E. O’Neil, Bounds assuring subsets in convex position, J. Combinatorial Theory 3 (1967), 252 – 255. · Zbl 0203.01404
[65] Jaroslav Nešetřil and Pavel Valtr, A Ramsey-type theorem in the plane, Combin. Probab. Comput. 3 (1994), no. 1, 127 – 135. · Zbl 0803.05052 · doi:10.1017/S0963548300001024 · doi.org
[66] NIELSEN M.J., Transverse matchings on a finite planar set (Manuscript), University of Idaho, Moscow, 1995.
[67] OVERMARS M., SCHOLTEN B., VINCENT I., Sets without empty convex 6-gons, Bull. European Assoc. Theor. Comput. Sci. No. 37 (1989), 160-168. · Zbl 1023.68686
[68] 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. · Zbl 0905.52001 · doi:10.1007/PL00009360 · doi.org
[69] J. Pach and G. Tóth, A generalization of the Erdős-Szekeres theorem to disjoint convex sets, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 437 – 445. Dedicated to the memory of Paul Erdős. · Zbl 0903.52004 · doi:10.1007/PL00009361 · doi.org
[70] PACH J., TOTH G., Erdos-Szekeres type theorems for segments and non-crossing convex sets, Geometriae Dedicata, to appear.
[71] PURDY G.B., The minimum number of empty triangles, AMS Abstracts 3 (1982), 318.
[72] Ira Gessel and Gian-Carlo Rota , Classic papers in combinatorics, Birkhäuser Boston, Inc., Boston, MA, 1987. · Zbl 0612.05001
[73] Bruce Schechter, My brain is open, Simon & Schuster, New York, 1998. The mathematical journeys of Paul Erdős. · Zbl 0969.01018
[74] Peter Schmitt, Problems in discrete and combinatorial geometry, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 449 – 483. · Zbl 0792.52009
[75] Введение в аксиоматическую теорию выпуклости, ”Штиинца”, Кишинев, 1984 (Руссиан). Щитх Енглиш анд Френч суммариес. · Zbl 0559.52001
[76] SOLYMOSI J., Combinatorial Problems in Finite Ramsey Theory, Master’s Thesis, Eötvös University, Budapest, 1988.
[77] STEINITZ E., Bedingt konvergente Reihen und konvexe Systeme, J. Reine Angew. Math. 143 (1913), 128-175; 144 (1914), 1-40; 146 (1916), 1-52.
[78] Paul Erdős, The art of counting: Selected writings, The MIT Press, Cambridge, Mass.-London, 1973. Edited by Joel Spencer and with a dedication by Richard Rado; Mathematicians of Our Time, Vol. 5. · Zbl 0287.01028
[79] TOTH G., Finding convex sets in convex position, Combinatorica, to appear.
[80] 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. · Zbl 0903.52006 · doi:10.1007/PL00009363 · doi.org
[81] Masatsugu Urabe, On a partition into convex polygons, Discrete Appl. Math. 64 (1996), no. 2, 179 – 191. · Zbl 0849.52015 · doi:10.1016/0166-218X(94)00120-3 · doi.org
[82] Pavel Valtr, Convex independent sets and 7-holes in restricted planar point sets, Discrete Comput. Geom. 7 (1992), no. 2, 135 – 152. · Zbl 0748.52005 · doi:10.1007/BF02187831 · doi.org
[83] Pavel Valtr, Sets in \?^\? with no large empty convex subsets, Discrete Math. 108 (1992), no. 1-3, 115 – 124. Topological, algebraical and combinatorial structures. Frolík’s memorial volume. · Zbl 0766.52003 · doi:10.1016/0012-365X(92)90665-3 · doi.org
[84] P. Valtr, On the minimum number of empty polygons in planar point sets, Studia Sci. Math. Hungar. 30 (1995), no. 1-2, 155 – 163. · Zbl 0867.52004
[85] VALTR P., Several Results Related to the Erdos-Szekeres Theorem, Doctoral Dissertation, Charles University, Prague, 1996.
[86] Pavel Valtr, On mutually avoiding sets, The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Springer, Berlin, 1997, pp. 324 – 332. · Zbl 0863.68114 · doi:10.1007/978-3-642-60406-5_30 · doi.org
[87] M. L. J. van de Vel, Theory of convex structures, North-Holland Mathematical Library, vol. 50, North-Holland Publishing Co., Amsterdam, 1993. · Zbl 0785.52001
[88] WATSON F.R., XIth International Mathematical Olympiad. Bucharest, July 1969, Math. Gaz. 53 (1969), 395-396.
[89] WATSON F.R., A problem on convex quadrilaterals, Math. Spectrum 2 (1969/70), 54-57.
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.