Helly's Theorem

Helly's Theorem

Helly's theorem is a statement about intersections of convex sets. A general theorem is as follows:

Let C be a finite family of convex sets in Rn such that, for k ≤ n + 1, any k members of C have a nonempty intersection. Then the intersection of all members of C is nonempty.

It is a well publicized fact that Eduard Helly published a proof of the theorem that bears his name in 1923, two years after Johann Radon published his. Alexander Soifer in his recent book gave an explanation to an apparent injustice:

(the theorem) ... was discovered by the Austrian mathematician Eduard Helly (Vienna, 1884 - Chicago, 1943), in 1913. But it was not published at that time. During World War I, Helly was a soldier in the Austrian Army, and he was taken a Russian prisoner in 1914. He explained his theorem to another Austrian mathematician who was in Russian captivity as well.

The theorem lived in mathematical folklore from the time of these mysterious meeting of two mathematical prisoners until 1921 when the first proof of the Helly theorem was published by the Austrian mathematician Johann Karl August Radon (with a reference to Helly). In 1923 Helly published his own proof (different from Radon's!).

I shall give a simple proof of the theorem in R² as it appears in the classical book of V. Boltyanski and I. Yaglom. The proof has been reproduced in [Etudes] by A. Soifer.

The proof starts with a particular case

Lemma

Four convex figures are given in the plane. If every three of them have a nonempty intersection, then the intersection of all four figure is also nonempty.

Proof of Lemma

Denote the four sets F1, F2, F3, F4. For j = 1, 2, 3, 4, let aj be a common point of the three sets, with Fj removed. Thus, for example, a1 ∈ F2 ∩ F3 ∩ F4, etc. Two cases are possible:

  1. One of the points a1, a2, a3, a4 lies in the interior or the border of the triangle formed by the other three. Assume, for example, that a1 ∈ Δa2a3a4. But each of the points a2, a3, a4 belongs to F1. By the convexity of the latter, the whole Δa2a3a4 ⊂ F1 and so a1 ∈ F1. Since, by our assumption, a1 ∈ F2 ∩ F3 ∩ F4, we also have a1 ∈ F1 ∩ F2 ∩ F3 ∩ F4.

  2. Points a1, a2, a3, a4 form a convex quadrilateral, so that none of them lies in the triangle formed by the other three. The diagonal a1a3 wholly belongs to F2 ∩ F4 while the diagonal a2a4 wholly belongs to F1 ∩ F3. The intersection of the diagonals then belongs to (F2 ∩ F4) ∩ (F1 ∩ F3).

Proof of Helly's Theorem (in R²)

The proof is by induction on the number s of sets in C. The case of s = 4 is covered by Lemma. So let's assume that the theorem holds for some s ≥ 4 and consider s + 1 sets F1, ..., Fs, Fs+1 with the property that the intersection of any three of them is nonempty.

Define Gk = Fk ∩ Fs+1, k = 1, ..., s. The intersection of any three G's is nonempty. For example,

G1 ∩ G2 ∩ G3 = F1 ∩ F2 ∩ F3 ∩ Fs+1,

which is nonempty by Lemma. This means that the intersection of all G's is nonempty. But the intersection of all G's is exactly the intersection of all F's.

References

  1. B. Bollobás, The Art of Mathematics, Cambridge University Press, 2006, p. 90-91
  2. A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)
  3. Yaglom, I. M.and V. G. Boltyanski, Convex Figures, Holt, Rinehart and Winstion, 1961

Convex Sets

|Contact| |Front page| |Contents| |Geometry| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 61184970

Search by google: