2. Carath´ eodory’s Theorem 11 with fewer terms. Let us consider a system of linear homogeneous equations in m real variables γ1,... , γm: γ1y1 + . . . + γmym = 0 and γ1 + . . . + γm = 0. The first vector equation reads as d real linear equations γ1η1j + . . . + γmηmj = 0 : j = 1, . . . , d in the coordinates ηij of yi: yi = (ηi1, . . . , ηid). Altogether, we have d + 1 linear homogeneous equations in m variables γ1,... , γm. Since m d + 1, there must be a non-trivial solution γ1,... , γm. Since γ1 + . . . + γm = 0, some γi are strictly positive and some are strictly negative. Let τ = min αi/γi : γi 0} = αi 0 /γi 0 . Let αi = αi τγi for i = 1, . . . , m. Then αi 0 for all i = 1, . . . , m and αi 0 = 0. Furthermore, α1 + . . . + αm = (α1 + . . . + αm) τ(γ1 + . . . + γm) = 1 and α1y1 + . . . + αmym = α1y1 + . . . + αmym τ(γ1y1 + . . . + γmym) = x. Therefore, we represented x as a convex combination x = i=i0 αiyi of m 1 points y1,... , yi 0 , . . . , ym (yi 0 omitted). So, if x is a convex combination of m d + 1 points, it can be written as a convex combination of fewer points. Iterating this procedure, we get x as a convex combination of d + 1 (or fewer) points from S. PROBLEMS. 1◦. Show by an example that the constant d + 1 in Carath´ eodory’s Theorem cannot be improved to d. 2∗ (I. ar´ any). Let S1,... , Sd+1 be subsets of Rd. Prove that if u conv(Si)) for each Si, then there exist points vi Si such that u conv ( v1,... , vd+1 . Hint: Choose points vi Si in such a way that the distance from u to conv(v1, . . . , vd+1) is the smallest possible. Prove that if u / conv ( v1,... , vd+1 , the distance could have been decreased further. This result is known as the “Col- ored Carath´ eodory Theorem” see [Bar82]. 3∗. Let S Rd be a set and let u be a point in the interior of conv(S). Prove that one can choose 2d points v1,... , v2d S such that u lies in the interior of conv ( v1,... , v2d ) . 4. Suppose that S Rd is a set such that every two points in S can be connected by a continuous path in S or a union of at most d such sets. Prove that every point u conv(S) is a convex combination of some d points of S. Here is a useful corollary relating convexity and topology.
Previous Page Next Page