So, I’ve written now on Radon’s theorem and Carathéodory’s theorem, but I have yet to complete the trifecta of results in combinatorial geometry; I have yet to say anything about Helly’s theorem. Helly’s theorem says that if we have a finite collection of convex sets in with the property that every subcollection of sets has nonempty intersection, then the entire collection has nonempty intersection. More precisely:
Theorem 1. (Helly) Let , where , be a finite collection of convex sets in . If, for every sets ,
We will prove Helly’s theorem using Radon’s theorem and in fact, the theorems of Helly, Radon, and Carathéodory are equivalent. I neither know the proof of this equivalence nor have a reference for a proof at hand, but I will try to find one–please drop me a comment if you have a reference! Before we prove Helly’s theorem, I want to make a couple observations on the necessity of the hypotheses.
The theorem is false if we drop the hypothesis that the are convex. Indeed, let , and let be a collection of distinct points in . For each , define the nonconvex set
Clearly, , but for any sets , the intersection consists of the point .
The theorem is also false if we relax the hypothesis to every collection of subsets has nonempty intersection. Let , and consider the collection of closed balls and open ball of radius centered at , and , respectively. It is clear that any two balls intersect nontrivially, but the intersection of all three must be empty since . Here’s a picture:
Proof of Theorem 1. We proceed by induction on . In the base case , there is nothing to prove, so assume that the theorem is true for . Then by the induction hypothesis, for any , there exists a point such that
If , for distinct indices and , then we’re done. Otherwise, by Radon’s theorem, there exists disjoint subsets and of such that the intersection
contains a point . I claim that . Indeed, we can write
where and . For any , . Since the sets are convex, . Similarly, for any , and therefore . We conclude that
If we don’t impose any topological conditions on the sets , then the theorem is false for infinite collections. Simply consider the collection of intervals , for . However, if we also require the sets to be compact, then Helly’s theorem is true for infinite collections.
Corollary 2. Let , where , be a (possibly infinite) collection of compact, convex subsets of . If, for any distinct ,
Proof. For any finite subset , the intersection is nonempty by Helly’s theorem. Fix some and consider the collection of nonempty subsets of . Since is compact, the intersection
if and only if there exists some finite subset of indices such that .
Helly’s theorem has many applications, as I have learned from reading Alexander Barvinok’s A Course in Convexity, which has served as the reference for this post as well as others on combinatorial geometry. The author covers a broad range of topics in convexity and has included many challenging exercises. My only complaint is that most of the applications are still theoretical, but this is to be expected given that it’s a “pure math” text.
One of the applications of Helly’s theorem is proving the existence of a hyperplane strictly separating disjoint finite sets in and in . The result is known as Kirchberger’s theorem, proven by P. Kirchberger in 1903, predating Helly’s theorem.
Theorem 2. (Kirchberger’s Theorem) Suppose that for any set with , there exists a hyperplane which strictly separates and . Then there exists a hyperplane which strictly separates the sets and . Then there exists a hyperplane which strictly separates and .
Proof. Note that since any hyperplane in is of the form , where and , there is a bijection between hyperplanes in and points .
For any points and , we define sets in by
I claim that are convex, open sets. For convexity, observe that
The argument for is completely analogous. To see that and are open, fix and let . If satisfies and , then
Hence, contains the open neighborhood . A completely analogous argument shows that is open.
If we can show that, for any subset consisting of at most points, the intersection
then by Helly’s theorem,
Since and are open, for any and , the intersection of finitely many sets is open. This intersection is nonempty if and only if it contains a point , where (otherwise, the strict inequalities and cannot hold). But such a point exists by our hypothesis that, for any such set , there exists a hyperplane which strictly separates and .
We conclude that there exists a point in such that
which is equivalent to the existence of a hyperplane strictly separating and .