The Erdos-Szekeres problem on points in convex position – a survey
Authors:
W. Morris and V. Soltan
Journal:
Bull. Amer. Math. Soc. 37 (2000), 437-458
MSC (2000):
Primary 52C10
DOI:
https://doi.org/10.1090/S0273-0979-00-00877-6
Published electronically:
June 26, 2000
MathSciNet review:
1779413
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: In 1935 Erdős and Szekeres proved that for any integer $n \ge 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 \ge 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.
- 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. MR 988745, DOI https://doi.org/10.1007/BF02187725
- 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). MR 208467 ar85 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.
- Imre Bárány and Zoltán Füredi, Empty simplices in Euclidean space, Canad. Math. Bull. 30 (1987), no. 4, 436–445. MR 919433, DOI https://doi.org/10.4153/CMB-1987-064-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, DOI https://doi.org/10.1007/PL00009350
- A. Bialostocki, P. Dierker, and B. Voxman, Some notes on the Erdős-Szekeres theorem, Discrete Math. 91 (1991), no. 3, 231–238. MR 1129987, DOI https://doi.org/10.1016/0012-365X%2890%2990232-7
- T. Bisztriczky and G. Fejes Tóth, A generalization of the Erdős-Szekeres convex $n$-gon theorem, J. Reine Angew. Math. 395 (1989), 167–170. MR 983064, DOI https://doi.org/10.1515/crll.1989.395.167
- 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. MR 1009885, DOI https://doi.org/10.1007/BF00184161
- T. Bisztriczky and G. Fejes Tóth, Convexly independent sets, Combinatorica 10 (1990), no. 2, 195–202. MR 1082649, DOI https://doi.org/10.1007/BF02123010
- Tibor Bisztriczky and Heiko Harborth, On empty convex polytopes, J. Geom. 52 (1995), no. 1-2, 25–29. MR 1317252, DOI https://doi.org/10.1007/BF01406823
- T. Bisztriczky and V. Soltan, Some Erdős-Szekeres type results about points in space, Monatsh. Math. 118 (1994), no. 1-2, 33–40. MR 1289846, DOI https://doi.org/10.1007/BF01305772
- W. E. Bonnice, On convex polygons determined by a finite planar set, Amer. Math. Monthly 81 (1974), 749–752. MR 355827, DOI https://doi.org/10.2307/2319566
- Peter B. Borwein, On monochromatic triangles, J. Combin. Theory Ser. A 37 (1984), no. 2, 200–204. MR 757616, DOI https://doi.org/10.1016/0097-3165%2884%2990072-4 car11Carathéodory C., Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo 32 (1911), 193–217.
- Yair Caro, On the generalized Erdős-Szekeres conjecture—a new upper bound, Discrete Math. 160 (1996), no. 1-3, 229–233. MR 1417573, DOI https://doi.org/10.1016/0012-365X%2895%2900162-P
- 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 https://doi.org/10.1007/PL00009353
- Fan Chung and Ron Graham, Erdős on graphs, A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems. MR 1601954
- V. Chvátal and G. Klincsek, Finding largest convex subsets, Congr. Numer. 29 (1980), 453–460. MR 608447
- W. A. Coppel, Foundations of convex geometry, Australian Mathematical Society Lecture Series, vol. 12, Cambridge University Press, Cambridge, 1998. MR 1629043 cfg91 Croft H.T., Falconer K.J., Guy R.K., Unsolved Problems in Geometry, Springer-Verlag, New York, 1991. (Corrected reprint: Springer-Verlag, New York, 1994) ;
- 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. MR 0157289
- David P. Dobkin, Herbert Edelsbrunner, and Mark H. Overmars, Searching for empty convex polygons, Algorithmica 5 (1990), no. 4, 561–571. MR 1072807, DOI https://doi.org/10.1007/BF01840404 dum00 Dumitrescu A., Planar point sets with few empty convex polygons, Studia Sci. Math. Hungar. 36 (2000), to appear.
- Paul H. Edelman and Robert E. Jamison, The theory of convex geometries, Geom. Dedicata 19 (1985), no. 3, 247–270. MR 815204, DOI https://doi.org/10.1007/BF00149365 erd61 Erdős P., Some unsolved problems, Magyar Tud. Akad. Mat. Kut. Int. Kozl. 6 (1961), 221–254. Partially reprinted in: Paul Erdős: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 15–22, MIT Press, Cambridge, MA, 1973. ;
- Paul Erdős, On some problems of elementary and combinatorial geometry, Ann. Mat. Pura Appl. (4) 103 (1975), 99–108. MR 411984, DOI https://doi.org/10.1007/BF02414146
- P. Erdős, Some more problems on elementary geometry, Austral. Math. Soc. Gaz. 5 (1978), no. 2, 52–54. MR 509363
- 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. MR 525325
- 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. MR 585852
- 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 https://doi.org/10.1007/978-3-642-60408-9_3
- 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. MR 1373673 es35 Erdős P., Szekeres G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. Reprinted in: Paul Erdős: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 3–12, MIT Press, Cambridge, MA, 1973. Reprinted in: Classic Papers in Combinatorics (I. Gessel and G.-C. Rota, eds.), pp. 49–56, Birkhäuser, Basel, 1987. ; es61 Erdős P., Szekeres G., On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1961), 53–62. Reprinted in: Paul Erdős: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 680–689, MIT Press, Cambridge, MA, 1973. ;
- Paul Erdős, Zsolt Tuza, and Pavel Valtr, Ramsey-remainder, European J. Combin. 17 (1996), no. 6, 519–532. MR 1401908, DOI https://doi.org/10.1006/eujc.1996.0045
- 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. MR 1661381, DOI https://doi.org/10.1090/conm/223/03136
- Jacob E. Goodman and Richard Pollack, A combinatorial perspective on some problems in geometry, Congr. Numer. 32 (1981), 383–394. MR 681897
- Jacob E. Goodman and Richard Pollack, A theorem of ordered duality, Geom. Dedicata 12 (1982), no. 1, 63–74. MR 645039, DOI https://doi.org/10.1007/BF00147331
- 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. MR 1425213, DOI https://doi.org/10.1007/978-3-642-60406-5_16
- 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. MR 1044995
- Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 0226496 hd55 Hadwiger H., Debrunner H., Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene, Enseign. Math. 1 (1955), 56–89. hd60 Hadwiger H., Debrunner M., Kombinatorische Geometrie in der Ebene, Inst. Math. Univ., Genève, 1960. (English translation: Hadwiger H., Debrunner M., and Klee V., Combinatorial Geometry in the Plane, Holt, Rinehart and Winston, New York, 1964.) ;
- Heiko Harborth, Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. 33 (1978), no. 5, 116–118 (German). MR 510092
- Heiko Harborth and Meinhard Möller, The Esther Klein problem in the projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171–179. MR 1274574 hof98 Hoffman P., The Man Who Loved Only Numbers, Hyperion, New York, 1998.
- J. D. Horton, Sets with no empty convex $7$-gons, Canad. Math. Bull. 26 (1983), no. 4, 482–484. MR 716589, DOI https://doi.org/10.4153/CMB-1983-077-8 hu00 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.
- Robert E. Jamison-Waldner, Partition numbers for trees and ordered sets, Pacific J. Math. 96 (1981), no. 1, 115–140. MR 634767
- Scott Johnson, A new proof of the Erdős-Szekeres convex $k$-gon result, J. Combin. Theory Ser. A 42 (1986), no. 2, 318–319. MR 847566, DOI https://doi.org/10.1016/0097-3165%2886%2990106-8
- J. D. Kalbfleisch, J. G. Kalbfleisch, and R. G. Stanton, A combinatorial problem on convex $n$-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. MR 0273516
- J. G. Kalbfleisch and R. G. Stanton, On the maximum number of coplanar points containing no convex $n$-gons, Utilitas Math. 47 (1995), 235–245. MR 1330906 kar00 Károlyi G., Ramsey-remainder for convex sets and the Erdős-Szekeres Theorem, Discr. Appl. Math., to appear. kpt00 Károlyi G., Pach J., Tóth G., A modular version of the Erdős-Szekeres Theorem, in preparation. kv00 Károlyi G., Valtr P., Sets in $R^d$ without large convex subsets, in preparation.
- M. Katchalski and A. Meir, On empty triangles determined by points in the plane, Acta Math. Hungar. 51 (1988), no. 3-4, 323–328. MR 956984, DOI https://doi.org/10.1007/BF01903339
- 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. MR 1133201
- 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 https://doi.org/10.1007/PL00009358
- 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. MR 771879
- Bernhard Korte, László Lovász, and Rainer Schrader, Greedoids, Algorithms and Combinatorics, vol. 4, Springer-Verlag, Berlin, 1991. MR 1183735
- M. Lewin, A new proof of a theorem of Erdős and Szekeres, Math. Gaz. 60 (1976), no. 412, 136–138. MR 491221, DOI https://doi.org/10.2307/3616247
- L. Lovász, Combinatorial problems and exercises, North-Holland Publishing Co., Amsterdam-New York, 1979. MR 537284 mor99 Morris W.D., Convex dimension of locally planar convex geometries, Discrete Comput. Geom., to appear.
- Theodore S. Motzkin, Cooperative classes of finite sets in one and more dimensions, J. Combinatorial Theory 3 (1967), 244–251. MR 214478
- Theodore S. Motzkin and P. E. O’Neil, Bounds assuring subsets in convex position, J. Combinatorial Theory 3 (1967), 252–255. MR 214479
- Jaroslav Nešetřil and Pavel Valtr, A Ramsey-type theorem in the plane, Combin. Probab. Comput. 3 (1994), no. 1, 127–135. MR 1285694, DOI https://doi.org/10.1017/S0963548300001024 nie95 Nielsen M.J., Transverse matchings on a finite planar set (Manuscript), University of Idaho, Moscow, 1995. osv89 Overmars M., Scholten B., Vincent I., Sets without empty convex 6-gons, Bull. European Assoc. Theor. Comput. Sci. No. 37 (1989), 160–168.
- 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 https://doi.org/10.1007/PL00009360
- 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. MR 1608885, DOI https://doi.org/10.1007/PL00009361 pt00 Pach J., Tóth G., Erdős-Szekeres type theorems for segments and non-crossing convex sets, Geometriae Dedicata, to appear. pur82 Purdy G.B., The minimum number of empty triangles, AMS Abstracts 3 (1982), 318.
- Ira Gessel and Gian-Carlo Rota (eds.), Classic papers in combinatorics, Birkhäuser Boston, Inc., Boston, MA, 1987. MR 904286
- Bruce Schechter, My brain is open, Simon & Schuster, New York, 1998. The mathematical journeys of Paul Erdős. MR 1638921
- Peter Schmitt, Problems in discrete and combinatorial geometry, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 449–483. MR 1242987
- V. P. Soltan, Vvedenie v aksiomaticheskuyu teoriyu vypuklosti, “Shtiintsa”, Kishinev, 1984 (Russian). With English and French summaries. MR 779643 sol88 Solymosi J., Combinatorial Problems in Finite Ramsey Theory, Master’s Thesis, Eötvös University, Budapest, 1988. ste13 Steinitz E., Bedingt konvergente Reihen und konvexe Systeme, J. Reine Angew. Math. 143 (1913), 128–175; 144 (1914), 1–40; 146 (1916), 1–52.
- 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. MR 0532670 tot00 Tóth G., Finding convex sets in convex position, Combinatorica, to appear.
- 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 https://doi.org/10.1007/PL00009363
- Masatsugu Urabe, On a partition into convex polygons, Discrete Appl. Math. 64 (1996), no. 2, 179–191. MR 1368270, DOI https://doi.org/10.1016/0166-218X%2894%2900120-3
- Pavel Valtr, Convex independent sets and $7$-holes in restricted planar point sets, Discrete Comput. Geom. 7 (1992), no. 2, 135–152. MR 1139076, DOI https://doi.org/10.1007/BF02187831
- Pavel Valtr, Sets in ${\bf R}^d$ 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. MR 1189834, DOI https://doi.org/10.1016/0012-365X%2892%2990665-3
- P. Valtr, On the minimum number of empty polygons in planar point sets, Studia Sci. Math. Hungar. 30 (1995), no. 1-2, 155–163. MR 1341574 val96 Valtr P., Several Results Related to the Erdős–Szekeres Theorem, Doctoral Dissertation, Charles University, Prague, 1996.
- Pavel Valtr, On mutually avoiding sets, The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Springer, Berlin, 1997, pp. 324–332. MR 1425226, DOI https://doi.org/10.1007/978-3-642-60406-5_30
- M. L. J. van de Vel, Theory of convex structures, North-Holland Mathematical Library, vol. 50, North-Holland Publishing Co., Amsterdam, 1993. MR 1234493 wat69 Watson F.R., XIth International Mathematical Olympiad. Bucharest, July 1969, Math. Gaz. 53 (1969), 395–396. wat70 Watson F.R., A problem on convex quadrilaterals, Math. Spectrum 2 (1969/70), 54–57.
Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 52C10
Retrieve articles in all journals with MSC (2000): 52C10
Additional Information
W. Morris
Affiliation:
Department of Mathematical Sciences, George Mason University, 4400 University Drive, Fairfax, VA 22030
V. Soltan
Affiliation:
Department of Mathematical Sciences, George Mason University, 4400 University Drive, Fairfax, VA 22030
Keywords:
Erdos-Szekeres problem,
Ramsey theory,
convex polygons and polyhedra,
generalized convexity
Received by editor(s):
December 20, 1999
Received by editor(s) in revised form:
April 4, 2000
Published electronically:
June 26, 2000
Article copyright:
© Copyright 2000
American Mathematical Society