The Radon exchange graph

The Radon exchange graph: "Radon's theorem states that, for a set of d + 2 points in general position in d-dimensional space there is a (unique) partition of the set into two subsets whose convex hulls intersect in a point. Here general position means no d + 1 of the points lie on a common hyperplane. For instance, if the four points p, q, r, and s in the plane form a convex quadrilateral pqrs, then in the partition ps/rq the two line segments ps and rq (the diagonals of the quadrilateral) cross each other, while if point p lies inside triangle qrs then the partition p/qrs works, and has p as the point of intersection of the two hulls.

Now suppose that we have n ≥ d + 2 points, still in general position. Each (d + 2)-tuple of the points defines a Radon partition. Define two of these partitions A/B and C/D to be adjacent if they differ by the removal of one point from A or B, and the addition of a different point to the corresponding set C or D. This forms a 2(n − d − 2)-regular graph that has as its vertices all possible (d + 2)-tuples and as its edges the adjacencies.

Why is this graph regular? Because, if A/B is any Radon partition of some d + 2 points of the set, and x is any point outside that (d + 2)-tuple, then there is a unique Radon partition formed by adding x to A and removing some other point from A or B, and there is another unique Radon partition formed by adding x to B and removing some other point from A or B. If A has fewer than d + 1 points, then the convex hulls of A+x and B intersect in a line segment; the Radon partition A/B has one endpoint of this line segment as its intersection point and the other endpoint is the intersection point of an adjacent partition. If, on the other hand, A has exactly d + 1 points, then A+x takes the form of a simplex divided into d + 1 smaller simplices; in this case, the outer simplex and exactly one of the inner simplices contain the sole point of B, and these two simplices form (with B) two adjacent partitions.

We can use this Radon exchange graph to prove a higher-dimensional relative of the Happy Ending problem first proven (using a different technique, Gale diagrams) by Micha Perles: for every set of d + 3 points in general position there is a subset of d + 2 that form the vertices of a neighborly polytope. A neighborly polytope is a polytope such that the convex hull of every subset of d/2 or fewer vertices forms a face; for instance, in four dimensions, every pair of vertices must form an edge. Perles' proof works for all dimensions (or at least, Grünbaum's book Convex Polytopes, where it appears as an exercise on p.120, doesn't say anything about it not working in all dimensions), whereas the proof below using the Radon exchange graph works only for even dimensions. However, it proves a slightly stronger result, that there are an odd number of ways of choosing d + 2 vertices to form a neighborly polytope.

Define a Radon partition to be k-unbalanced (for k < d/2 + 1) if one side of the partition has k or fewer points. Then, in the Radon exchange graph for any set of d + 3 points, the k-unbalanced partitions have a perfect matching. The proof is by induction on k: suppose by induction that the (k − 1)-unbalanced partitions are already perfectly matched, consider the partitions A/B where |A|=k, and for each such partition consider the edge to the adjacent partition formed by adding the missing point x to B and removing a point. The edges where the removed point comes from B form a matching among some of these partitions; but when the removed point comes from A, these edges go to the already-matched (k − 1)-unbalanced partitions. Each path in the Radon exchange graph formed by these already-matched partitions must have exactly two edges connecting it to the rest of the graph, both of which are among the set of edges being considered. By replacing alternating edges along each such path, we get a matching of all the k-unbalanced partitions.

The parity version of Perles' problem follows immediately: in any dimension d, and for any set of d + 3 points, the number of unbalanced partitions (for all choices of k) is even, and the total number of partitions is exactly d + 3, so the number of balanced partitions has the opposite parity from d. And in even dimensions a set of d + 2 points forms a neighborly polytope if and only if its Radon partition is balanced, so for even dimensions there is an odd number of ways of forming a neighborly polytope.

In all the examples I calculated, the Radon exchange graphs for sets of d + 3 points always took the form of a single (d + 3)-vertex cycle. But I don't know whether that's always true, or whether I just haven't looked at sufficiently many examples. If it is always a cycle, then these cycles could be used to define 2-faces of a higher-dimensional Radon exchange complex..."