Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

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

Abstract | References | Similar Articles | Additional Information

Abstract:

In 1935 Erdos 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 Erdos-Szekeres problem is still far from being solved. This paper surveys the known results and questions related to the Erdos-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 [Enhancements On Off] (What's this?)

  • 1. ALON N., KATCHALSKI M., PULLEYBLANK W.R., The maximum size of a convex polygon in a restricted set of points in the plane, Discrete Comput. Geom. 4 (1989), 245-251. MR 91a:52006
  • 2. AMBARCUMJAN R.V., Convex subclusters of point clusters in the plane, (Russian) Dokl. Acad. Nauk Armjan. SSR 43 (1966), 12-14. MR 34:8277
  • 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. BARANY I., FUREDI Z., Empty simplices in Euclidean space, Canad. Math. Bull. 30 (1987), 436-445. MR 89g:52004
  • 5. BARANY I., VALTR P., A positive fraction Erdos-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 335-342. MR 99a:52024
  • 6. BIALOSTOCKI A., DIERKER P., VOXMAN B., Some notes on the Erdos-Szekeres theorem, Discrete Math. 91 (1991), 231-238. MR 92k:52034
  • 7. BISZTRICZKY T., FEJES TOTH G., A generalization of the Erdos-Szekeres convex $n$-gon theorem, J. Reine Angew. Math. 395 (1989), 167-170. MR 90b:52005
  • 8. BISZTRICZKY T., FEJES TOTH G., Nine convex sets determine a pentagon with convex sets as vertices, Geom. Dedicata 31 (1989), 89-104. MR 90h:52003
  • 9. BISZTRICZKY T., FEJES TOTH G., Convexly independent sets, Combinatorica 10 (1990), 195-202. MR 92c:52005
  • 10. BISZTRICZKY T., HARBORTH H., On empty convex polytopes, J. Geom. 52 (1995), 25-29. MR 95m:52038
  • 11. BISZTRICZKY T., SOLTAN V., Some Erdos-Szekeres type results about points in space, Monatsh. Math. 118 (1994), 33-40. MR 95e:52026
  • 12. BONNICE W.E., On convex polygons determined by a finite planar set, Amer. Math. Monthly 81 (1974), 749-752. MR 50:8301
  • 13. BORWEIN P.B., On monochromatic triangles, J. Combin. Theory Ser. A 37 (1984), 200-204. MR 85h:52013
  • 14. CARATHÉODORY C., Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo 32 (1911), 193-217.
  • 15. CARO Y., On the generalized Erdos-Szekeres conjecture - a new upper bound, Discrete Math. 160 (1996), 229-233. MR 97h:52023
  • 16. CHUNG F.R.L., GRAHAM R.L., Forced convex $n$-gons in the plane, Discrete Comput. Geom. 19 (1998), 367-371. MR 99e:52020
  • 17. CHUNG F.R.L., GRAHAM R.L., Erdos on Graphs. His Legacy of Unsolved Problems. A. K. Peters, Ltd., Wellesley, MA, 1998. MR 99b:05031
  • 18. CHVÁTAL V., KLINCSEK G., Finding largest convex subsets, Congr. Numer. 29 (1980), 453-460. MR 82i:52001
  • 19. COPPEL W. A., Foundations of Convex Geometry, Cambridge University Press, Cambridge, 1998, 222 pp. MR 99f:52001
  • 20. 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) MR 92c:52001; MR 95k:52001
  • 21. DANZER L., GRÜNBAUM B., KLEE V., Helly's theorem and its relatives, pp. 101-179. Convexity (Seattle, 1961), Proc. Symp. Pure Math. Vol. VII. Amer. Math. Soc., Providence, R.I., 1963. MR 28:524
  • 22. DOBKIN D.P., EDELSBRUNNER H., OVERMARS M., Searching for empty convex polygons, Algorithmica 5 (1990), 561-571. MR 91g:68160
  • 23. DUMITRESCU A., Planar point sets with few empty convex polygons, Studia Sci. Math. Hungar. 36 (2000), to appear.
  • 24. EDELMAN P.H., JAMISON R.E., The theory of convex geometries, Geom. Dedicata 19 (1985), 247-270. MR 87f:52002
  • 25. ERDOS P., Some unsolved problems, Magyar Tud. Akad. Mat. Kut. Int. Kozl. 6 (1961), 221-254. Partially reprinted in: Paul Erdos: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 15-22, MIT Press, Cambridge, MA, 1973. MR 31:2106; MR 58:27144
  • 26. ERDOS P., On some problems of elementary and combinatorial geometry, Ann. Mat. Pura Appl. 103 (1975), 99-18. MR 54:113
  • 27. ERDOS P., Some more problems on elementary geometry, Austral. Math. Soc. Gaz. 5 (1978), 52-54. MR 80b:52005
  • 28. ERDOS P., Combinatorial problems in geometry and number theory, Relations Between Combinatorics and Other Parts of Mathematics. Proc. Conf. Ohio State Univ. Columbus, 1978. Proc. Symp. Pure Math. Vol. 34, 1979, pp. 149-162. MR 80i:05001
  • 29. ERDOS P., Some combinatorial problems in geometry, Geometry and Differential Geometry. Proc. Conf. Univ. Haifa, 1979. Lecture Notes Math. 792 (1980), 46-53. MR 82d:51002
  • 30. ERDOS P., Some of my favorite problems and results, The Mathematics of Paul Erdos, Vol. I (R. L. Graham and J. Nesetril, eds.), Springer-Verlag, Berlin, 1997, 47-67. MR 98e:11002
  • 31. ERDOS P., PURDY G., Extremal problems in combinatorial geometry, pp. 809-874. Handbook of Combinatorics (R. L. Graham, M. Grötschel, and L. Lovász, eds.), Elsevier Science, Amsterdam, 1995. MR 96m:52025
  • 32. ERDOS P., SZEKERES G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470. Reprinted in: Paul Erdos: 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. MR 58:27144; MR 88c:01055
  • 33. ERDOS 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 Erdos: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 680-689, MIT Press, Cambridge, MA, 1973. MR 24:A3560; MR 58:27144
  • 34. ERDOS P., TUZA Z., VALTR P., Ramsey remainder, European J. Combin. 17 (1996), 519-532. MR 98d:05146
  • 35. FEJES TOTH G., Recent progress on packing and covering, Advances in Discrete and Computational Geometry, (South Hadley, MA, 1996), pp. 145-162. Contemp. Math. 223 (1999), AMS, Providence, RI, 1999. MR 99g:52036
  • 36. GOODMAN J.E., POLLACK R., A combinatorial perspective on some problems in geometry, Congr. Numer. 32 (1981), 383-394. MR 84b:05003
  • 37. GOODMAN J.E., POLLACK R., A theorem of ordered duality, Geom. Dedicata 12 (1982), 63-74. MR 83f:51009
  • 38. GRAHAM R.L., NESETRIL J. Ramsey theory in the work of Paul Erdos, The Mathematics of Paul Erdos, Vol. II, (R. L. Graham and J. Nesetril, eds.), Springer-Verlag, Berlin, 1997, 193-209. MR 97j:01031
  • 39. GRAHAM R.L., ROTHSCHILD B.L., SPENCER J.H., Ramsey Theory, 2nd edition, Wiley-Interscience, New York, 1990. MR 90m:05003
  • 40. GRÜNBAUM B., Convex Polytopes, Interscience Publishers, New York, 1967. MR 37:2085
  • 41. HADWIGER H., DEBRUNNER H., Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene, Enseign. Math. 1 (1955), 56-89. MR 17:887c
  • 42. 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.) MR 22:11310; MR 29:1577
  • 43. HARBORTH H., Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. 33 (1978), 116-118. MR 80a:52003
  • 44. HARBORTH H., MOLLER M., The Esther Klein problem in the projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171-179. MR 95d:52013
  • 45. HOFFMAN P., The Man Who Loved Only Numbers, Hyperion, New York, 1998. CMP 99:07
  • 46. HORTON J.D., Sets with no empty convex 7-gons, Canad. Math. Bull. 26 (1983), 482-484. MR 85f:52007
  • 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.
  • 48. JAMISON-WALDNER R.E., Partition numbers for trees and ordered sets, Pacific J. Math. 96 (1981), 115-140. MR 83a:52003
  • 49. JOHNSON S., A new proof of the Erdos-Szekeres convex $k$-gon result, J. Combin. Theory Ser. A 42 (1986), 318-319. MR 87j:52004
  • 50. KALBFLEISCH J.D., KALBFLEISCH J.G., STANTON R.G., A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La, 1970. Congr. Numer. 1 (1970), 180-188. MR 42:8394
  • 51. KALBFLEISCH J.G., STANTON R.G., On the maximum number of coplanar points containing no convex $n$-gons, Utilitas Math. 47 (1995), 235-245. MR 96b:52016
  • 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. KATCHALSKI M., MEIR A., On empty triangles determined by points in the plane, Acta. Math. Hungar. 51 (1988), 323-328. MR 89f:52021
  • 56. KLEE V., WAGON S., Old and New Unsolved Problems in Plane Geometry and Number Theory, Mathematical Association of America, Dolciani Mathematical Expositions-No. 11, 1991. MR 92k:00014
  • 57. KLEITMAN D., PACHTER L., Finding convex sets among points in the plane, Discrete Comput. Geom. 19 (1998), 405-410. MR 99e:52021
  • 58. KORTE B., LOVÁSZ L., Shelling structures, convexity and a happy end, pp. 219-232. Graph Theory and Combinatorics (B. Bollobás, ed.), Academic Press, London, 1984. MR 86e:90091
  • 59. KORTE B., LOVÁSZ L., SCHRADER R., Greedoids, Springer-Verlag, Berlin, 1991. MR 93f:90003
  • 60. LEWIN M., A new proof of a theorem of Erdos and Szekeres, Math. Gaz. 60 (1976), 136-138. MR 58:10486
  • 61. LOVÁSZ L., Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979. MR 80m:05001
  • 62. MORRIS W.D., Convex dimension of locally planar convex geometries, Discrete Comput. Geom., to appear.
  • 63. MOTZKIN T.S., Cooperative classes of finite sets in one and more dimensions, J. Combin. Theory 3 (1967), 244-251. MR 35:5328
  • 64. MOTZKIN T.S., O'NEIL P.E., Bounds assuring subsets in convex position, J. Combin. Theory 3 (1967), 252-255. MR 35:5329
  • 65. NESETRIL J., VALTR P., A Ramsey-type theorem in the plane, Combin. Probab. Comput. 3 (1994), 127-135. Also in: Combinatorics, Geometry and Probability, pp. 525-533 (Cambridge, 1993), Cambridge University Press, Cambridge, 1997. MR 95e:05119
  • 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.
  • 68. PACH J., SOLYMOSI J., Canonical theorems for convex sets, Discrete Comput. Geom. 19 (1998), 427-435. MR 99a:52025
  • 69. PACH J., TOTH G., A generalization of the Erdos-Szekeres theorem for disjoint convex sets, Discrete Comput. Geom. 19 (1998), 437-445. MR 99b:52038
  • 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. RAMSEY F.P., On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264-286. Reprinted in: Classic Papers in Combinatorics (I. Gessel and G.-C. Rota, eds.), pp. 2-24. Birkhäuser, Basel, 1987. MR 88c:01055
  • 73. SCHECHTER B., My Brain Is Open, Simon & Schuster, New York, 1998. MR 99h:01038
  • 74. SCHMITT P., Problems in discrete and combinatorial geometry, pp. 449-483. Handbook of Convex Geometry, (P.M. Gruber and J.M. Wills, eds.), Elsevier Sci. Publ., 1993. MR 94h:52002
  • 75. SOLTAN V., Introduction to the Axiomatic Theory of Convexity, (Russian) Stiinta, Chisinau, 1984. MR 87h:52004
  • 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. SZEKERES G., A combinatorial problem in geometry, Reminiscences, pp. xix-xxii. Paul Erdos: The Art of Counting. Selected Writings (J. Spencer, ed.), MIT Press, Camgridge, MA, 1973. MR 58:27144
  • 79. TOTH G., Finding convex sets in convex position, Combinatorica, to appear.
  • 80. TOTH G., VALTR P., Note on the Erdos-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457-459. MR 99e:52022
  • 81. URABE M., On a partition into convex polygons, Discrete Appl. Math. 64 (1996), 179-191. MR 96m:52027
  • 82. VALTR P., Convex independent sets and 7-holes in restricted planar point sets, Discrete Comput. Geom. 7 (1992), 135-152. MR 93e:52037
  • 83. VALTR P., Sets in $IR^d$ with no large empty convex subsets, Discrete Math. 108 (1992), 115-124. MR 93i:52007
  • 84. VALTR P., On the minimum number of empty polygons in planar point sets, Studia Sci. Math. Hungar. 30 (1995), 155-163. MR 96e:52019
  • 85. VALTR P., Several Results Related to the Erdos-Szekeres Theorem, Doctoral Dissertation, Charles University, Prague, 1996.
  • 86. VALTR P., On mutually avoiding sets, The Mathematics of Paul Erdos, Vol. II, (R. L. Graham and J. Nesetril, eds.), Springer-Verlag, Berlin, 1997, 324-328. MR 98d:52025
  • 87. VAN DE VEL M.L.J., Theory of Convex Structures, North-Holland, Amsterdam, 1993. MR 95a:52002
  • 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.

Similar Articles

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

DOI: https://doi.org/10.1090/S0273-0979-00-00877-6
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

American Mathematical Society