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

Avis D., Rappaport D.

Proc. First ACM Symp. Comput. Geom. Baltimore,

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

Carathéodory C.

Rend. Circ. Mat. Palermo

32

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

Dumitrescu A.

Studia Sci. Math. Hungar.

36

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

Hoffman P.

The Man Who Loved Only Numbers

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

Hosono K., Urabe M.

Comput. Geom. Theory and Applications,

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

Károlyi G.

Discr. Appl. Math.,

Károlyi G., Pach J., Tóth G.

Károlyi G., Valtr P.

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

Morris W.D.

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

Nielsen M.J.

Overmars M., Scholten B., Vincent I.

Bull. European Assoc. Theor. Comput. Sci.

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

Pach J., Tóth G.

Geometriae Dedicata

Purdy G.B.

AMS Abstracts

3

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

Solymosi J.

Combinatorial Problems in Finite Ramsey Theory

Steinitz E.

J. Reine Angew. Math.

143

144

146

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

Tóth G.

Combinatorica

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

Valtr P.

Several Results Related to the Erdős–Szekeres Theorem

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

Watson F.R.

Math. Gaz.

53

Watson F.R.

Math. Spectrum

2