Radon’s theorem is a neat result in discrete geometry which makes use of elementary linear algebra to find disjoint subsets and of a sufficiently large set such that the convex hulls of and have nonempty intersection. If is a set with at least points, then we can label some of the points red (those that belong to the set ) and some of the points blue (those that belong to the set ) such that there exists a point in which can be written as a convex combination of red points and also as a convex combination of blue points.
Before we get to the details, some quick remarks on notation. I will use the notation or to denote the convex hull of points or a set . Also, if are points in an affine space, we denote the line segment between and by .
Theorem (Radon) Let be a subset containing at least elements. Then there exist disjoint subsets and such that
Proof. Let be distinct points in , where . We introduce real variables , regard as column vectors, and consider the matrix equation
Since , there does not exist an injection of into , which implies that there exists a nontrivial solution to the matrix equation. We abuse notation and denote this solution by the coordinates . Define disjoint subsets and
I claim that . Since and all the are zero, we see that and . Since , we see that
But we have shown that can be written as a convex combination of points in and also as a convex combination of points in , and therefore .
I claim that the constant cannot be improved to in Radon’s theorem. Fix , and consider the set consisting of the origin and the standard basis elements of . has points. Suppose and are disjoint nonempty subsets of with intersecting convex hulls. Since , we see that
which implies that .
To add some concreteness to our discussion of Radon’s theorem, we consider the case . Suppose we have a set consisting of 4 points in the plane. Radon’s theorem tells us that there exist nonempty disjoint subsets and such that . If consists of a single point (w.l.o.g.) . Then lies in the interior of the triangle formed by . If consists of two points (w.l.o.g.) , then we have that the line segments and intersect at precisely one point.