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.

Therefore,

p ∈

i/I ∈

Ai and p ∈

j /J ∈

Aj.

Since I ∩ J = ∅, we have

p ∈

m

i=1

Ai

and the proof follows.

PROBLEMS.

1◦.

Show that the theorem does not hold for non-convex sets Ai.

2◦.

Construct an example of convex sets Ai in

R2,

such that every two sets

have a common point, but there is no point which would belong to all the sets Ai.

3◦.

Give an example of an infinite family {Ai : i = 1, 2, . . . } of convex sets in

Rd

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

Rd

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:

i∈I

Ai = ∅.