Helly's theorem

In geometry, Helly's theorem is a basic combinatorial result on convex sets. It was proved by Eduard Helly in 1923, and gave rise to the notion of Helly family.

tatement of Helly's theorem

:Suppose that

::$X\_1,X\_2,dots,X\_n$

:is a finite collection of convex subsets of $Bbb\{R\}^d$, where $n\; >\; d$. If the intersection of every $d+1$ of these sets is nonempty, then the whole collection has a nonempty intersection; that is,

::

For infinite collections one has to assume compactness::If $\{X\_alpha\}$ is a collection of compact convex subsets of $R^d$ and every subcollection of cardinality at most $d+1$ has nonempty intersection, then the whole collection has nonempty intersection.

Proof of Helly's theorem

We prove the finite version; the infinite version then follows by the finite intersection property characterization of compactness: a collection of closed subsets of a compact space has a non-empty intersection if and only if every finite subcollection has a non-empty intersection (once you fix a single set, the intersection of all others with it are closed subsets of a fixed compact space).

Suppose first that $n=d+2$. By our assumptions, there is a point$x\_1$ that is in the common intersection of :$X\_2,X\_3,dots,X\_n$.Likewise, for every

:$j=2,3,dots,n$

there is a point $x\_j$ that is in thecommon intersection of all $X\_i$ with the possible exception of $X\_j$.We now apply Radon's theorem to the set

:$A=\{x\_1,x\_2,dots,x\_n\}.$

Radon's theorem tells us that there are disjoint subsets $A\_1,A\_2subset\; A$ such that the
convex hull of $A\_1$ intersects the convex hull of $A\_2$. Suppose that $p$ is a point in the intersection of these two convex hulls. We claim that

:

Indeed, consider any $jin\{1,2,...,n\}$. Note that the only element of $A$ that is notin $X\_j$ is $x\_j$. If $x\_jin\; A\_1$, then $x\_j\; otin\; A\_2$, and therefore $X\_jsupset\; A\_2$.Since $X\_j$ is convex, it then also contains the convex hull of $A\_2$ and therefore also $pin\; X\_j$.Likewise, if $x\_j\; otin\; A\_1$, then $X\_jsupset\; A\_1$, and by the same reasoning $pin\; X\_j$.Since $p$ is in every $X\_j$, it must also be in the intersection.

Above, we have assumed that the points $x\_1,x\_2,dots,x\_n$ are all distinct. If this is not the case,say $x\_i=x\_k$ for some $i\; e\; k$, then $x\_i$ is in every one of the sets $X\_j$, and again we conclude that the intersection is nonempty. This completes the proof in the case $n=d+2$.

Now suppose that $n>d+2$ and that the statement is true for $n-1$, by induction.The above argument shows that any subcollection of $d+2$ sets will have nonempty intersection.We may then consider the collection where we replace the two sets $X\_\{n-1\}$ and $X\_n$with the single set

:$X\_\{n-1\}cap\; X\_n.$

In this new collection, every subcollection of $d+1$ sets willhave nonempty intersection. The inductive hypothesis therefore applies, and shows that thisnew collection has nonempty intersection. This implies the same for the original collection, and completes the proof.

References

*E. Helly, "Über Mengen konvexer Körper mit gemeinschaftlichen Punkten," Jber. Deutsch. Math. Vereinig. 32 (1923), 175-176.

*L. Danzer, B. Grünbaum, V. Klee, "Helly's theorem and its relatives," Convexity, Proc. Symp. Pure Math. Vol. VII, pp. 101-179. Amer. Math. Soc., Providence, R.I., 1963.

*J. Eckhoff, "Helly, Radon, and Carathéodory type theorems," Handbook of convex geometry, Vol. A, B, 389-448, North-Holland, Amsterdam, 1993.

*B. Bollobás, "The Art of Mathematics: Coffee Time in Memphis ", Cambridge University Press 2006. See problem 29," Intersecting Convex Sets: Helly's Theorem " and pages 90-91 for a proof of the theorem. ISBN 0521693950.