Helly's theorem

Helly's theorem for the Euclidean plane: if a family of convex sets has a nonempty intersection for every triple of sets, then the whole family has a nonempty intersection.

Helly's theorem is a basic result in discrete geometry describing the ways that convex sets may intersect each other. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared. Helly's theorem gave rise to the notion of a Helly family.

Statement

Suppose that

$X_1,X_2,\dots,X_n$

is a finite collection of convex subsets of $\Bbb{R}^d$, where $n > d$. If the intersection of every $d+1$ of these sets is nonempty, then the whole collection has a nonempty intersection; that is,

$\bigcap_{j=1}^n X_j\ne\varnothing.$

For infinite collections one has to assume compactness: If $\{X_\alpha\}$ is a collection of compact convex subsets of $R^d$ and every subcollection of cardinality at most $d+1$ has nonempty intersection, then the whole collection has nonempty intersection.

Proof

We prove the finite version, using Radon's theorem as in the proof by Radon (1921). The infinite version then follows by the finite intersection property characterization of compactness: a collection of closed subsets of a compact space has a non-empty intersection if and only if every finite subcollection has a non-empty intersection (once you fix a single set, the intersection of all others with it are closed subsets of a fixed compact space).

Suppose first that $n=d+2$. By our assumptions, there is a point $x_1$ that is in the common intersection of

$X_2,X_3,\dots,X_n.$

Likewise, for every

$j=1,2,3,\dots,n$

there is a point $x_j$ that is in the common intersection of all $X_i$ with the possible exception of $X_j$. We now apply Radon's theorem to the set

$A=\{x_1,x_2,\dots,x_n\}.$

Radon's theorem tells us that there are disjoint subsets $A_1,A_2\subset A$ such that the convex hull of $A_1$ intersects the convex hull of $A_2$. Suppose that $p$ is a point in the intersection of these two convex hulls. We claim that

$p\in\bigcap_{j=1}^n X_j.$

Indeed, consider any $j\in\{1,2,...,n\}$. Note that the only element of $A$ that may not be in $X_j$ is $x_j$. If $x_j\in A_1$, then $x_j\notin A_2$, and therefore $X_j\supset A_2$. Since $X_j$ is convex, it then also contains the convex hull of $A_2$ and therefore also $p\in X_j$. Likewise, if $x_j\notin A_1$, then $X_j\supset A_1$, and by the same reasoning $p\in X_j$. Since $p$ is in every $X_j$, it must also be in the intersection.

Above, we have assumed that the points $x_1,x_2,\dots,x_n$ are all distinct. If this is not the case, say $x_i=x_k$ for some $i\ne k$, then $x_i$ is in every one of the sets $X_j$, and again we conclude that the intersection is nonempty. This completes the proof in the case $n=d+2$.

Now suppose that $n>d+2$ and that the statement is true for $n-1$, by induction. The above argument shows that any subcollection of $d+2$ sets will have nonempty intersection. We may then consider the collection where we replace the two sets $X_{n-1}$ and $X_n$ with the single set

$X_{n-1}\cap X_n.$

In this new collection, every subcollection of $d+1$ sets will have nonempty intersection. The inductive hypothesis therefore applies, and shows that this new collection has nonempty intersection. This implies the same for the original collection, and completes the proof.

See also

• Carathéodory's theorem
• Shapley–Folkman lemma
• Krein–Milman theorem
• Choquet theory
• Radon's theorem

References

• Bollobás, B. (2006), "Problem 29, Intersecting Convex Sets: Helly's Theorem", The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, pp. 90–91, ISBN 0-521-69395-0 .
• Danzer, L.; Grünbaum, B.; Klee, V. (1963), "Helly's theorem and its relatives", Convexity, Proc. Symp. Pure Math. 7, American Mathematical Society, pp. 101–179 .
• Eckhoff, J. (1993), "Helly, Radon, and Carathéodory type theorems", Handbook of Convex Geometry A, B, Amsterdam: North-Holland, pp. 389–448 .
• Heinrich Guggenheimer (1977) Applicable Geometry, page 137, Krieger, Huntington ISBN 0-88275-368-1 .
• Helly, E. (1923), "Über Mengen konvexer Körper mit gemeinschaftlichen Punkten", Jahresbericht der Deutschen Mathematiker-Vereinigung 32: 175–176 .
• König, D. (1922), "Über konvexe Körper", Mathematische Zeitschrift 14 (1): 208–220, doi:10.1007/BF01215899 .
• Radon, J. (1921), "Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten", Mathematische Annalen 83 (1–2): 113–115, doi:10.1007/BF01464231 .