Helly s Theorem
Presentation Outline
Oleg Golberg
November 20, 2007
1 Line segments
Proposition 1. Given n segments of a line, if every two of them have a common point, all
n of them have a common point.
Proof outline. Consider the rightmost left endpoint.
How can we generalize this result for higher dimensions? To do that, we need to think
about the properties of segments in R.
" They are closed.
" They are connected.
" They are closed balls.
" They are convex.
2 Convexity
Definition 1. For x, y " Rn we will denote by s(x, y) the set of points on the segment with
endpoints x and y.
Definition 2. A set C ‚" Rn is called convex if s(x, y) ‚" C for all x, y " C.
Proposition 2. For all x, y " Rn
s(x, y) = {x + (1 - )y | 0 d"  d" 1} .
Definition 3. The convex hull of x1, x2, . . . , xn " Rn is


H(x1, x2, . . . , xk) = ixi | i e" 0, i = 1 .
1d"id"k 1d"id"k
1/4
Proposition 3. If a convex C ‚" Rn contains all x1, x2, . . . , xk, then
H(x1, x2, . . . , xk) ‚" C.
Proof outline. Induct using proposition 2.
Corollary 1. For any choice of points x1, x2, . . . , xk " Rk their convex hull is the minimum
by inclusion convex set that contains all of them.
Proof outline. It suffices to observe that xi " H(x1, x2, . . . , xn) for all 1 d" i d" n.
3 Radon s Theorem
Theorem 1 (Radon, [1]). For each S ‚" Rn with |S| = n + 2 there exist nonempty disjoint
S1, S2 ‚" S such that
H(S1) *" H(S2) = ".

Proof outline. Let S = {x1, x2, . . . , xn+2}. For each 1 d" i d" n+2 if xi = (xi1, xi2, . . . , xi(n+2))
we define yi = (xi1, xi2, . . . , xi(n+2), 1) " Rn+1. There exist k1, k2, . . . , kn+2 such that

kiyi = 1.
1d"id"n+2
Let ki , ki , . . . , ki > 0 and kj , kj , . . . , kj < 0. Then
1 2 p 1 2 q

ki = |kj | = d.
l l
1d"ld"p 1d"ld"q
This instantly implies p, q > 0. We also have

ki |kj |
l l
xi = xj .
l l
d d
1d"ld"p 1d"ld"q
The LHS is clearly in H(xi , xi , . . . , xi ) whereas the RHS is clearly in H(xj , xj , . . . , xj ).
1 2 p 1 2 q
4 Helly s Theorem
Theorem 2 (Helly, [2]). Given a finite collection C of convex sets in Rn, if every n + 1 of
them have a common point, all of them have a common point.
Proof outline. We induct on |C|. Suppose the statement is true for m-1 e" n+1 and consider
convex sets C1, C2, . . . , Cm satisfying the property from the theorem statement. The by the
inductive hypothesis every m - 1 of them have a common point. For all 1 d" i d" m let
bi " C1 )" C2 )" · · · )" Ci-1 )" Ci+1 )" · · · )" Cm.
2/4
Since m e" n+2, by Radon Theorem there exist disjoint A, B " {1, 2, . . . , m} such that there
is a point p that belongs to both H({bi}i"A) and H({bj}j"B). For every 1 d" j d" m either
j " A or j " B. In the former case
{bi}i"A ‚" Cj
and thus
p " H({bi}i"A) ‚" Cj.
The latter case is analogous.
The number n + 1 in Helly s theorem is precise. For example, consider the edges of an
n-dimensional simplex. Every n of them share a vertex of the simplex whereas no point
belongs to all of them.
5 The infinite case
Note that as long as C is finite its sets can be unbounded. What about infinite C? The
1
example of Ci = (0, ) shows that Helly s theorem in general does not hold for infinite
i
collections even if we require the sets to be bounded. The example of Ci = [i, ") shows that
Helly s theorem does not work in general either if we require the sets to be closed. However,
combining these two natural restrictions yields a positive result.
Proposition 4. Given an infinite collection C of bounded closed convex sets in Rn, if every
n + 1 of them have a common point, all of them have a common point.
Proof outline. Because the sets are bounded, there is a closed ball B that contains all of them.
Suppose no point belongs to all sets from C. This means, the union of their complements
is Rn. In particular, they cover B. However, B is compact and the complements of the sets
from C are open. Thus, there is a finite subcovering, i.e. a finite number of complements
cover B. This means, there is a finite subcollection of C of sets that do not have a common
point. This contradicts with Helly s theorem.
6 Applications
Planar results are introduced for the sake of simplicity. All of them allow straightforward
generalizations to n dimensions. Further applications can be found in [3] and [4].
Proposition 5. Given a set of points on the plane, if every 3 of them can be covered by a
unit disk, all of them can be covered by a unit circle.
Proposition 6. Given a convex polygon P, there is point inside it such that every line
1
through it splits P into two polygons with area ratio between and 2.
2
Proposition 7. If n e" 3 semiplanes cover the plane, then there are three of them that cover
the plane.
Proposition 8. For every convex polygon P there is a dilation Ć with coefficient -1 such
2
that Ć(P ) ‚" P.
3/4
7 Further results
Further  Helly-like results can be pursued at least in two directions: restricting the shape
of the sets and relaxing the intersection property. One example of the former is as follows.
Proposition 9. In a collection of axis-parallel n-dimensional boxes, if every two have a
common point, then all paralellotopes have a common point.
A prominent example of the latter generalization is Hadwiger-Debrunner problem.
Definition 4. A collection C of convex sets in Rn is said to have the (p, q)-property if among
every p elements of C there are at least q that have a common point.
The problem is to find whether there exists M = M(p, q, n) such that every collection
with (p, q)-property can be partitioned into at most M subcollection such that all elements
of every subcollection have a common point, and find its precise value. The problem was
posed in 1957 [5]. The authors proved that if p(n - 1) < (q - 1)n, then M(p, q, n) = p - q + 1
and conjectured that in general M(p, q, n) exists if and only if p e" q > n. It was only in 1992
that N. Alon and D. Kleitman confirmed the conjecture [6]. However, the precise value of
M is not yet found even for many small values p, q, n. In particular, M(4, 3, 2) is only known
to be between 3 and 13  a result obtained in 2001 [7].
References
[1] J. Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Math.
Ann., 83:113 115, 1921.
[2] E. Helly. Über mengen konvexer Körper mit gemeinschaftlichen Punkten. Jber. Deutsch.
Math. Vereinig, 32:175 176, 1923.
[3] I.M. Yaglom and V.G. Boltyansky. Convex Figures. Holt, Rinehart, and Winston, 1961.
[4] H. Hadwiger, H. Debrunner, and V.L. Klee. Combinatorial geometry in the plane. Holt,
Rinehart, and Winston, 1964.
[5] H. Hadwiger and H. Debrunner. Über eine variante zum Hellyschen satz. Archiv der
Mathematik, 8(4):309 313, 1957.
[6] N. Alon and D.J. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p, q)
problem. Advances in Math., 96:103 112, 1992.
[7] D.J. Kleitman, A. Gyárfás, and G. Tóth. Convex sets in the plane with three of every
four meeting. Combinatorica, 21(2):221 232, 2001.
4/4