Helly’s Theorem and Applications

So, I’ve written now on Radon’s theorem and Carathéodory’s theorem, but I have yet to complete the trifecta of results in combinatorial geometry; I have yet to say anything about Helly’s theorem. Helly’s theorem says that if we have a finite collection of convex sets in $\mathbb{R}^{d}$ with the property that every subcollection of $d+1$ sets has nonempty intersection, then the entire collection has nonempty intersection. More precisely:

Theorem 1. (Helly) Let $A_{1},\cdots,A_{m}$ , where $m\geq d+1$ , be a finite collection of convex sets in $\mathbb{R}^{d}$ . If, for every $d+1$ sets $i_{1},\cdots,i_{d+1}$ ,

$\displaystyle A_{i_{1}}\cap\cdots\cap A_{i_{d+1}}\neq\emptyset$

then

$\displaystyle A_{1}\cap\cdots\cap A_{m}\neq\emptyset$

We will prove Helly’s theorem using Radon’s theorem and in fact, the theorems of Helly, Radon, and Carathéodory are equivalent. I neither know the proof of this equivalence nor have a reference for a proof at hand, but I will try to find one–please drop me a comment if you have a reference! Before we prove Helly’s theorem, I want to make a couple observations on the necessity of the hypotheses.

The theorem is false if we drop the hypothesis that the $A_{i}$ are convex. Indeed, let $m=d+2$ , and let $\left\{x_{1},\cdots,x_{m}\right\}$ be a collection of distinct points in $\mathbb{R}^{d}$ . For each $i\in\left\{1,\cdots,m\right\}$ , define the nonconvex set

$A_{i}:=\left\{x_{j}: 1\leq j\leq m, j\neq i\right\}$

Clearly, $\bigcap_{i=1}^{m}A_{i}=\emptyset$ , but for any $d+1$ sets $A_{j}: 1\leq j\leq m, i\neq j$ , the intersection consists of the point $x_{i}$ .

The theorem is also false if we relax the hypothesis to every $d$ collection of subsets has nonempty intersection. Let $d=2$ , and consider the collection of closed balls $\overline{B}_{1},\overline{B}_{2}$ and open ball ${B}_{3}$ of radius $1$ centered at $(0,0), (2,0)$ , and $(1,1)$ , respectively. It is clear that any two balls intersect nontrivially, but the intersection of all three must be empty since $(1,0)\notin B_{3}$ . Here’s a picture:

Proof of Theorem 1. We proceed by induction on $m$ . In the base case $m=d+1$ , there is nothing to prove, so assume that the theorem is true for $m>d+1$ . Then by the induction hypothesis, for any $i\in\left\{1,\cdots,m\right\}$ , there exists a point $p_{i}$ such that

$\displaystyle p_{i}\in A_{1}\cap\cdots A_{i-1}\cap A_{i+1}\cap\cdots\cap A_{m}$

If $p_{i}=p_{j}$ , for distinct indices $i$ and $j$ , then we’re done. Otherwise, by Radon’s theorem, there exists disjoint subsets $I$ and $J$ of $\left\{1,\cdots,m\right\}$ such that the intersection

$\displaystyle\text{co}\left\{p_{i}:i\in I\right\}\cap\text{co}\left\{p_{j}: j\in I\right\}$

contains a point $p$ . I claim that $p\in\bigcap_{i=1}^{m}A_{i}$ . Indeed, we can write

$\displaystyle p=\sum_{i\in I}\lambda_{i}p_{i}=\sum_{j\in J}\lambda_{j}p_{j}$ ,

where $\lambda_{i},\lambda_{j}\geq 0$ and $\sum_{i\in I}\lambda_{i}=\sum_{j\in J}\lambda_{j}=1$ . For any $j\in J$ , $p_{j}\in A_{i} \ \forall i\notin J$ . Since the sets $A_{1},\cdots,A_{m}$ are convex, $\text{co}\left\{p_{j}:j\in J\right\}\subset A_{i} \ \forall i\notin J$ . Similarly, for any $i\in I$ , $p_{i}\in A_{j} \ \forall j\notin I$ and therefore $\text{co}\left\{p_{i}:i\in I\right\} \subset A_{j} \ \forall j\notin I$ . We conclude that

$\displaystyle p\in\left(\bigcap_{i\notin I}A_{i}\right)\cap\left(\bigcap_{j\notin J}A_{j}\right)=\bigcap_{i=1}^{m}A_{i}$

$\Box$

If we don’t impose any topological conditions on the sets $A_{i}$ , then the theorem is false for infinite collections. Simply consider the collection of intervals $(-\infty,-n]$ , for $n\in\mathbb{Z}^{\geq0}$ . However, if we also require the sets $A_{i}$ to be compact, then Helly’s theorem is true for infinite collections.

Corollary 2. Let $\left\{A_{i}:I\right\}$ , where $\left|I\right|\geq d+1$ , be a (possibly infinite) collection of compact, convex subsets of $\mathbb{R}^{d}$ . If, for any distinct $i_{1},\cdots,i_{d+1}\in I$ ,

$\displaystyle A_{i_{1}}\cap\cdots\cap A_{i_{d+1}}\neq\emptyset$

then $\bigcap_{i\in I}A_{i}\neq\emptyset$ .

Proof. For any finite subset $J\subset I$ , the intersection $\bigcap_{i\in J}A_{i}$ is nonempty by Helly’s theorem. Fix some $k\in I$ and consider the collection $\left\{A_{k}\cap A_{i}\right\}_{i\in I}$ of nonempty subsets of $A_{k}$ . Since $A_{k}$ is compact, the intersection

$\displaystyle\bigcap_{i\in I}A_{i}=\bigcap_{i\in I}A_{k}\cap A_{i}=\emptyset$

if and only if there exists some finite subset of indices $J\subset I$ such that $\bigcap_{i\in J}A_{k}\cap A_{i}=\emptyset$ . $\Box$

Helly’s theorem has many applications, as I have learned from reading Alexander Barvinok’s A Course in Convexity, which has served as the reference for this post as well as others on combinatorial geometry. The author covers a broad range of topics in convexity and has included many challenging exercises. My only complaint is that most of the applications are still theoretical, but this is to be expected given that it’s a “pure math” text.

One of the applications of Helly’s theorem is proving the existence of a hyperplane strictly separating disjoint finite sets in $R$ and $B$ in $\mathbb{R}^{d}$ . The result is known as Kirchberger’s theorem, proven by P. Kirchberger in 1903, predating Helly’s theorem.

Theorem 2. (Kirchberger’s Theorem) Suppose that for any set $S\subset\mathbb{R}^{d}$ with $\left|S\right|\leq d+2$ , there exists a hyperplane which strictly separates $S\cap R$ and $S\cap B$ . Then there exists a hyperplane which strictly separates the sets $S\cap R$ and $S\cap B$ . Then there exists a hyperplane which strictly separates $R$ and $B$ .

Proof. Note that since any hyperplane $H$ in $\mathbb{R}^{d}$ is of the form $H=\left\{x\in\mathbb{R}^{d}:\langle{c,x}\rangle=\alpha\right\}$ , where $c=(c_{1},\cdots,c_{d})\in\mathbb{R}^{d}$ and $\alpha\in\mathbb{R}$ , there is a bijection between hyperplanes in $\mathbb{R}^{d}$ and points $(c,\alpha)\in\mathbb{R}^{d+1}$ .

For any points $r\in R$ and $b\in B$ , we define sets in $\mathbb{R}^{d+1}$ by

$\displaystyle A_{r}:=\left\{(c,\alpha)\in\mathbb{R}^{d+1}:\langle{c,r}\rangle<\alpha\right\},\indent A_{b}:=\left\{(c,\alpha)\in\mathbb{R}^{d+1}:\langle{c,b}\rangle>\alpha\right\}$

I claim that $A_{r}, A_{b}$ are convex, open sets. For convexity, observe that

$\begin{array}{lcl}\displaystyle(c_{1},\alpha_{1}),(c_{2},\alpha_{2})\in A_{r}\Rightarrow \langle{\lambda c_{1}+(1-\lambda)c_{2},r}\rangle&=&\displaystyle\lambda\langle{c_{1},r}\rangle+(1-\lambda)\langle{c_{2},r}\rangle\\&<&\displaystyle\lambda\alpha_{1}+(1-\lambda)\alpha_{2}\end{array}$

The argument for $A_{b}$ is completely analogous. To see that $A_{r}$ and $A_{b}$ are open, fix $(c,\alpha)\in A_{r}$ and let $\epsilon > 0$ . If $(c',\beta)\in\mathbb{R}^{d+1}$ satisfies $\left\|c-c'\right\|<\epsilon$ and $\beta>\alpha+\epsilon\left\|r\right\|$ , then

$\displaystyle\langle{c',r}\rangle<\alpha+\langle{c'-c,r}\rangle\leq\alpha+\left\|c'-c\right\|\left\|r\right\|<\alpha+\epsilon\left\|r\right\|=\beta+(\alpha-\beta)+\epsilon\left\|r\right\|<\beta$

Hence, $A_{r}$ contains the open neighborhood $B(c;\epsilon)\times(\alpha+\epsilon\left\|r\right\|,\infty)$ . A completely analogous argument shows that $A_{b}$ is open.

If we can show that, for any subset $S\subset R\cup B$ consisting of at most $d+2$ points, the intersection

$\displaystyle\left(\bigcap_{r\in S\cap R}A_{r}\right)\cap\left(\bigcap_{b\in S\cap B}A_{b}\right)\neq\emptyset$ ,

then by Helly’s theorem,

$\displaystyle\left(\bigcap_{r\in R}A_{r}\right)\cap\left(\bigcap_{b\in B}A_{b}\right)\neq\emptyset$

Since $A_{r}$ and $A_{b}$ are open, for any $r\in R$ and $b\in B$ , the intersection of finitely many sets $A_{r_{1}},\cdots,A_{r_{k}},A_{b_{1}},\cdots,A_{b_{m}}$ is open. This intersection is nonempty if and only if it contains a point $(c,\alpha)\in\mathbb{R}^{d+1}$ , where $c\neq 0$ (otherwise, the strict inequalities $\langle{c,r}\rangle<\alpha$ and $\langle{c,b}\rangle>\alpha$ cannot hold). But such a point exists by our hypothesis that, for any such set $S$ , there exists a hyperplane which strictly separates $S\cap R$ and $S\cap B$ .