Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Categories: Convex geometry | Discrete geometry | Theorems | Proofs

Helly's theorem

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

Suppose that

$X_1,X_2,\dots,X_n$

is a finite collection of convex sets in

R d

. Also suppose that

n > d + 1

and the intersection of any

d + 1

of these sets is nonempty. Helly's theorem states that in this case the whole collection has a nonempty intersection; that is,

$\bigcap_{j=1}^n X_j\ne\emptyset$ .

For infinite collections one has to assume compactness:

{X α}

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 easily follows by an elementary compactness argument.) 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 the common 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_2\subset 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

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

Indeed, suppose that $j\in\{1,2,\dots,n\}$ . Note that the only element of $A$ that is not in $X j$ is $x j$ . If $x_j\in A_1$ , then $x_j\notin A_2$ , and therefore $X_j\supset A_2$ . Since $X j$ is convex, it then also contains the convex hull of $A 2$ 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 $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\ne 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 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.

References:

H. G. Eggleston, Convexity, Cambridge Univ. Press
S. R. Lay, Convex Sets and Their Applications, Wiley.

Categories: Convex geometry | Discrete geometry | Theorems | Proofs

Last updated: 05-15-2005 03:36:25

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects