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. ar´ any, M. Katchalski and J. Pach; see [E93]
and references therein.
Previous Page Next Page