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: Ai 1 . . . Ai d+1 = ∅. Then all the sets have a common point: A1 . . . Am = ∅.
Previous Page Next Page