Oriented Matroids: The Power of Unification
5. Allowable sequences
Here is another configuration of 5 labeled points:
Are these two configurations of points the same or different?
If we take the point configuration above and project (using the red lines) its labeled vertices onto the blue line L, we obtain points in the order 13452. As we rotate the line L into other positions in a counterclockwise direction, we reach a location where there is a pair of points in the original configuration which for the first time determine a line whose direction is perpendicular to the rotating line. If we rotate just a bit further (to the green line L') and project the points onto this line, the order of the points 1 and 3 will reverse and we obtain the permutation 31452. Rotating further for the above configuration and making switches as they are encountered, we get the new permutation 34152, and then 34512, 54321 (note for this position we get two switches of numbers simultaneously because there are two parallel lines in the configuration), 54231, 52431, and 25431. At this point we have rotated the original line through 180 degrees. The permutation is exactly the reverse of what it was originally. We can now continue our rotation until we get back to the original position for the rotating line, and arrive at the original permutation 31452. Notice that we can code the way one obtains the next permutation in the sequence by the "section(s)" of the previous permutation that must be flipped to obtain the next permutation. The sequence of permutations that is obtained from the point configuration in this way is called an allowable sequence by Goodman and Pollack. What has been accomplished is to capture information about the point configuration in terms of "algebra." A collection of permutations on the symbols 1,..., n, starting and ending with the same permutation, is called allowable if:
However, what happens at the other extreme? How few directions can be determined by planar configurations of points (not all on a line)? The rectangular configuration of points below determines only 4 different directions:
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance