Continuing my recent sequence of posts of half-baked doodles in combinatorial geometry...

In one of the earlier posts in this sequence, I defined the "Radon exchange graph" of a set of \( k + d + 2 \) points in general position in \( d \)-dimensional Euclidean space to be a graph that has as its vertices the Radon partitions of \( (d + 2) \)-tuples of points (partitions of the points into two subsets with intersecting convex hulls), and with edges connecting pairs of partitions that differ by the addition of one point and the removal of one other point. I observed that this graph is \( 2k \)-regular, and that when \( k = 1 \) it seems to always form a cycle.

Now what other graphs do we know of that are \( 2k \)-regular and have one vertex per \( (d + 2) \)-tuple (or equivalently, per \( k \)-tuple) among a set of \( k + d + 2 \) items? That's right: the graphs of arrangements of \( k + d + 2 \) hyperplanes in general position in \( k \)-dimensional projective space. And that's exactly what the Radon exchange graph turns out to be: it's always the graph of a hyperplane arrangement. For instance, the Radon exchange graph for five points \( a \)–\( b \)–\( c \)–\( d \)–\( e \) on a line is the graph of an arrangement of five lines in the projective plane:

The Radon exchange graph of five points as the graph of an arrangement of five lines

Being in the projective plane means that we should interpret each line as wrapping around "to infinity and beyond" to connect the vertices on the far ends of the line to each other. Each line in this instance is formed by the four Radon partitions that do not involve some particular one of the five given points.

To see that every Radon exchange graph is a hyperplane arrangement graph, suppose we have a set \( P \) of \( k + d + 2 \) points \( p_i \) in general position in \( d \)-space. As in the usual proof of Radon's theorem, consider the system of linear equations \( \sum a_i p_i = 0 \), \( \sum a_i = 0 \). There are \( d + 1 \) equations in \( k + d + 2 \) unknowns, so we can choose some \( k + 1 \) linearly independent solutions to these equations. Use these chosen solution values as the Cartesian coordinates of a set \( Q \) of \( k + d + 2 \) points \( q_i \) in \( (k + 1) \)-dimensional space. The \( k + 1 \) coordinates of the \( i \)th point are just the \( k + 1 \) different values of the coefficient \( a_i \) in each of these chosen \( k + 1 \) independent solutions. Although different choices of independent solutions will lead to different point sets, they are all equivalent up to linear transformations of \( (k + 1) \)-dimensional space.

Suppose that we wish to find the Radon partition for some \( (d + 2) \)-tuple of our original points. To do so, we solve a system of linear equations like the ones above and partition the points according to the signs of their coefficients. But eliminating the unpicked points so that only the \( (d + 2) \)-tuple remains is the same as forcing the coefficients for the other \( k \) points to be zero. And this can be done by letting \( H \) be the hyperplane \( H \) through the origin and the missing \( k \) points, projecting \( Q \) onto a line perpendicular to \( H \), and using the projected position of \( q_i \) as the coefficient \( a_i \). The partition of the coefficients \( a_i \) by their signs is the same as the partition of \( Q \) by which side of \( H \) each point is on. So Radon partitions of \( (d + 2) \)-tuples of \( P \) correspond one-for-one with the partitions of \( Q \) formed by hyperplanes through \( k \)-tuples of points and the origin.

Now, in order to understand the combinatorics of these hyperplane partitions of \( Q \), the distance of each point from the origin is completely irrelevant: if we move a point \( q_i \) inwards or outwards on the ray from the origin through \( q_i \), we would get the same partition. And even if we moved a point \( q_i \) to the other side of the origin along the same line, that would change all the hyperplane partitions of \( Q \) in a predictable way: in every partition, such a move would cause \( q_i \) to change from one side of the partition to the other. So we might as well treat all points on a line through the origin as being equivalent, and this equivalence is exactly the standard one used to reduce \( (k + 1) \)-dimensional affine space (and hyperplanes through the origin) to \( k \)-dimensional projective space (and arbitrary hyperplanes). In \( k \)-dimensional projective space, the family of partitions of a point set by a hyperplane through \( k \) of the points corresponds one-for-one (by projective duality) to the family of vertices of a hyperplane arrangement, and two dual arrangement vertices are adjacent if and only if one can move from one primal partition to another by adding and removing one point.

So there's the correspondence: given point set \( P \), solve a system of linear equations to get a new set of points \( Q \) in a \( (k + 1) \)-dimensional space, project down to \( k \)-dimensional projective space, and take the projective-dual hyperplane arrangement. The vertices and edges of this arrangement are in one-to-one correspondence with the vertices and edges of the Radon exchange graph of \( P \). This shows, in particular, that the Radon exchange graph for \( k = 1 \) is always a cycle, because a cycle is the only possible arrangement of hyperplanes in a one-dimensional projective space. It also shows that the signed Radon exchange graph (a related construct in which we interpret \( ab/cde \) as being a different partition from its swap \( cde/ab \)) is a polyhedral graph, the graph of the polar polytope of a zonotope.

Probably there's some connection to Gale transforms if only I understood those better than I do.