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,

::$$igcap_{j=1}^n X_j evarnothing.

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

:$$pinigcap_{j=1}^n X_j.

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_nwith 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.