Feature Column from the AMS

Oriented Matroids: The Power of Unification

4. Arrangements of pseudolines

The concept of a pseudoline is a natural generalization of the concept of a straight line. If one thinks of a line as a thin piece of (uncooked) spaghetti, think of a pseudoline as a cooked piece of spaghetti. Pseudolines are "floppy" lines, it being understood that they intersect only once, as would straight lines. Here is an example of an arrangement of pseudolines. An arrangement of pseudolines will be a collection of pseudolines where each pair of pseudolines intersects exactly once. (The obvious extension of the pseudoline "to infinity" is understood but with care being taken that no further intersections occur among the pseudolines other than those indicated in the "finite part" of the diagram.)

Figure 2

Like many ideas in mathematics the first investigation of pseudolines was done much earlier than a "sustained" effort to understand them could be carried out. Thus, in 1926 F. W. Levi (1888-1966) used the word pseudoline (in German) in what appears to be the first paper devoted to this subject.

(This photograph is used with the kind permission of H. Begehr, (and assistance of Sven Guckes) and appears in H. Begehr (Ed.): Mathematik in Berlin, Geschichte und Dokumentation, Erster Halbband. Shaker Verlag, Aachen, 1998, p. 332, and was provided by Hochschularchiv Freie Universitaet Berlin, Math.-Nat. Fak., Dekanat, Photosammlung).

Levi proved a remarkable result which is now known as the Levi Enlargement Lemma. What this result says is that if one has a planar arrangement of pseudolines and one picks two points P and Q which are not both on the same pseudoline (these points can be on pseudolines or not), then it is possible to create a new pseudoline that passes through P and Q and creates a new arrangement of pseudolines which has one more pseudoline. (Levi had a complex career due to the fact that he was forced to give up a position in Leipzig by the Nazis. He spent the years of the war in India, where he had positions in Calcutta and the Tata Institute. He did early work on finite geometries and in the development of the theory of combinatorial designs, but returned to a position at the Free University in Berlin after the war. He also did important work in the theory of groups.)

If one picks out a pseudoline one can try to "stretch" it so that it does not change the cell structure into which the pseudolines divide the plane, but straightens out the pseudoline until it becomes a straight line. An arrangement of pseudolines is called stretchable if all the pseudolines in the arrangement can be made into straight lines in such a way that at each stage of the transformation, the combinatorial type (as indicated by the faces that are formed) of the pseudolines is maintained. What is your intuition? Do you think that all pseudoline arrangements arestretchable into an arrangement of the same type with lines? The German mathematician Gerhart Ringel conjecturedthat a specific arrangement of pseudolines could not be transformed by "stretching" intoa collection of straight lines. Eventually he was proven right.

The key to the fact that not all arrangements of pseudolines are stretchable is that there are theorems that guarantee that points constructed from the intersections of certain points and lines must be collinear. Two of the most famous of such theorems are Pappus' Theorem and Desargues' Theorem. These theorems are most naturally stated in projective geometry (where there are no parallel lines), because to state them in Euclidean geometry one must rule out that certain lines become parallel for the conclusions involved to hold.

Here is a diagram to illustrate Pappus' Theorem.

The most natural approach to Pappus' Theorem involves conic sections but here I consider a special case, where we have two lines which are shown parallel but could be intersecting. There are three points on each line: a, b, c on one, and A, B, C on the other. Join a to B and C; b to A and C; c to A and B. Pappus' Theorem states that the lines aB and aC, bA and bC, cA and CB intersect at points, respectively, p, q, and r which are collinear. Thus, in our picture, p, q, and r are collinear. Put somewhat differently, the points p, q, and r, which by their definition might not seem forced to be on a line, in fact, must be on a line.

Using Pappus' Theorem we can design an arrangement of pseudolines (as Ringel did) that can not be stretched to an arrangement of lines.

A non-stretchable arrangement of pseudolines based on the Pappus configuration

The eight black pseudolines are straight lines (think of the two pseudolines which look parallel as meeting far in the distance) and there is one red pseudoline which meets all the others.

Another subtle aspect of straightening pseudolines is that a diagram that looks as if it consists of straight lines can sometimes be proven not to exist as lines. The pseudolines that one sees deviate from being actually straight in such a "small" way that the eye is unable to discern that they are not really straight lines, but are either slightly curved or are the union of segments which meet almost but not exactly at 180º! All of the questions that were raised above about lines can also be asked about pseudolines, together with some new questions that grow out of their own special nature.

For an unexpected appearance of pseudolines, consider the polygon below where the opposite sides of the polygon are equal in length and parallel. In fact, the polygon here is regular, that is, all of its sides have equal length and the angles between pairs of sides of the polygon are all the same. The polygon has been chopped up into cells using its vertices and additional interior vertices so that the resulting polygons are all parallelograms. Since we started with a regular polygon, in this case the result is a tiling of the original polygon by rhombuses.

Where do the pseudolines come in?

An arrangement of pseudolines obtained from a tiled octagon

The diagram above shows how the octagonal polygon and a tiling of it gives rise to 4 pseudolines! This ingenious idea allows one to unify ideas about tilings and the enumeration of tilings with ideas about arrangements of lines and pseudolines. Mathematics can make a big leap forward when such an unexpected unification of ideas occurs.