Summary
LetP be a finite set of three or more noncollinear points in the plane. A line which contains two or more points ofP is called aconnecting line (determined byP), and we call a connecting lineordinary if it contains precisely two points ofP. Almost a century ago, Sylvester posed the disarmingly simple question:Must every set P determine at least one ordinary line? No solution was offered at that time and the problem seemed to have been forgotten. Forty years later it was independently rediscovered by Erdös, and solved by Gallai. In 1943 Erdös proposed the problem in the American Mathematical Monthly, still unaware that it had been asked fifty years earlier, and the following year Gallai's solution appeared in print. Since then there has appeared a substantial literature on the problem and its generalizations.
In this survey we review, in the first two sections, Sylvester's problem and its generalization to higher dimension. Then we gather results about the connecting lines, that is, the lines containing two or more of the points. Following this we look at the generalization to finite collections of sets of points. Finally, the points will be colored and the search will be for monochromatic connecting lines.
Similar content being viewed by others
References
Balomenos, R. H., Bonnice, W. E. andSilverman, R. J. 1966.Extensions of Sylvester's theorem. Canad. Math. Bull.9, 1–14. MR:33, # 6477.
Basterfield, J. G. andKelly, L. M. 1968.A characterization of sets of n points which determine n hyperplanes. Proc. Cambridge Philos. Soc.64, 585–588. MR:38, # 2040.
Baston, V. J. andBostock, F. A. 1978.A Gallai-type problem. J. Combin. Theory Ser. A24, 122–125. MR:57, # 150.
Beck, J. 1983.On a “lattice property” of the plane and some problems in combinatorial geometry. Combinatorica3, 281–297. Zbl 533.52004.
Bonnice, W. andEdelstein, M. 1967.Flats associated with finite sets in P d. Niew Arch. Wisk.15, 11–14. MR:35, # 7189.
Bonnice, W. andKelly, L. M. 1971.On the number of ordinary planes. J. Combin. Theory11, 45–53. MR:45, # 1784.
Boros, E., Füredi Z. andKelly, L. M. On representing Sylvester-Gallai designs. Discrete Comput. Geom.4, 345–348.
Borwein, J. 1979.Monochrome lines in the plane. Math. Mag.52, 41–45.
Borwein, J. 1980.Problems 297, 298. Canad. Math. Bull.23, 506.
Borwein, P. 1982.On monochrome lines and hyperplanes. J. Combin. Theory Ser. A33, 76–81.
Borwein, P. 1983a.On Sylvester's problem and Haar spaces. Pacific J. Math.109, 275–278.
Borwein, P. 1983b.The Desmic conjecture. J. Combin. Theory Ser. A35, 1–9.
Borwein, P. 1984.Sylvester's problem and Motzkin's theorem for countable and compact sets. Proc. Amer. Math. Soc.90, 580–584.
Borwein, P. andEdelstein, M. 1983.A conjecture related to Sylvester's problem. Amer. Math. Monthly90, 389–390.
Brakke, K. A. 1972.Some new values of Sylvester's function for n noncollinear points. J. Undergrad. Math.4, 11–14.
Bruijn, N. G. de andErdös, P. 1948.On a combinatorial problem. Neder. Akad. Wetensch. Proc.51, 1277–1279 (=Indagationes Math10, 421–423). MR:10, p. 424.
Burckhardt, J. J. 1940.Über konvexe Körper mit Mittlepunkt. Vierteljahrsschr. Naturforsch: Ges. Zürich85, 149–154.
Burr, S. A., Grünbaum, B. andSloane.N. J. A. 1974.The Orchard Problem. Geom. Dedicata2, 397–424. MR:49, # 2428.
Chakerian, G. D. 1970.Sylvester's problem on collinear points and a relative. Amer. Math. Monthly77, 164–167. MR:41, # 3305.
Coxeter, H. S. M. 1984.A problem of collinear points. Amer. Math. Monthly55, 26–28. MR:9, p. 458.
Coxeter, H. S. M. 1955.The Real Projective Plane (2nd ed.). Cambridge University Press, Cambridge. MR:10, p. 729.
Coxeter, H. S. M. 1968.Twelve Geometric Essays. Southern Illinois University Press, Carbondale, IL. MR:46, # 9843.
Coxeter, H. S. M. 1969.Introduction to Geometry (2nd ed.). Wiley, New York. MR:49, # 11369.
Coxeter, H. S. M. 1973.Regular Polytopes (3rd ed.). Dover, New York. MR:51, # 6554.
Croft, H. T. 1967.Incidence incidents. Eureka (Cambridge)30, 22–26.
Crowe, D. W. andMcKee, T. A. 1968.Sylvester's problem on collinear points. Math. Mag.41, 30–34. MR:38, # 3761.
Dirac, G. A. 1951.Collinearity properties of sets of points. Quart. J. Math.2, 221–227. MR:13, p. 270.
Dirac, G. A. 1959.Review of Kelly and Moser (1958). MR:20, # 3494.
Edelstein, M. 1957.A further generalization of a problem of Sylvester. Riveon Lamatematika11, 50–55. Hebrew. English summary. MR:21, # 2211.
Edelstein, M. 1969.Hyperplanes and lines associated with families of compact sets in locally convex spaces. Math. Scand.25, 25–30. MR:41, # 983.
Edelstein, M., Herzog, F. andKelly, L. M. 1963.A further theorem of the Sylvester type. Proc. Amer. Math. Soc.14, 359–363. MR:26, # 4333.
Edelstein, M. andKelly, L. M. 1966.Bisecants of finite collections of sets in linear spaces. Canad. J. Math.18, 375–380. MR:32, # 6185.
Edmonds, J., Lovász, andMandel, A. 1980.Solution to problem in vol. 1, p. 250. Math. Intelligencer2, 106–107.
Erdös, P. 1943.Problem 4065. Amer. Math. Monthly50, 65.
Erdös, P. 1944.Solution of Problem 4065. Amer. Math. Monthly51, 169–171.
Erdös, P. 1972.On a problem of Grünbaum. Canad. Math. Bull.15, 23–25. MR:47, # 5709.
Erdös, P., 1973.Problems and results in combinatorial analysis. (Technion Preprint Series No. MT-182). Technion, Haifa.
Erdös, P. 1975.On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. (4)103, 99–108. MR:54, # 113.
Erdös, P. 1980.Some combinatorial problems in geometry. Geometry and Differential Geometry (Proc. Conf. Univ. Haifa 1979), 46–53. (Lecture Notes in Math., Vol. 792). Springer, Berlin.
Erdös, P. 1982.Personal reminiscences and remarks on the mathematical work of Tibor Gallai. Combinatorica2, 207–212.
Erdös, P. 1983.Combinatorial problems in geometry. Math. Chronicle12, 35–54.
Erdös, P. 1984a.Some old and new problems on combinatorial geometry. Convexity and Graph Theory (Jerusalem, 1981), 129–136. (North-Holland Math. Studies, Vol. 87). MR:87b, # 52018.
Erdös, P. 1984b.Some old and new problems on combinatorial geometry. Annals Discrete Math.20, 129–136.
Erdös, P. 1984c.Research problems. Period Math. Hung.15, 101–103, Zbl 537.0515.
Erdös, P. 1985.Problems and results in combinatorial geometry. Discrete geometry and convexity (New York, 1982), 1–11. (Ann. New York Acad. Sci., Vol. 440). MR:87g, # 52001.
Erdös, P. andPurdy, G. 1976.Some extremal problems in geometry. IV. Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1976, 307–322. (Congressus Numerantium, Vol. XVII). Utilitas Math., Winnipeg, Man. MR:55, # 10292.
Gallai, T. 1944.Solution to Problem 4065. Amer. Math. Monthly51, 169–171.
Grünbaum, B. 1956.A generalization of a problem of Sylvester. Riveon Lematematika10, 46–48. (Hebrew. English summary) MR:19, p. 667.
Grünbaum, B. 1972.Arrangements and Spreads. (CBMS, No. 10). Amer. Math. Soc., Providence, RI. MR:46, # 6148.
Grünbaum, B. 1975.Arrangements of colored lines. Notices Amer. Math. Soc.22, A-200.
Grünbaum, B. 1976.New views on some old questions of combinatorial geometry. (Colloq. Int. Theorie Comb., Roma 1973, Tomo 1), 451–468. MR:57, # 10605. Zbl 347.52004.
Grünbaum, B. andShephard, G. C. 1984.Simplicial arrangements in projective 3-space. (Coxeter Festschrift) Mitt. Math. Sem. Giessen166, 49–101.
Guy, R. K. 1971.Problem 15. Unsolved combinatorial problems. Combinatorial Mathematics and its Applications (Proceedings Conf. Oxford 1969, Editor, D. J. A. Welsh), 121–127. Academic Press, London. MR:43, # 3126.
Hadwiger, H., Debrunner, H. andKlee, V. 1964.Combinatorial Geometry in the Plane. Holt, Rinehart and Winston, New York. MR:29, # 1577.
Hanani, H. 1951.On the number of straight lines determined by n points. Riveon Lematematika5, 10–11. MR:13, p. 5.
Hanani, H. 1954/5.On the number of lines and planes determined by d points. Technion Israel Tech. Sci. Publ.6, 58–63.
Hansen, S. 1965.A generalization of a theorem of Sylvester on the lines determined by a finite point set. Math. Scand.16, 175–180. MR:34, # 3411.
Hansen, S. 1980.On configurations in 3-space without elementary planes and on the number of ordinary planes. Math. Scand.47, 181–194. Zbl 438.51002.
Hansen, S. 1981.Contributions to the Sylvester—Gallai theory. Ph.D. Thesis. Copenhagen.
Herzog, F. andKelly, L. M. 1960.A generalization of the theorem of Sylvester. Proc. Amer. Math. Soc.11, 327–331. MR:22, # 4044.
Kárteszi, F. 1963.Alcuni problemi della geometria d'incindenza. (Conf. Sem. Math. Univ. Bari, No. 88). FM:31, # 3926.
Kelly, L. M. 1986.A resolution of the Sylvester—Gallai problem of J.-P. Serre. Discrete Comput. Geom.1, 101–104.
Kelly, L. M. andMoser, W. 1958.On the number of ordinary lines determined by n points. Canad. J. Math.10, 210–219. MR:20, # 3494.
Kelly, L. M. andRottenberg, R. 1972.Simple points on pseudoline arrangements. Pacific J. Math.40, 617–622. MR:46, # 6150.
Lang, G. D. W. 1955.The dual of a well-known theorem. Math. Gazette39, 314.
Melchior, E. 1940.Über Vielseite der projektiven Ebene. Deutsche Math.5, 461–475. MR:3, p. 13.
Meyer, W. 1974.On ordinary points in arrangements. Israel J. Math.17, 124–135. MR:52, # 148.
Moser, W. 1957.Abstract Groups and Geometrical Configurations. Ph.D. Thesis. Univ. of Toronto.
Moser, W. 1961.An enuneration of the five parallelohedra. Cand. Math. Bull.4, 45–47. MR24a, # 3556.
Motzkin, T. 1951.The lines and planes connecting the points of a finite set. Trans. Amer. Math. Soc.70, 451–464. MR:12, p. 849.
Motzkin, T. 1967.Nonmixed connecting lines. Abstract 67T–605. Notices Amer. Math. Soc.14, 837.
Motzkin, T. 1975.Sets for which no point lies on many connecting lines. J. Combinatorial TheoryA 18, 345–348. MR51, # 2946.
Rottenberg, R. 1971.On finite sets of points in P 3. Israel J. Math.10, 160–171. MR:45, # 5879.
Rottenberg, R. 1973.Exceptional sets in a projective plane. (Technion Preprint Series, No. MT-169). Technion, Haifa.
Rottenberg, R. 1981.Visibility and parallelotopes in projective space. J. Geometry16, 19–29. MR:83b, 51005. Zbl 473.51012.
Rottenberg, R. 1982.Singular points in planar finite sets I. Geometriae Dedicata12, 407–415. Zbl 492.05021.
Sah, Chih-Han. 1986.The rich line problem of P. Erdös. (Colloquia Math. Soc. János Bolyai, Vol. 48. Intuitive Geometry, Siófok, 1985), 123–125.
Salamon, P. andErdös, P. 1988.The solution to a problem of Grünbaum. Canad. Math. Bull.31, 129–138.
Shannon, R. 1974. Ph.D. Thesis. Univ. Washington, Seattle.
Steinberg, R. 1944.Three point collinearity. Amer. Math. Monthly51, 169–171.
Sylvester, J. J. 1893.Mathematical Question 11851. Educational Times59, 98.
Szemerédi, E. andTrotter Jr., W. T. 1983a.A combinatorial distinction between the Euclidean and projective plane. European J. Combin.4, 385–394. Zbl 539.05026.
Szemerédi, E. andTrotter Jr., W. T. 1983b.Recent progress on extremal problems in discrete geometry. (Graphs and other combinatorial topics, Prague 1982). (Teubner-Text zur Math. Vol. 59), 316–319. Teubner, Leipzig.
Szemerédi, E. andTrotter Jr., W. T. 1983c.Extremal problems in discrete geometry. Combinatorica3, 381–392. Zbl 541.05012.
Tingley, D. 1975.Monochromatic lines in the plane. Math. Mag.48, 271–274, MR:53, # 9115.
Williams, V. C. 1968.A proof of Sylvester's theorem on collinear points. Amer. Math Monthly.75, 980–982.
Watson, K. S. 1981.Sylvester's problem for spreads of curves. Canad. J. Math.32, 219–239, Zbl 436. 51010.
Woodall, D. R. 1969.The λ-μ problem. J. Lond. Math. Soc. (2)1, 509–519.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Borwein, P., Moser, W.O.J. A survey of Sylvester's problem and its generalizations. Aeq. Math. 40, 111–135 (1990). https://doi.org/10.1007/BF02112289
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02112289