# Helly’s theorem

Suppose $A_{1},\ldots,A_{m}\subset\mathbb{R}^{d}$ is a family of convex sets, and every $d+1$ of them have a non-empty intersection. Then $\bigcap_{i=1}^{m}A_{i}$ is non-empty.

###### Proof.

The proof is by induction on $m$. If $m=d+1$, then the statement is vacuous. Suppose the statement is true if $m$ is replaced by $m-1$. The sets $B_{j}=\bigcap_{i\neq j}A_{i}$ are non-empty by inductive hypothesis. Pick a point $p_{j}$ from each of $B_{j}$. By Radon’s lemma, there is a partition of $p$’s into two sets $P_{1}$ and $P_{2}$ such that $I=(\operatorname{conv}P_{1})\cap(\operatorname{conv}P_{2})\neq\emptyset$. For every $A_{j}$ either every point in $P_{1}$ belongs to $A_{j}$ or every point in $P_{2}$ belongs to $A_{j}$. Hence $I\subseteq A_{j}$ for every $j$. ∎

Title Helly’s theorem HellysTheorem 2013-03-22 13:57:38 2013-03-22 13:57:38 bbukh (348) bbukh (348) 6 bbukh (348) Theorem msc 52A35