A Discrete Geometrical Gem
4. Generalizations and adding color
There are many directions in which one can try to generalize the Sylvester-Gallai result. One direction is to understand the domain of plane geometries in which the result is true. Does the result hold in finite projective plane geometries? Does it hold in a stripped down version of Euclidean geometry where we give up some of the usual axioms of David Hilbert (1862-1943), whose axioms made the axiomatic system reported on in Euclid's Elements rigorous? In particular, to deal with Coxeter's concern that Kelly's proof uses a sledge hammer, Coxeter looked into proving Sylvester-Gallai in a geometry where the "extraneous" idea of distance is not present. One can also look at whether the result holds in a plane geometry where the points are coordinatized using complex numbers. An area of recent generalization for the Sylvester-Gallai Theorem is in studying what happens for circles rather than for lines. Rom Pinchashi recently (2002) proved a result of this kind, which was conjectured by A. Bezdek:
Given a finite family (with at least 5 members) of pairwise intersecting circles of the same radius, there is a point of intersection of the circles that lies on exactly two circles.
Results which involve circles of different radii are also being investigated. This whole area of research has intriguing connections to problems in computational geometry concerned with the "complexity" of the arrangements of various types of objects (e.g. lines, circles, hyperplanes).
Beyond generalizations that involve plane geometry, it is natural to try to extend the Sylvester-Gallai Theorem to higher dimensions. One approach to do this would be to consider sets of points in real 3-dimensional Euclidean space and ask: If all the points are not on a single plane, does there always have to be some plane passing through exactly 3 points? Generalizations to pseudolines and pseudoplanes also are of interest.
The problems that we have considered so far assume that the points we are dealing with look all alike, that is, they are one color. However, suppose that we have a point set with blue and red points. We can now consider situations where we investigate when we can find lines which have only two points (ordinary lines) where the two points are the same color or the two points are different colors. Intriguingly, the problem of monochromatic lines was considered some time ago. Perhaps this grew out of the interest in Ramsey Theory in combinatorics and graph theory, where finding a "monochromatic" substructure in some larger structure was the goal of the investigation.
In this connection, an interesting generalization of Sylvester's problem was given by Theodore Motzkin (1908-1970) in response to a question posed by Ronald Graham.
Motzkin showed (with a very nice argument) that if one has two finite sets X and Y in the plane which have no points in common, the points in X or Y all lie on a line or there exist two points of one of these sets that determine a line that does not intersect the other set. Sometimes the condition that points do not all lie on a single line is stated as the points in X or Y "span" the plane. If we think of the points of X as being red and those of Y being blue, we can interpret this theorem as saying that if we have two finite sets of points which are of different colors, then if the points do not all lie on a line, there is a monochromatic line of one of the two colors.
A recent tantalizing problem related to the Sylvester-Gallai result and involving colored point sets was suggested by I. da Silva and K. Fukuda. They suggested conditions under which a set of points which come in two colors would have a line with exactly two points from the set, one of each color. Suppose one has a collection of points P in the plane not all on a single line. Furthermore suppose there exists a line m with the property that m contains no point of P but m separates the points of P into two half spaces which differ in size by at most one. Then there exists a line m* such that m* has exactly two points of P on it, one from each of the half planes determined by m. If we color all of the points in one of the half planes with one color, and all of the points in the other half plane with a different color, we can interpret the conclusion of this conjecture as being that a "bichromatic line" with exactly two points, one point with each of two colors, exists.
Inspired by this conjecture, Janos Pach and Rom Pinchasi proved some results related to bichromatic lines and showed that if the da Silva-Fukuda conjecture is true, then all the hypotheses of the conjecture must be present. However, recently, as a byproduct of work in enumerating inequivalent configurations of finite sets of points, the da Silva-Fukuda conjecture has been shown not to hold.
L. Finschi and K. Fukuda, using ideas about oriented matroids, set themselves the task of counting the number of inequivalent point configurations and hyperplane arrangements in a fixed dimension. In particular, they worked on point configurations in the plane and line arrangements in the plane. For example, it grew out of their work that there are 461,053 "different" oriented matroids with 9 elements in dimension 2. This allowed them to show there are 158,830 "non-degenerate" plane point configurations with 9 points, where inequivalence is defined in terms of "abstract order type," order type being defined in terms of the orientation of triples of points. Once this enumeration, and more importantly, database of examples of all the different configurations was obtained, Finschi and Fukuda used the database to check whether or not the da Silva-Fukoda conjecture was true for plane point sets with not too many elements. They verified that the conjecture did hold for point sets with 8 or fewer points, but showed that there was exactly one configuration for 9 points for which the conjecture failed. To accomplish this required examining the 15,296,266 possibly degenerate 9 point order types, locating one potential counterexample among them, and then actually producing the coordinates for 9 points in the plane that realized the "abstract" configuration physically. The diagram below shows the spirit (but not the exact placement) of the points in Finschi-Fukuda's counterexample:
The line AB and AC are bichromatic lines if the points to the left of the red line are colored one color and the point to the right of it are colored with a second color! (Finschi and Fukuda give the following coordinates for the points in this configuration, (1, 1), (1/2, 0), (1/, -1 + 2), (1/3, -1/3), (3/2 - /2, 0), (1/, 1 - 2/), (0, 0), (1/, 1/), (1, -1). It is a nice exercise to verify that the points (1, -1), (1/, -1 + 2/), and (3/2 - /2, 0) really do lie on a straight line.) In light of the fact that out of so many point configurations which might provide a counterexample for 9 points, there is a unique counterexample, it is tempting to ask if the daSilva-Fukuda conjecture might be true for sufficiently large point sets. After all, the long-standing conjecture that there are n/2 ordinary lines also fails for two small point sets, but no counterexample has been located for large values of n. Attempting to find a counterexample with an even number of points to the conjecture might also be attempted.
The Sylvester problem provides a classic example of a simple-to-state puzzle which continues to tantalize those seeing it for the first time, because it is a nut that is not easy to crack, and at the same time, for experienced researchers it offers new vistas for expanding geometry in many different directions.
-
Introduction
-
Planar point configurations
-
Some ramifications of the Sylvester-Gallai Theorem
-
Generalizations and adding color
-
References