CHAPTER 1 Sylvester–Gallai Problem: The Beginnings of Combinatorial Geometry 1. James Joseph Sylvester and the Beginnings James Joseph Sylvester (1814–1897) was one of the most colorful figures of nineteenth century British mathematics. He started his studies at the University of London at the age of 14, where he was a student of the logician, Augustus de Morgan. In spite of his brilliant achievements in Cambridge, he was not granted a degree there until 1872, because as a Jew, he declined to take the Thirty-Nine Articles of the Church of England. In 1838, however, he became Professor of Nat- ural Philosophy at University College London, but he could not obtain a teaching position until 1855. In 1841, he was awarded a BA and an MA by Trinity College Dublin. While working in London as an actuary, together with his lifelong friend, Arthur Cayley, he made important contributions to matrix theory and invariant theory. In 1877, Sylvester became the inaugural professor of mathematics at the new Johns Hopkins University, and one year later he founded the American Journal of Mathematics. He did pioneering work in combinatorics, in number theory, and in the theory of partitions. “The early study of Euclid made me a hater of geometry,” said Sylvester [521]. It is somewhat ironic that most likely the hatred would not be mutual! The follow- ing innocent looking question of Sylvester was first proposed as a problem in the Educational Times [708]. Euclid would have probably loved this question, because to formulate it we need only three notions: points, lines, and incidences, the three basic elements of his geometry! Is it true that any finite set of points in the Eu- clidean plane, not all on a line, has two elements whose connecting line does not pass through a third? Such a connecting line is called an ordinary line. In the same year, the journal published an incorrect solution by Woodall and another argument, which was characterized as “equally incomplete, but may be worth notice.” In the early 1930s, the question was rediscovered by Erd˝ os, and shortly thereafter, an aﬃrmative answer was given by T. Gr¨ unwald (alias Gallai). In 1943, Erd˝ os [325] posed the problem in the American Mathematical Monthly. In the following year, it was solved by Steinberg [337] and others. However, the oldest published proof is due to Melchior [547], who established the dual statement, as a corollary to a more general inequality: any finite family of lines in the plane, not all of which pass through the same point, determines a simple intersection point, i.e., a point that belongs to precisely two lines. Both the primal and dual forms of the result have become known as the Sylvester–Gallai theorem. Many alternative proofs and generalizations have been found by de Bruijn and Erd˝ os [184], Coxeter [253], Motzkin [557], Lang [505], Williams [749], Lin [515], Edelstein et al. [312, 311], Borwein [164, 165], Giering [378], Herzog and Kelly [441], Kupitz [502], Watson 1 http://dx.doi.org/10.1090/surv/152/01

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.