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. B´ 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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2002 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.