Sylvester–Gallai theorem

It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

Another way of stating the theorem is that every finite set of points that is not collinear has an ordinary line.

[1] H. J. Woodall (1893a, 1893b) claimed to have a short proof of the Sylvester–Gallai theorem, but it was already noted to be incomplete at the time of publication.

Eberhard Melchior (1941) proved the theorem (and actually a slightly stronger result) in an equivalent formulation, its projective dual.

Unaware of Melchior's proof,[2] Paul Erdős (1943) again stated the conjecture, which was subsequently proved by Tibor Gallai, and soon afterwards by other authors.

Gallai's 1944 proof switches back and forth between Euclidean and projective geometry, in order to transform the points into an equivalent configuration in which an ordinary line can be found as a line of slope closest to zero; for details, see Borwein & Moser (1990).

The 1941 proof by Melchior uses projective duality to convert the problem into an equivalent question about arrangements of lines, which can be answered using Euler's polyhedral formula.

Another proof by Leroy Milton Kelly shows by contradiction that the connecting line with the smallest nonzero distance to another point must be ordinary.

And, following an earlier proof by Steinberg, H. S. M. Coxeter showed that the metric concepts of slope and distance appearing in Gallai's and Kelly's proofs are unnecessarily powerful, instead proving the theorem using only the axioms of ordered geometry.

[7] In 1941 (thus, prior to Erdős publishing the question and Gallai's subsequent proof) Melchior showed that any nontrivial finite arrangement of lines in the projective plane has at least three ordinary points.

By duality, this results also says that any finite nontrivial set of points on the plane has at least three ordinary lines.

[8] Melchior observed that, for any graph embedded in the real projective plane, the formula

But if every vertex in the arrangement were the crossing point of three or more lines, then the total number of edges would be at least

Then[8] or equivalently, H. S. M. Coxeter (1948, 1969) writes of Kelly's proof that its use of Euclidean distance is unnecessarily powerful, "like using a sledge hammer to crack an almond".

[11] The problem of finding a minimal set of axioms needed to prove the theorem belongs to reverse mathematics; see Pambuccian (2009) for a study of this question.

The usual statement of the Sylvester–Gallai theorem is not valid in constructive analysis, as it implies the lesser limited principle of omniscience, a weakened form of the law of excluded middle that is rejected as an axiom of constructive mathematics.

, was given earlier by Edelsbrunner & Guibas (1989), as a subroutine for finding the minimum-area triangle determined by three of a given set of points.

The same paper of Edelsbrunner & Guibas (1989) also shows how to construct the dual arrangement of lines to the given points (as used in Melchior and Steenrod's proof) in the same time,

Mukhopadhyay, Agrawal & Hosabettu (1997) first showed how to find a single ordinary line (not necessarily the one from Kelly's proof) in time

The algorithm of Mukhopadhyay & Greene (2012) is based on Coxeter's proof using ordered geometry.

It performs the following steps: As the authors prove, the line returned by this algorithm must be ordinary.

The construction, due to Károly Böröczky, that achieves this bound consists of the vertices of a regular

One example, by Kelly & Moser (1958), consists of the vertices, edge midpoints, and centroid of an equilateral triangle; these seven points determine only three ordinary lines.

[17] Ben Green and Terence Tao showed that for all sufficiently large point sets (that is,

A variation of Sylvester's problem, posed in the mid-1960s by Ronald Graham and popularized by Donald J. Newman, considers finite planar sets of points (not all in a line) that are given two colors, and asks whether every such set has a line through two or more points that are all the same color.

Another way of stating the Sylvester–Gallai theorem is that whenever the points of a Sylvester–Gallai configuration are embedded into a Euclidean space, preserving colinearities, the points must all lie on a single line, and the example of the Hesse configuration shows that this is false for the complex projective plane.

[21] Similarly, Elkies, Pretorius & Swanepoel (2006) showed that whenever a Sylvester–Gallai configuration is embedded into a space defined over the quaternions, its points must lie in a three-dimensional subspace.

Every set of points in the Euclidean plane, and the lines connecting them, may be abstracted as the elements and flats of a rank-3 oriented matroid.

Relatedly, the Kelly–Moser configuration with seven points and only three ordinary lines forms one of the forbidden minors for GF(4)-representable matroids.

[15] Another generalization of the Sylvester–Gallai theorem to arbitrary metric spaces was conjectured by Chvátal (2004) and proved by Chen (2006).

Three of the ordinary lines in a 4 × 4 grid of points
The elongated dodecahedron , a zonohedron . Its eight red parallelogram faces correspond to ordinary points of a five-line arrangement; an equivalent form of the Sylvester–Gallai theorem states that every zonohedron has at least one parallelogram face.
Two lines, six points on them, and two perpendicular segments from a point on one line to a point on the other, labeled as described in Kelly's proof
Notation for Kelly's proof
The two known examples of point sets with fewer than ordinary lines.
Example of Böröczky's (even) configuration with 10 points determining 5 ordinary lines (the five solid black lines of the figure).
A 3 by 3 grid of points, with 8 straight lines through triples of points and four more curves through triples of points on the broken diagonals of the grid
The Hesse configuration , in which the line through every pair of points contains a third point. The Sylvester–Gallai theorem shows that it cannot be realized by straight lines in the Euclidean plane, but it has a realization in the complex projective plane .