Helly's theorem is a statement about intersections of convex sets. A general theorem is as follows:
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!).
The proof starts with a particular case
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,
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 ⊂ F1and so a1 ∈ F1.Since, by our assumption, a1 ∈ F2 ∩ F3 ∩ F4,we also have a1 ∈ F1 ∩ F2 ∩ F3 ∩ F4.
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 ∩ F4while 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
Define Gk = Fk ∩ Fs+1, k = 1, ..., s. The intersection of any three G's is nonempty. For example,
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.
- 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
Copyright © 1996-2018 Alexander Bogomolny