Extremal Problems Related to the Sylvester—Gallai Theorem
Niranjan Nilakantan · 2005
We discuss certain extremal problems in combinatorial geometry, including Sylvester's problem and its generalizations. 1. Introduction Many interesting problems in combinatorial geometry have remained unsolved or only partially solved for a long time. From time to time breakthroughs are made. In this survey, we shall discuss the known results about some metric and nonmetric problems. In particular, we shall discuss the Sylvester-Gallai problem and the Dirac-Motzkin conjecture on the existence and number of ordinary lines, the Dirac conjecture on the number of connecting lines, and the problem of distinct and repeated distances. The main focus will be on versions of these problems in the Euclidean and real projective plane. The method of allowable sequences will be described as a tool to give purely combinatorial solutions to extremal problems in combinatorial geometry. 2. Sylvester's Problem Sylvester [1893] posed a question in the Educational Times that was to remain unsolved for 40 years until it was raised again by Erdos [1943]. Then it was soon solved by Gallai [1944], who gave an affine proof. More followed: Steinberg's proof in the projective plane and others by Buck, Grünwald and Steenrod, all collected in [Steinberg et al. 1944]; Kelly's Euclidean proof [1948], and others, including [Motzkin 1951; Lang 1955; Williams 1968]. We give the following definitions before we state the problem and its solutions. Let P be a finite set of 3 or more noncollinear points in the plane. Let F be a finite collection of simple closed curves in the real projective plane which do not separate the plane, every two of which have exactly one point in common, where they cross. F is known as a pseudoline arrangement