Helly's theorem
From Wikipedia, the free encyclopedia
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.
[edit] Statement of Helly's theorem
- Suppose that
- is a finite collection of convex subsets of , 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α} is a collection of compact convex subsets of Rd and every subcollection of cardinality at most d + 1 has nonempty intersection, then the whole collection has nonempty intersection.
[edit] Proof of Helly's theorem
We prove the finite version. (The infinite version easily follows by an elementary compactness argument.) Suppose first that n = d + 2. By our assumptions, there is a point x1 that is in the common intersection of
- .
Likewise, for every
there is a point xj that is in the common intersection of all Xi with the possible exception of Xj. We now apply Radon's theorem to the set
Radon's theorem tells us that there are disjoint subsets such that the convex hull of A1 intersects the convex hull of A2. Suppose that p is a point in the intersection of these two convex hulls. We claim that
Indeed, consider any . Note that the only element of A that is not in Xj is xj. If , then , and therefore . Since Xj is convex, it then also contains the convex hull of A2 and therefore also . Likewise, if , then , and by the same reasoning . Since p is in every Xj, it must also be in the intersection.
Above, we have assumed that the points are all distinct. If this is not the case, say xi = xk for some , then xi is in every one of the sets Xj, 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 Xn − 1 and Xn with the single set
In this new collection, every subcollection of d + 1 sets will have nonempty intersection. The inductive hypothesis therefore applies, and shows that this new collection has nonempty intersection. This implies the same for the original collection, and completes the proof.
[edit] 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.