4. Theorems of Radon and Helly 19 Proof. The proof is by induction on m (starting with m = d + 1). Suppose that m d + 1. Then, by the induction hypothesis, for every i = 1, . . . , m there is a point pi in the intersection A1 . . . Ai−1 Ai+1 . . . Am (Ai is missing). Altogether, we have m d + 1 points pi, each of which belongs to all the sets, except perhaps Ai. If two of these points happened to coincide, we get a point which belongs to all the Ai’s. Otherwise, by Radon’s Theorem (Theorem 4.1) there are non-intersecting subsets R = {pi : i I} and B = {pj : j J} such that there is a point p conv(R) conv(B). We claim that p is a common point of A1,... , Am. Indeed, all the points pi : i I of R belong to the sets Ai : i / I. All the points pj : j J of B belong to the sets Aj : j / J. Since the sets Ai are convex, every point from conv(R) belongs to the sets Ai : i / I. Similarly, every point from conv(B) belongs to the sets Aj : j / J. Therefore, p i/I Ai and p j /J Aj. Since I J = ∅, we have p m i=1 Ai and the proof follows. PROBLEMS. 1◦. Show that the theorem does not hold for non-convex sets Ai. 2◦. Construct an example of convex sets Ai in R2, such that every two sets have a common point, but there is no point which would belong to all the sets Ai. 3◦. Give an example of an infinite family {Ai : i = 1, 2, . . . } of convex sets in Rd such that every d+1 sets have a common point but there are no points common to all the sets Ai. The theorem can be extended to infinite families of compact convex sets. (4.3) Corollary. Let {Ai : i I}, |I| d + 1 be a (possibly infinite) family of compact convex sets in Rd such that the intersection of any d +1 sets is not empty: Ai 1 . . . Ai d+1 = ∅. Then the intersection of all the sets Ai is not empty: i∈I Ai = ∅.
Previous Page Next Page