The Erdos-Szekeres problem on points in convex position – a survey
HTML articles powered by AMS MathViewer
- by W. Morris and V. Soltan PDF
- Bull. Amer. Math. Soc. 37 (2000), 437-458 Request permission
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.References
- 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 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 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 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 10.1016/0012-365X(90)90232-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 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 10.1007/BF00184161
- T. Bisztriczky and G. Fejes Tóth, Convexly independent sets, Combinatorica 10 (1990), no. 2, 195–202. MR 1082649, DOI 10.1007/BF02123010
- Tibor Bisztriczky and Heiko Harborth, On empty convex polytopes, J. Geom. 52 (1995), no. 1-2, 25–29. MR 1317252, DOI 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 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 10.2307/2319566
- Peter B. Borwein, On monochromatic triangles, J. Combin. Theory Ser. A 37 (1984), no. 2, 200–204. MR 757616, DOI 10.1016/0097-3165(84)90072-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 10.1016/0012-365X(95)00162-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 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, DOI 10.1201/9781439863879
- 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
- W. J. Trjitzinsky, General theory of singular integral equations with real kernels, Trans. Amer. Math. Soc. 46 (1939), 202–279. MR 92, DOI 10.1090/S0002-9947-1939-0000092-6
- 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 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 10.1007/BF00149365
- G. A. Miller, Groups which contain ten or eleven proper subgroups, Proc. Nat. Acad. Sci. U.S.A. 25 (1939), 540–543. MR 31, DOI 10.1073/pnas.25.10.540
- Paul Erdős, On some problems of elementary and combinatorial geometry, Ann. Mat. Pura Appl. (4) 103 (1975), 99–108. MR 411984, DOI 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 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
- Leo F. Epstein, A function related to the series for $e^{e^x}$, J. Math. Phys. Mass. Inst. Tech. 18 (1939), 153–173. MR 58, DOI 10.1002/sapm1939181153
- A. Gloden, Sur la résolution en nombres entiers du système $A^{kx}+B^{kx}+C^{kx}+D^{kx}=E^x+F^x+G^x+H^x$ ($x=1$, $2$ et $3$), Bol. Mat. 12 (1939), 118–122 (French). MR 24
- Paul Erdős, Zsolt Tuza, and Pavel Valtr, Ramsey-remainder, European J. Combin. 17 (1996), no. 6, 519–532. MR 1401908, DOI 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 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 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 10.1007/978-3-642-60406-5_{1}6
- 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
- Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
- P. Erdös, Note on products of consecutive integers, J. London Math. Soc. 14 (1939), 194–198. MR 22, DOI 10.1112/jlms/s1-14.3.194
- 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 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, DOI 10.2140/pjm.1981.96.115
- 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 10.1016/0097-3165(86)90106-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 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, DOI 10.1090/dol/011
- 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
- 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, DOI 10.1007/978-3-642-58191-5
- M. Lewin, A new proof of a theorem of Erdős and Szekeres, Math. Gaz. 60 (1976), no. 412, 136–138. MR 491221, DOI 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, DOI 10.1016/S0021-9800(67)80072-3
- Theodore S. Motzkin and P. E. O’Neil, Bounds assuring subsets in convex position, J. Combinatorial Theory 3 (1967), 252–255. MR 214479, DOI 10.1016/S0021-9800(67)80073-5
- 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 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 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 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, DOI 10.1007/978-0-8176-4842-8
- 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, Mathematicians of Our Time, Vol. 5, MIT Press, Cambridge, Mass.-London, 1973. Edited by Joel Spencer and with a dedication by Richard Rado. 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 10.1007/PL00009363
- Masatsugu Urabe, On a partition into convex polygons, Discrete Appl. Math. 64 (1996), no. 2, 179–191. MR 1368270, DOI 10.1016/0166-218X(94)00120-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 10.1007/BF02187831
- Pavel Valtr, Sets in $\textbf {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 10.1016/0012-365X(92)90665-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 10.1007/978-3-642-60406-5_{3}0
- 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.
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
- Received by editor(s): December 20, 1999
- Received by editor(s) in revised form: April 4, 2000
- Published electronically: June 26, 2000
- © Copyright 2000 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 37 (2000), 437-458
- MSC (2000): Primary 52C10
- DOI: https://doi.org/10.1090/S0273-0979-00-00877-6
- MathSciNet review: 1779413