4. Theorems of Radon and Helly 19
Proof. The proof is by induction on m (starting with m = d + 1). Suppose that
m d + 1. Then, by the induction hypothesis, for every i = 1, . . . , m there is
a point pi in the intersection A1 . . . Ai−1 Ai+1 . . . Am (Ai is missing).
Altogether, we have m d + 1 points pi, each of which belongs to all the sets,
except perhaps Ai. If two of these points happened to coincide, we get a point
which belongs to all the Ai’s. Otherwise, by Radon’s Theorem (Theorem 4.1) there
are non-intersecting subsets R = {pi : i I} and B = {pj : j J} such that there
is a point
p conv(R) conv(B).
We claim that p is a common point of A1,... , Am. Indeed, all the points pi : i I
of R belong to the sets Ai : i / I. All the points pj : j J of B belong to the sets
Aj : j / J. Since the sets Ai are convex, every point from conv(R) belongs to the
sets Ai : i / I. Similarly, every point from conv(B) belongs to the sets Aj : j / J.
Ai and p
j /J
Since I J = ∅, we have
and the proof follows.
Show that the theorem does not hold for non-convex sets Ai.
Construct an example of convex sets Ai in
such that every two sets
have a common point, but there is no point which would belong to all the sets Ai.
Give an example of an infinite family {Ai : i = 1, 2, . . . } of convex sets in
such that every d+1 sets have a common point but there are no points common
to all the sets Ai.
The theorem can be extended to infinite families of compact convex sets.
(4.3) Corollary. Let {Ai : i I}, |I| d + 1 be a (possibly infinite) family of
compact convex sets in
such that the intersection of any d +1 sets is not empty:
Ai1 . . . Aid+1 = ∅.
Then the intersection of all the sets Ai is not empty:
Ai = ∅.
Previous Page Next Page