Helly’s theorem

Suppose $A_1,\mathrm{\dots },A_m\subset {ℝ}^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\ne 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=(\mathrm{conv}{P}_1)\cap (\mathrm{conv}{P}_2)\ne \mathrm{\varnothing }$. 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