Disjoint Simplices and Geometric Hypergraphs

Let A be a set of 2n points in general position in the Euclidean plane R2, and suppose n of the points are colored red and the remaining n are colored blue. A celebrated Putnam problem (see [6] ) asserts that there are n pairwise disjoint straight line segments matching the red points to the blue points. To show this, consider the set of all n! possible matchings and choose one, M , that minimizes the sum of lengths I(M) of its line segments. It is easy to show that these line segments cannot intersect. Indeed, if the two segments v, , b , and v2 , b, intersect, where v, , v2 are two red points and b,, b, are two blue points, the matching M' obtained from M by replacing q b , and v ,b , by v,b2 and u2 b, satisfies I(M') < I(M), contradicting the choice of M . Our first result in this paper is a generalization of this result to higher dimensions.