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