The Erdos-Szekeres problem on points in convex position – a survey

Morris, W.; Soltan, V.

doi:10.1090/S0273-0979-00-00877-6

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.