20 I. Convex Sets at Large

Proof. By Theorem 4.2, for any finite subfamily J ⊂ I the intersection

i∈J

Ai is

not empty. Now we use the fact that if the intersection of a family of compact sets

is empty, then the intersection of the sets from some finite subfamily is empty.

Helly’s Theorem has numerous generalizations, extensions, ramifications, etc.

To list all of them is impossible; here are just some.

PROBLEMS.

1. Let A1,... , Am be convex sets in

Rd

and let k ≤ d + 1. Prove that if

every k of the sets have a common point, then for every (d − k + 1)-dimensional

subspace L in

Rd

there exists a translate L + u : u ∈

Rd

which intersects every set

Ai : i = 1, . . . , m.

2. Let A1,... , Am and C be convex sets in Rd. Suppose that for any d + 1

sets Ai1 , . . . , Aid+1 there is a translate C + u : u ∈ Rd of C which intersects all

Ai1 , . . . , Aid+1 . Prove that there is a translate C + u of C which intersects all sets

A1,... , Am.

3. In Problem 2, replace intersects by contains.

4. In Problem 2, replace intersects by is contained in.

5∗

(Fractional Helly’s Theorem). Prove that for any 0 α 1 and any d there

exists a β = β(d, α) 0 with the following property:

Suppose that A1,... , Am, m ≥ d+1, are convex sets in

Rd.

Let f be the number)(

of (d + 1)-subfamilies Ai1 , . . . , Aid+1 that have a common point. If f ≥ α

m

d+1

,

then at least some βm sets Ai have a common point.

Prove that one can choose β = 1 − (1 −

α)1/(d+1).

Remark: The bound β = 1 − (1 −

α)1/(d+1)

is best possible. A weaker bound

β ≥ α/(d + 1) is much easier to prove; see Chapter 8 of [Mat02].

6∗ (“Piercing” Theorem). Prove that for every triple (p, q, d) such that p ≥

q ≥ d + 1 there exists a positive integer c(p, q, d) such that if A1,... , Am ⊂ Rd are

convex sets, m ≥ p and out of every p sets Ai1 , . . . , Aip some q sets have a common

point, then some set X of c(p, q, d) points in Rd intersects every set Ai.

Remark: This is a conjecture of H. Hadwiger and M. Debrunner, proved by N.

Alon and D. Kleitman; see [We97] and references therein.

7∗ (Measure of the intersection). Prove that for every d there exists a constant

γ = γ(d) 0 with the following property:

Let A1,... , Am ⊂

Rd

be convex sets. Suppose that m ≥ 2d and that the

intersection of every 2d sets Ai1 , . . . , Ai2d has volume at least 1. Prove that the

intersection A1 ∩ . . . ∩ Am has volume at least γ.

Prove that one can choose γ(d) =

d−2d2

(it is conjectured that the constant

d−2d2

can be improved to

d−αd

for some absolute constant α 0).

Remark: This is a result of I. B´ ar´ any, M. Katchalski and J. Pach; see [E93]

and references therein.