# Helly's theorem

This is the last of a small series of similar and basic results in convex geometry.

Helly's theorem: Let $$X_1,\ldots,X_n$$ be a finite collection of convex subsets of $$R^d$$. If the intersection of every $$d+1$$ of these sets is nonempty, then the whole collection has a nonempty intersection.

Proof:
Below we show that if every $$k\geq d+1$$ sets have nonempty intersection, then so do every $$k+1$$ sets.

It suffices to consider only $$k+1\geq d+2$$ convex sets $$X_1,\ldots,X_{k+1}$$.

Let $$C_i=\bigcap_{v\neq i}X_v$$

Clearly if any two distinct $$C_i$$ and $$C_j$$ overlap then we are done, so assume they don't and pick a representative point $$p_i$$ for $$C_i$$ for each $$i$$. Now apply Radon's theorem to $$p_1,\ldots,p_{k+1}$$, i.e. without loss of generality there is a point $$x$$ that is convex combination of $$p_1,\ldots,p_m$$, and also convex combination of $$p_{m+1},\ldots,p_{k+1}$$. For any $$i\in[1,m]$$, the latter ensures $$x\in X_i$$, and for any $$i\in[m+1,k+1]$$, the former implies the same thing.
Q.E.D.