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
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,
\bigcap_{j=1}^n X_j\ne\varnothing.

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

X_2,X_3,\dots,X_n.

Likewise, for every

j=2,3,\dots,n

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

A=\{x_1,x_2,\dots,x_n\}.

Radon's theorem tells us that there are disjoint subsets A_1,A_2\subset A 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

p\in\bigcap_{j=1}^n X_j.

Indeed, consider any j\in\{1,2,...,n\}. Note that the only element of A that is not in Xj is xj. If x_j\in A_1, then x_j\notin A_2, and therefore X_j\supset A_2. Since Xj is convex, it then also contains the convex hull of A2 and therefore also p\in X_j. Likewise, if x_j\notin A_1, then X_j\supset A_1, and by the same reasoning p\in X_j. Since p is in every Xj, 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 xi = xk for some i\ne k, 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

X_{n-1}\cap X_n.

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.