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 Rⁿ 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 F₁, F₂, F₃, F₄. For j = 1, 2, 3, 4, let a_j be a common point of the three sets, with F_j removed. Thus, for example, a₁ ∈ F₂ ∩ F₃ ∩ F₄, etc. Two cases are possible:

One of the points a₁, a₂, a₃, a₄ lies in the interior or the border of the triangle formed by the other three. Assume, for example, that a₁ ∈ Δa₂a₃a₄. But each of the points a₂, a₃, a₄ belongs to F₁. By the convexity of the latter, the whole Δa₂a₃a₄ ⊂ F₁ and so a₁ ∈ F₁. Since, by our assumption, a₁ ∈ F₂ ∩ F₃ ∩ F₄, we also have a₁ ∈ F₁ ∩ F₂ ∩ F₃ ∩ F₄.
Points a₁, a₂, a₃, a₄ form a convex quadrilateral, so that none of them lies in the triangle formed by the other three. The diagonal a₁a₃ wholly belongs to F₂ ∩ F₄ while the diagonal a₂a₄ wholly belongs to F₁ ∩ F₃. The intersection of the diagonals then belongs to (F₂ ∩ F₄) ∩ (F₁ ∩ F₃).

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 F₁, ..., F_s, F_s+1 with the property that the intersection of any three of them is nonempty.

Define G_k = F_k ∩ F_s+1, k = 1, ..., s. The intersection of any three G's is nonempty. For example,

G₁ ∩ G₂ ∩ G₃ = F₁ ∩ F₂ ∩ F₃ ∩ F_s+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

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

Convex Sets

Helly's Theorem

First Applications of Helly's Theorem
Crossed-Lines Construction of Shapes of Constant Width
Shapes of constant width (An Interactive Gizmo)
Star Construction of Shapes of Constant Width
Convex Polygon Is the Intersection of Half Planes
Minkowski's addition of convex shapes
The Theorem of Barbier
A. Soifer's Book, P. Erdos' Conjecture, B. Grunbaum's Counterexample

41173506