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:

An example of three convex sets

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.

We conclude that there exists a point in (c,\alpha)\in\mathbb{R}^{d+1} such that

\displaystyle(c,\alpha)\in\left(\bigcap_{r\in R}A_{r}\right)\cap\left(\bigcap_{b\in B}A_{b}\right)

which is equivalent to the existence of a hyperplane strictly separating R and B. \Box

 

Advertisements
This entry was posted in math.CO and tagged , , . Bookmark the permalink.

One Response to Helly’s Theorem and Applications

  1. Pingback: Helly’s Theorem and Applications II: Jung’s Theorem | Math by Matt

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s