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
Canonical name	HellysTheorem
Date of creation	2013-03-22 13:57:38
Last modified on	2013-03-22 13:57:38
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	6
Author	bbukh (348)
Entry type	Theorem
Classification	msc 52A35