18 I. Convex Sets at Large

Let

v =

i:γi 0

γi

β

vi =

i:γi 0

−γi

β

vi.

Hence v is a convex combination of points from R and a convex combination of

points from B. In other words, v ∈ conv(R) and v ∈ conv(B).

a

b

c

d

a

b

c

d

Figure 5. Example: for any set of four points in the plane, either one

of the points lies within the convex hull of the other three, or the points

can be split into two pairs whose convex hulls intersect.

PROBLEMS.

1◦.

Show by an example that the constant d + 2 in Radon’s Theorem cannot

be improved to d + 1.

2∗

(Tverberg’s Theorem). Let k ≥ 2. Prove that for any set S of (k−1)(d+1)+1

or more points in

Rd,

one can find k pairwise non-intersecting subsets A1,... , Ak ⊂

S such that the intersection

conv(A1) ∩ conv(A2) ∩ . . . ∩ conv(Ak)

is not empty. Show that for some sets of (k − 1)(d + 1) points, such subsets

A1,... , Ak cannot be found.

Remark: See, for example, Chapter 8 of [Mat02].

The following result (one of the most famous results in convexity) was discov-

ered by E. Helly in 1913. The proof below is due to Radon (1921).

(4.2) Helly’s Theorem. Let A1,... , Am, m ≥ d + 1, be a finite family of convex

sets in

Rd.

Suppose that every d + 1 of the sets have a common point:

Ai1 ∩ . . . ∩ Aid+1 = ∅.

Then all the sets have a common point:

A1 ∩ . . . ∩ Am = ∅.