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 Ai 1 , . . . , Ai d+1 there is a translate C + u : u Rd of C which intersects all Ai 1 , . . . , Ai d+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 Ai 1 , . . . , Ai d+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 Ai 1 , . . . , Ai p 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 Ai 1 , . . . , Ai 2d 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