- Helly's theorem
In
geometry , Helly's theorem is a basic combinatorial result onconvex set s. It was proved byEduard Helly in 1923, and gave rise to the notion ofHelly 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 pointx_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.
Wikimedia Foundation. 2010.