10 I. Convex Sets at Large Remark: We prove this in Chapter II see Corollary II.4.3. 7∗. Prove that a bounded polyhedron P ⊂ Rd is also a polytope. Remark: We prove this in Chapter IV see Corollary IV.1.3. It seems intuitively obvious that in the space of a small dimension, to represent a given point x from the convex hull of a set A as a convex combination, we would need to use only a few points of A, although their choice will, of course, depend on x. For example, in the plane, to represent x as a convex combination, we need to use only three points see Figure 4. a b c d e u Figure 4. Example: to represent u as a convex combination of a, b, c, d and e, we need only three points, for instance b, e and d. The general fact is known as Carath´ eodory’s Theorem, which was proved by C. Carath´ eodory around 1907. (2.3) Carath´ eodory’s Theorem. Let S ⊂ Rd be a set. Then every point x ∈ conv(S) can be represented as a convex combination of d + 1 points from S: x = α1y1 + . . . + αd+1yd+1, where d+1 i=1 αi = 1, αi ≥ 0 and yi ∈ S for i = 1, . . . , d + 1. Proof. Every point x ∈ conv(S) can be written as a convex combination x = α1y1 + . . . + αmym of some points y1,... , ym ∈ S. We can assume that αi 0 for all i = 1, . . . , m. If m d+1, we can add terms 0y1, say, to get a convex combination with d+1 terms. Suppose that m d + 1. Let us show that we can construct a convex combination

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.