Bulletin of the American Mathematical Society

Author(s): W. Morris; V. Soltan
Journal: Bull. Amer. Math. Soc. 37 (2000), 437-458.
MSC (2000): Primary 52C10
Posted: June 26, 2000
Retrieve article in: PDF

In 1935 Erdos and Szekeres proved that for any integer $n \ge 3$ there exists a smallest positive integer

such that any set of at least

points in general position in the plane contains

points that are the vertices of a convex

-gon. They also posed the problem to determine the value of

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.

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 -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 -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 -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 -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 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 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.

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 52C10

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: 10.1090/S0273-0979-00-00877-6
PII: S 0273-0979(00)00877-6
Keywords: Erdos-Szekeres problem, Ramsey theory, convex polygons and polyhedra, generalized convexity
Received by editor(s): December 20, 1999, and in revised form April 4, 2000
Posted: June 26, 2000
Copyright of article: Copyright 2000, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS