18.2 Carathéodory’s Theorem

By Theorem 18.1.3, the convex hull of a set $S$ consists of the convex combinations of points of $S$ , with any number of points allowed. For a hundred points in the plane, that description permits a single point of the hull to be an average of all hundred at once. A picture says that this is wasteful: the hundred points spread out into a polygon, the polygon can be cut into triangles with corners among the points, and every point of the polygon lies in one of those triangles, so three points always suffice. This section proves the general statement. In a space of dimension $n$ , every point of a convex hull is a convex combination of at most $n + 1$ points of the set, and the bound cannot be lowered. Two consequences follow. The hull of a compact set is compact, which §08 uses. And from the same counting argument come Radon’s theorem and Helly’s theorem, which describe how convex sets in $\mathbb{R}^n$ can intersect.

As in §01, all spaces are real. Carathéodory’s theorem needs a finite dimension and nothing else; the compactness corollary needs, in addition, a norm, and any norm will do.

18.2.1. When there are too many points

The proof we want has a simple plan. If a point is written as a convex combination of too many points, find a way to shift the weights so that the point stays where it is while one weight falls to zero. That point can then be dropped. Two things are needed: a precise meaning of “too many”, and a way to shift the weights without moving the point.

Both come from one observation. If $\sum_i \lambda_i\mathbf{x}_i = \mathbf{0}$ and $\sum_i \lambda_i = 0$ , then for every real $s$ , $\sum_i (t_i - s\lambda_i)\mathbf{x}_i = \sum_i t_i\mathbf{x}_i \quad\text{and}\quad \sum_i (t_i - s\lambda_i) = \sum_i t_i .$ So the weights $t_i - s\lambda_i$ describe the same point, and they still add up to $1$ . A relation of this shape is what we need a word for.

A list of points is affinely dependent when some combination with coefficients adding to zero, not all of them zero, cancels out.

Definition 18.2.1 (Affine Independence)

Let $V$ be a real vector space and let $(\mathbf{x}_0, \mathbf{x}_1, \dots, \mathbf{x}_m)$ be a list in $V$ , $m \ge 0$ . The list is affinely independent if, for all real $\lambda_0, \dots, \lambda_m$ , $\sum_{i=0}^{m} \lambda_i\mathbf{x}_i = \mathbf{0} \ \text{ and } \ \sum_{i=0}^{m} \lambda_i = 0 \quad\Longrightarrow\quad \lambda_0 = \lambda_1 = \dots = \lambda_m = 0 .$ It is affinely dependent otherwise. A relation $\sum_i \lambda_i\mathbf{x}_i = \mathbf{0}$ with $\sum_i\lambda_i = 0$ and the $\lambda_i$ not all zero is an affine dependence.

In words: this is linear independence (Definition 1.4.1) with one extra hypothesis, that the coefficients add up to zero. The extra hypothesis makes the condition easier to satisfy, and it makes the notion blind to the choice of origin. Translating every point by $\mathbf{p}$ changes $\sum_i\lambda_i\mathbf{x}_i$ by $\bigl(\sum_i\lambda_i\bigr)\mathbf{p} = \mathbf{0}$ , so a translated list is affinely dependent exactly when the original is.

Some small cases:

A single point $(\mathbf{x}_0)$ is always affinely independent: $\lambda_0 = 0$ is forced by the sum condition alone.
Two points $(\mathbf{x}_0, \mathbf{x}_1)$ are affinely dependent exactly when they are equal: the condition forces $\lambda_1 = -\lambda_0$ , and then $\lambda_0(\mathbf{x}_0 - \mathbf{x}_1) = \mathbf{0}$ has a solution $\lambda_0 \ne 0$ if and only if $\mathbf{x}_0 = \mathbf{x}_1$ .
Three collinear points are affinely dependent: $(0, 0), (1, 1), (2, 2)$ satisfy $1 \cdot (0, 0) - 2 \cdot (1, 1) + 1 \cdot (2, 2) = \mathbf{0}$ , with $1 - 2 + 1 = 0$ .

A non-example by minimal change. The list $(\mathbf{0}, \mathbf{e}_1, \mathbf{e}_2)$ in $\mathbb{R}^2$ is affinely independent: the $\mathbf{e}_1$ - and $\mathbf{e}_2$ -coordinates of $\lambda_0\mathbf{0} + \lambda_1\mathbf{e}_1 + \lambda_2\mathbf{e}_2 = \mathbf{0}$ give $\lambda_1 = \lambda_2 = 0$ , and then the sum condition gives $\lambda_0 = 0$ . Move the third point to $2\mathbf{e}_1$ . The list $(\mathbf{0}, \mathbf{e}_1, 2\mathbf{e}_1)$ still spans the same line as $(\mathbf{0}, \mathbf{e}_1)$ , but now $1\cdot\mathbf{0} - 2\mathbf{e}_1 + 1 \cdot (2\mathbf{e}_1) = \mathbf{0}$ with $1 - 2 + 1 = 0$ : the three points have fallen onto one line, and the implication in the definition fails.

Warning. Affine independence is not linear independence. The list $(\mathbf{0}, \mathbf{e}_1, \mathbf{e}_2)$ in $\mathbb{R}^2$ is linearly dependent, since it contains $\mathbf{0}$ , yet it was just shown to be affinely independent. A triangle is an affinely independent list of three points in a two-dimensional space, which linear independence would never allow. That is why the bound in this section is $n + 1$ , and not $n$ . The implication does run one way: a linearly independent list is affinely independent, since an affine dependence is in particular a linear relation with coefficients not all zero.

The next lemma converts affine dependence into linear dependence of differences, which is what allows a dimension count.

Lemma 18.2.1 (Affine Dependence by Differences)

Let $V$ be a real vector space and $\mathbf{x}_0, \dots, \mathbf{x}_m \in V$ .

(a) The list $(\mathbf{x}_0, \dots, \mathbf{x}_m)$ is affinely independent if and only if the list $(\mathbf{x}_1 - \mathbf{x}_0, \dots, \mathbf{x}_m - \mathbf{x}_0)$ is linearly independent.
(b) If $\dim V = n$ , every affinely independent list in $V$ has at most $n + 1$ entries. Equivalently, every list of $n + 2$ or more points of $V$ is affinely dependent.

Idea. The sum condition determines $\lambda_0$ from the other coefficients, and eliminating it turns an affine relation among the points into a linear relation among the differences, and back.

Proof.

(a) Suppose $\sum_{i=0}^{m}\lambda_i\mathbf{x}_i = \mathbf{0}$ and $\sum_{i=0}^{m}\lambda_i = 0$ . Then $\lambda_0 = -\sum_{i \ge 1}\lambda_i$ , and substituting, $\sum_{i=1}^{m} \lambda_i(\mathbf{x}_i - \mathbf{x}_0) = \sum_{i=0}^{m}\lambda_i\mathbf{x}_i = \mathbf{0} .$ Conversely, if $\sum_{i=1}^{m} \lambda_i(\mathbf{x}_i - \mathbf{x}_0) = \mathbf{0}$ , then setting $\lambda_0 = -\sum_{i \ge 1}\lambda_i$ gives an affine relation $\sum_{i=0}^{m}\lambda_i\mathbf{x}_i = \mathbf{0}$ with $\sum_{i=0}^{m}\lambda_i = 0$ . These two passages are inverse to each other, and $(\lambda_0, \dots, \lambda_m)$ is not all zero exactly when $(\lambda_1, \dots, \lambda_m)$ is not all zero, because $\lambda_0$ is determined by the others. So affine dependences of the points correspond to linear relations, not all zero, among the differences, and one exists exactly when the other does.
(b) If $(\mathbf{x}_0, \dots, \mathbf{x}_m)$ is affinely independent, then by (a) the $m$ differences $\mathbf{x}_i - \mathbf{x}_0$ are linearly independent, so $m \le n$ by Theorem 1.6.3 (a). The list has $m + 1 \le n + 1$ entries.

18.2.2. The theorem

Now the plan can be carried out. The statement is sharper than the count: the points can be taken affinely independent, and the count is a consequence.

Theorem 18.2.2 (Carathéodory’s Theorem)

Let $V$ be a real vector space with $\dim V = n$ , and let $S \subseteq V$ . Every point of $\operatorname{conv} S$ is a convex combination of an affinely independent list of points of $S$ . In particular, every point of $\operatorname{conv} S$ is a convex combination of at most $n + 1$ points of $S$ .

Idea. Count, then drop a point. Write $\mathbf{x}$ with as few points as possible, so that every weight is positive. If the points were affinely dependent, the weights $t_i - s\lambda_i$ would describe the same $\mathbf{x}$ for every $s$ . Start at $s = 0$ and increase $s$ . The weights with $\lambda_i > 0$ decrease, and there is at least one of these, because the $\lambda_i$ add up to zero without all being zero. Stop at the first moment a weight reaches $0$ : all the weights are still $\ge 0$ , and one point has become unnecessary. That contradicts minimality.

Proof. Let $\mathbf{x} \in \operatorname{conv} S$ . By Theorem 18.1.3, $\mathbf{x}$ is a convex combination of finitely many points of $S$ . Among all ways of writing it so, choose one, $\mathbf{x} = \sum_{i=0}^{m} t_i\mathbf{x}_i , \qquad \mathbf{x}_i \in S,\ \ (t_0, \dots, t_m) \in \Delta_{m+1} ,$ with the number $m + 1$ of points as small as possible. Then every $t_i > 0$ : a zero weight could be deleted, and the remaining weights would still be non-negative and add up to $1$ , giving a shorter expression.

Suppose, for a contradiction, that $(\mathbf{x}_0, \dots, \mathbf{x}_m)$ is affinely dependent, and let $\sum_i\lambda_i\mathbf{x}_i = \mathbf{0}$ , $\sum_i\lambda_i = 0$ be an affine dependence. The $\lambda_i$ are not all zero and add up to $0$ , so at least one of them is positive. Put $s = \min\Bigl\{ \frac{t_i}{\lambda_i} : \lambda_i > 0 \Bigr\} ,$ a minimum over a non-empty finite set, and let $j$ be an index where it is attained; $s > 0$ since each $t_i > 0$ . Define $t_i' = t_i - s\lambda_i$ . Then:

$t_i' \ge 0$ for every $i$ . If $\lambda_i \le 0$ , then $t_i' \ge t_i > 0$ , since $s > 0$ . If $\lambda_i > 0$ , then $s \le t_i/\lambda_i$ by the choice of $s$ , so $s\lambda_i \le t_i$ .
$t_j' = t_j - (t_j/\lambda_j)\lambda_j = 0$ .
$\sum_i t_i' = \sum_i t_i - s\sum_i\lambda_i = 1$ and $\sum_i t_i'\mathbf{x}_i = \sum_i t_i\mathbf{x}_i - s\sum_i\lambda_i\mathbf{x}_i = \mathbf{x}$ .

So $\mathbf{x}$ is a convex combination of the $m$ points $\mathbf{x}_i$ , $i \ne j$ , contradicting the minimality of $m + 1$ . Hence $(\mathbf{x}_0, \dots, \mathbf{x}_m)$ is affinely independent. By Lemma 18.2.1 (b) it has at most $n + 1$ entries. This proves the theorem.

In the plane, then, every point of the hull of any set $S$ lies in a triangle whose corners are points of $S$ , possibly a degenerate one (a segment or a single point). In $\mathbb{R}^3$ it lies in a tetrahedron with corners in $S$ . The proof is constructive: given any convex combination, it says how to shorten it, one point at a time.

Example (Dropping a point in the plane)

In $\mathbb{R}^2$ let $\mathbf{x}_0 = (0, 0)$ , $\mathbf{x}_1 = (3, 0)$ , $\mathbf{x}_2 = (0, 3)$ , $\mathbf{x}_3 = (2, 2)$ , and let $\mathbf{x} = \tfrac14(\mathbf{x}_0 + \mathbf{x}_1 + \mathbf{x}_2 + \mathbf{x}_3) = (\tfrac54, \tfrac54)$ . Write $\mathbf{x}$ as a convex combination of three of these points by the method of the proof.

Solution. Four points in $\mathbb{R}^2$ are affinely dependent by Lemma 18.2.1 (b). To find a dependence, solve $\sum_i \lambda_i\mathbf{x}_i = \mathbf{0}$ and $\sum_i\lambda_i = 0$ : the two coordinate equations read $3\lambda_1 + 2\lambda_3 = 0$ and $3\lambda_2 + 2\lambda_3 = 0$ . Taking $\lambda_3 = 3$ gives $\lambda_1 = \lambda_2 = -2$ , and then $\lambda_0 = -(\lambda_1 + \lambda_2 + \lambda_3) = 1$ . Check: $1\cdot(0,0) - 2(3,0) - 2(0,3) + 3(2,2) = (-6 + 6, -6 + 6) = \mathbf{0}$ , and $1 - 2 - 2 + 3 = 0$ .

The positive coefficients are $\lambda_0 = 1$ and $\lambda_3 = 3$ , with ratios $t_0/\lambda_0 = \tfrac14$ and $t_3/\lambda_3 = \tfrac1{12}$ . So $s = \tfrac1{12}$ , attained at $j = 3$ , and the new weights are $\mathbf{t}' = \bigl(\tfrac14 - \tfrac1{12},\ \tfrac14 + \tfrac2{12},\ \tfrac14 + \tfrac2{12},\ \tfrac14 - \tfrac3{12}\bigr) = \bigl(\tfrac16,\ \tfrac5{12},\ \tfrac5{12},\ 0\bigr) .$ Check: $\tfrac5{12}(3, 0) + \tfrac5{12}(0, 3) = (\tfrac54, \tfrac54) = \mathbf{x}$ , and $\tfrac2{12} + \tfrac5{12} + \tfrac5{12} = 1$ . So $\mathbf{x} = \tfrac16\mathbf{x}_0 + \tfrac5{12}\mathbf{x}_1 + \tfrac5{12}\mathbf{x}_2$ lies in the triangle with corners $\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2$ , and $\mathbf{x}_3$ has been dropped.

The minimum matters. Using the other positive coefficient, $s = \tfrac14$ , would make the weight of $\mathbf{x}_3$ equal to $\tfrac14 - \tfrac34 = -\tfrac12 < 0$ : the point would still be described correctly, but not as a convex combination.

$Diagram. Labels: mathbf x_0, mathbf x_1, mathbf x_2, mathbf x_3 (dropped), mathbf x, mathbf x is an average of all four points,\\ and already lies in the shaded triangle of three$

The bound $n + 1$ cannot be improved, and the standard simplex shows it.

Example (The bound is attained)

In $\mathbb{R}^n$ , let $S = \{\mathbf{0}, \mathbf{e}_1, \dots, \mathbf{e}_n\}$ and let $\mathbf{c} = \tfrac{1}{n+1}(\mathbf{0} + \mathbf{e}_1 + \dots + \mathbf{e}_n) = \tfrac1{n+1}\mathbf{1}$ . Show that $\mathbf{c} \in \operatorname{conv} S$ is not a convex combination of any $n$ points of $S$ .

Solution. The point $\mathbf{c}$ is a convex combination of the $n + 1$ points of $S$ , each with weight $\tfrac1{n+1}$ . A convex combination of $n$ of the points leaves one out. If it leaves out $\mathbf{e}_j$ , the combination is $t_0\mathbf{0} + \sum_{i \ne j} t_i\mathbf{e}_i$ , whose $j$ -th coordinate is $0$ , while $c_j = \tfrac1{n+1} \ne 0$ . If it leaves out $\mathbf{0}$ , the combination is $\sum_i t_i\mathbf{e}_i = (t_1, \dots, t_n)$ , whose coordinates add up to $1$ , while those of $\mathbf{c}$ add up to $\tfrac{n}{n+1} \ne 1$ . Either way it is not $\mathbf{c}$ .

The bound can be far from attained for a particular set, however, and it is worth seeing one.

Example (Two points suffice for a circle)

Let $S = \{\mathbf{x} \in \mathbb{R}^2 : \left\| \mathbf{x} \right\|_2 = 1\}$ be the unit circle. Show that $\operatorname{conv} S$ is the closed unit disc $B_2$ , and that every point of $B_2$ is a convex combination of two points of $S$ .

Solution. $B_2$ is convex (Example (The first convex sets) (d)) and contains $S$ , so $\operatorname{conv} S \subseteq B_2$ by Definition 18.1.4. Conversely, let $(a, b) \in B_2$ , so $a^2 + b^2 \le 1$ , and put $c = \sqrt{1 - a^2}$ , which is real since $\lvert a\rvert \le 1$ . The points $(a, c)$ and $(a, -c)$ lie on $S$ , and $\lvert b\rvert \le c$ because $b^2 \le 1 - a^2$ . With $t = \tfrac{c + b}{2c}$ when $c > 0$ , $t(a, c) + (1-t)(a, -c) = \bigl(a,\ (2t - 1)c\bigr) = (a, b) ,$ and $0 \le t \le 1$ because $-c \le b \le c$ . When $c = 0$ , we have $a = \pm1$ and $b = 0$ , and $(a, b)$ is itself a point of $S$ . So every point of the disc lies on a vertical chord of the circle, and $B_2 \subseteq \operatorname{conv} S$ by Theorem 18.1.3.

Quick check. A point of $\mathbb{R}^3$ is given as a convex combination of seven points of a set $S$ . What is the smallest number of points of $S$ that Theorem 18.2.2 guarantees will suffice? Can one always manage with three?

Solution. Four, since $n + 1 = 4$ for $n = 3$ . Three do not always suffice: by Example (The bound is attained) with $n = 3$ , the point $\tfrac14(1, 1, 1)$ is a convex combination of $\mathbf{0}, \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$ and of no three of them.

Remark. The only place the proof used $\dim V = n$ was the final count, through Lemma 18.2.1 (b), and all that count needs is a space containing the differences of the points. If $S$ lies in an affine subspace of dimension $d$ , then $n + 1$ can be replaced by $d + 1$ ; Exercise (C1: Carathéodory in the affine hull) carries this out. A set of points on a line in $\mathbb{R}^{100}$ needs only two at a time.

18.2.3. The hull of a compact set

The first use of the theorem is a statement about limits. Recall from Corollary 16.2.5 that a subset $K$ of a finite-dimensional real space with a norm is compact if every sequence in $K$ has a subsequence converging to a point of $K$ . Compactness is what lets later sections take a maximum, or a nearest point, over a hull, and it is not obvious that a hull keeps it. A convex combination may use arbitrarily many points, so a sequence of combinations could use more and more of them, and there would be no single compact set of parameters from which to extract a convergent subsequence. Carathéodory’s bound removes that possibility: every point of the hull is described by exactly $n + 1$ points of $K$ and $n + 1$ weights.

Corollary 18.2.3 (The Hull of a Compact Set Is Compact)

Let $V$ be a finite-dimensional real vector space with a norm, and let $K \subseteq V$ be compact.

(a) $\operatorname{conv} K$ is compact.
(b) If $K$ is non-empty, then every linear functional $\varphi$ on $V$ attains a maximum on $\operatorname{conv} K$ , and $\max_{\mathbf{x} \in \operatorname{conv} K} \varphi(\mathbf{x}) = \max_{\mathbf{x} \in K} \varphi(\mathbf{x}) .$

Idea. For (a), write each term of a sequence in $\operatorname{conv} K$ as a combination of exactly $n + 1$ points of $K$ , using Theorem 18.2.2 and padding with zero weights. That turns one sequence into $n + 2$ sequences: one of weight vectors in $\Delta_{n+1}$ , and $n + 1$ of points of $K$ . Extract a convergent subsequence from each in turn, a subsequence of the previous one each time, and pass to the limit in the combination. For (b), a linear functional cannot do better on an average than on the best of the points averaged.

Proof. Let $n = \dim V$ .

(a) If $K = \emptyset$ , then $\operatorname{conv} K = \emptyset$ , which is compact vacuously. Otherwise let $(\mathbf{y}_k)$ be a sequence in $\operatorname{conv} K$ . By Theorem 18.2.2, each $\mathbf{y}_k$ is a convex combination of at most $n + 1$ points of $K$ ; repeating one of those points with weight $0$ if necessary, we may write $\mathbf{y}_k = \sum_{i=0}^{n} t_{k,i}\,\mathbf{x}_{k,i} , \qquad \mathbf{x}_{k,i} \in K,\ \ \mathbf{t}_k = (t_{k,0}, \dots, t_{k,n}) \in \Delta_{n+1} .$
Step 1: the weights. $\Delta_{n+1}$ is closed in $\mathbb{R}^{n+1}$ by Proposition 18.1.6 (b), (c), and bounded, since each coordinate of a point of it lies in $[0, 1]$ . By the compactness of closed bounded sets in $\mathbb{R}^{n+1}$ , fact (A3) of Chapter 16’s introduction, some subsequence of $(\mathbf{t}_k)$ converges to a point $\mathbf{t} = (t_0, \dots, t_n) \in \Delta_{n+1}$ . In particular $t_{k,i} \to t_i$ along it for each $i$ , since $\lvert t_{k,i} - t_i\rvert \le \left\| \mathbf{t}_k - \mathbf{t} \right\|_2$ .

Step 2: the points. Along that subsequence, the sequence $(\mathbf{x}_{k,0})$ lies in $K$ , so by compactness of $K$ a further subsequence has $\mathbf{x}_{k,0} \to \mathbf{x}_0 \in K$ . Along it, a further subsequence has $\mathbf{x}_{k,1} \to \mathbf{x}_1 \in K$ , and so on through $i = n$ . A subsequence of a convergent sequence converges to the same limit, so along the final subsequence, which we index by $k$ again, $\mathbf{t}_k \to \mathbf{t}$ and $\mathbf{x}_{k,i} \to \mathbf{x}_i$ for every $i$ .

Step 3: the limit. Put $\mathbf{y} = \sum_{i=0}^{n} t_i\mathbf{x}_i$ , which lies in $\operatorname{conv} K$ by Theorem 18.1.3. By (N3) and (N2) of Definition 16.1.1, along the final subsequence, $\begin{aligned} \left\| \mathbf{y}_k - \mathbf{y} \right\| &\le \sum_{i=0}^{n} \left\| t_{k,i}\mathbf{x}_{k,i} - t_i\mathbf{x}_i \right\| \\ &\le \sum_{i=0}^{n} \Bigl(\lvert t_{k,i} - t_i\rvert\,\left\| \mathbf{x}_{k,i} \right\| + t_i\left\| \mathbf{x}_{k,i} - \mathbf{x}_i \right\|\Bigr) , \end{aligned}$ where the second line writes $t_{k,i}\mathbf{x}_{k,i} - t_i\mathbf{x}_i = (t_{k,i} - t_i)\mathbf{x}_{k,i} + t_i(\mathbf{x}_{k,i} - \mathbf{x}_i)$ . Each $\left\| \mathbf{x}_{k,i} \right\| \le \left\| \mathbf{x}_i \right\| + \left\| \mathbf{x}_{k,i} - \mathbf{x}_i \right\|$ is bounded, since the last term tends to $0$ . So every term on the right tends to $0$ , and $\mathbf{y}_k \to \mathbf{y} \in \operatorname{conv} K$ along the subsequence. Hence $\operatorname{conv} K$ is compact.
(b) By Lemma 18.1.5, $\varphi$ is continuous. By the extreme value theorem, fact (A4) of Chapter 16’s introduction, applied to $\varphi$ on the non-empty compact set $K$ , there is $\mathbf{x}^{\ast} \in K$ with $\varphi(\mathbf{x}) \le M = \varphi(\mathbf{x}^{\ast})$ for every $\mathbf{x} \in K$ . Now let $\mathbf{y} = \sum_i t_i\mathbf{x}_i$ be any point of $\operatorname{conv} K$ , with $\mathbf{x}_i \in K$ and $\mathbf{t} \in \Delta_m$ (Theorem 18.1.3). By linearity, and since every $t_i \ge 0$ , $\varphi(\mathbf{y}) = \sum_i t_i\varphi(\mathbf{x}_i) \le \sum_i t_iM = M .$ So $M$ bounds $\varphi$ on $\operatorname{conv} K$ , and it is attained there, at $\mathbf{x}^{\ast} \in K \subseteq \operatorname{conv} K$ . This proves the corollary.

For instance, $\varphi(x, y) = x + 2y$ takes the values $0, 3, 6$ at the corners $(0, 0), (3, 0), (0, 3)$ of the triangle in Example (Dropping a point in the plane); as in the proof of (b), at a point $\sum_i t_i\mathbf{x}_i$ of the triangle it takes the average $3t_1 + 6t_2 \le 6$ of these values, so its maximum over the triangle is $6$ , attained at $(0, 3)$ . At the interior point $\mathbf{x} = (\tfrac54, \tfrac54)$ it takes $\tfrac{15}4 = \tfrac16 \cdot 0 + \tfrac5{12} \cdot 3 + \tfrac5{12} \cdot 6$ , an average of the corner values and so no larger than the largest.

To maximize a linear functional over the hull of finitely many points it is enough to evaluate it at those points (Exercise (B3: Linear functionals on a polygon)). §08 extends this to every compact convex set, and §09 shows that a bounded feasible region of §06 is such a hull.

Warning. The hull of a closed set need not be closed. In $\mathbb{R}^2$ , let $S = \{(0, 1)\} \cup \{(x, 0) : x \in \mathbb{R}\}$ , a point together with a line. $S$ is closed, by Proposition 18.1.6 (b), (c). Its hull is $\operatorname{conv} S = \{(x, y) : 0 \le y < 1\} \cup \{(0, 1)\} .$ Indeed a convex combination of points of $S$ with total weight $y$ on $(0, 1)$ has second coordinate $y$ , and when $y < 1$ any first coordinate $x$ is reached, as $y(0,1) + (1-y)\bigl(x/(1-y), 0\bigr) = (x, y)$ ; when $y = 1$ all the weight is on $(0, 1)$ . The points $(1, 1 - 1/k)$ lie in $\operatorname{conv} S$ and converge to $(1, 1)$ , which does not. So compactness in Corollary 18.2.3 cannot be weakened to closedness: here $S$ is closed but unbounded, and the hull loses the line $y = 1$ , except for the one point that belongs to $S$ .

18.2.4. Radon’s theorem and Helly’s theorem

The dimension count behind Carathéodory’s theorem says something about intersections of convex sets as well. Its first form is a statement about $n + 2$ points.

Theorem 18.2.4 (Radon’s Theorem)

Let $V$ be a real vector space with $\dim V = n$ , and let $\mathbf{x}_1, \dots, \mathbf{x}_m \in V$ with $m \ge n + 2$ . Then the index set $\{1, \dots, m\}$ can be split into two disjoint non-empty sets $I$ and $J$ with $\operatorname{conv}\{\mathbf{x}_i : i \in I\} \cap \operatorname{conv}\{\mathbf{x}_j : j \in J\} \ne \emptyset .$

Idea. Take an affine dependence and separate its positive coefficients from the rest. Moving the negative terms across the equation gives an equation between a positive combination of some points and a positive combination of the others, with the same total weight on each side, because the coefficients add up to zero. Divide by that total, and each side becomes a convex combination.

Proof. By Lemma 18.2.1 (b), the list $(\mathbf{x}_1, \dots, \mathbf{x}_m)$ is affinely dependent: there are $\lambda_1, \dots, \lambda_m$ , not all zero, with $\sum_i\lambda_i\mathbf{x}_i = \mathbf{0}$ and $\sum_i\lambda_i = 0$ . Let $I = \{i : \lambda_i > 0\}$ and $J = \{j : \lambda_j \le 0\}$ , which are disjoint with union $\{1, \dots, m\}$ . Since the $\lambda_i$ add up to $0$ and are not all zero, some $\lambda_i$ is positive and some is negative, so neither $I$ nor $J$ is empty. Put $\sigma = \sum_{i \in I}\lambda_i > 0$ ; then $\sum_{j \in J}(-\lambda_j) = \sigma$ as well, since the total is $0$ . Moving the terms indexed by $J$ across and dividing by $\sigma$ , $\mathbf{y} \mathrel{:=} \sum_{i \in I} \frac{\lambda_i}{\sigma}\,\mathbf{x}_i = \sum_{j \in J} \frac{-\lambda_j}{\sigma}\,\mathbf{x}_j .$ On the left the coefficients are positive and add up to $1$ ; on the right they are $\ge 0$ and add up to $1$ . So $\mathbf{y}$ lies in both hulls, by Theorem 18.1.3. This proves the theorem.

A partition as in the theorem is a Radon partition. In the plane, four points in general position (no three on a line) either have one inside the triangle of the other three, or they form a quadrilateral whose two diagonals cross; Exercise (B2: Radon partitions in the plane) finds the partition in each case. The count $n + 2$ cannot be lowered: the $n + 1$ points $\mathbf{0}, \mathbf{e}_1, \dots, \mathbf{e}_n$ have no Radon partition (Exercise (C3: The counts are sharp)).

Helly’s theorem turns the counting around. Instead of asking how many points a hull needs, it asks how many sets of a family must be checked to know that all of them have a common point. Checking pairs is not enough, since three lines in the plane can meet pairwise in three different points; checking triples in the plane is.

Theorem 18.2.5 (Helly’s Theorem)

Let $V$ be a real vector space with $\dim V = n$ , and let $C_1, \dots, C_m$ be convex subsets of $V$ , with $m \ge n + 1$ . If every $n + 1$ of the sets have a point in common, then all $m$ of them have a point in common.

Idea. Induction on the number of sets. Given $m \ge n + 2$ sets, the inductive hypothesis provides, for each $i$ , a point $\mathbf{x}_i$ lying in every set except possibly $C_i$ . That is $m \ge n + 2$ points, so Radon’s theorem splits them into two groups whose hulls meet at some $\mathbf{y}$ . Any one set $C_k$ misses at most one point, $\mathbf{x}_k$ , and that point lies in only one of the two groups; the other group lies entirely in $C_k$ , and so does its hull, which contains $\mathbf{y}$ .

Proof. We use induction on $m$ . For $m = n + 1$ , the hypothesis applied to all $m$ sets is the conclusion. Let $m \ge n + 2$ , and suppose the theorem holds for families of $m - 1$ convex sets. For each $i = 1, \dots, m$ , the family $\{C_k : k \ne i\}$ has $m - 1 \ge n + 1$ members, and every $n + 1$ of them have a common point by hypothesis. By the inductive hypothesis, there is a point $\mathbf{x}_i$ with $\mathbf{x}_i \in C_k \quad\text{for every } k \ne i .$ Since $m \ge n + 2$ , Theorem 18.2.4 splits $\{1, \dots, m\}$ into disjoint non-empty sets $I$ , $J$ and gives a point $\mathbf{y} \in \operatorname{conv}\{\mathbf{x}_i : i \in I\} \cap \operatorname{conv}\{\mathbf{x}_j : j \in J\}$ .

Fix $k \in \{1, \dots, m\}$ . If $k \in I$ , then $k \notin J$ , so every $\mathbf{x}_j$ with $j \in J$ lies in $C_k$ . Since $C_k$ is convex, Lemma 18.1.2 puts every convex combination of these points in $C_k$ , so $\operatorname{conv}\{\mathbf{x}_j : j \in J\} \subseteq C_k$ by Theorem 18.1.3, and in particular $\mathbf{y} \in C_k$ . If $k \in J$ , the same argument with $I$ in place of $J$ gives $\mathbf{y} \in C_k$ . Hence $\mathbf{y}$ lies in every $C_k$ . This completes the induction.

Example (Helly’s proof run on four half-planes)

In $\mathbb{R}^2$ , let $\begin{aligned} C_1 &= \{y \ge 0\}, & C_2 &= \{x \ge 0\}, \\ C_3 &= \{x + y \le 2\}, & C_4 &= \{x - y \le 1\}. \end{aligned}$ Find points $\mathbf{x}_i$ in all the sets except $C_i$ , and follow the proof of Theorem 18.2.5 to a common point of all four.

Solution. Here $n = 2$ and $m = 4 = n + 2$ , so the proof applies Radon’s theorem (Theorem 18.2.4) to four points. The following points lie in every set except their own, as substitution into the four inequalities shows: $\mathbf{x}_1 = (0, -1), \quad \mathbf{x}_2 = (-1, 0), \quad \mathbf{x}_3 = (2, 2), \quad \mathbf{x}_4 = (2, 0) .$ For instance, $\mathbf{x}_1$ has $x = 0 \ge 0$ , $x + y = -1 \le 2$ , $x - y = 1 \le 1$ , and $y = -1 < 0$ violates $C_1$ . And $\mathbf{x}_4$ has $y = 0$ , $x = 2$ , $x + y = 2$ , and $x - y = 2 > 1$ violates $C_4$ .

An affine dependence: the equations $\sum_i\lambda_i\mathbf{x}_i = \mathbf{0}$ , $\sum_i\lambda_i = 0$ are satisfied by $\boldsymbol{\uplambda} = (-6, 4, -3, 5)$ . Check: the first coordinates give $-4 - 6 + 10 = 0$ , the second $6 - 6 + 0 = 0$ , and $-6 + 4 - 3 + 5 = 0$ . The positive coefficients are at $I = \{2, 4\}$ , with $\sigma = 9$ , so $\mathbf{y} = \tfrac49\mathbf{x}_2 + \tfrac59\mathbf{x}_4 = \bigl(\tfrac{-4 + 10}{9}, 0\bigr) = \bigl(\tfrac23, 0\bigr) ,$ and from the other side $\tfrac69\mathbf{x}_1 + \tfrac39\mathbf{x}_3 = \bigl(\tfrac69, \tfrac{-6 + 6}{9}\bigr) = (\tfrac23, 0)$ , as it must be. Finally $\mathbf{y} = (\tfrac23, 0)$ satisfies $y = 0 \ge 0$ , $x = \tfrac23 \ge 0$ , $x + y = \tfrac23 \le 2$ and $x - y = \tfrac23 \le 1$ : it lies in all four half-planes. The proof explains why, without any checking: $C_2$ and $C_4$ contain $\mathbf{x}_1$ and $\mathbf{x}_3$ , hence the segment between them, which contains $\mathbf{y}$ ; and $C_1$ and $C_3$ contain $\mathbf{x}_2$ and $\mathbf{x}_4$ , hence the other segment through $\mathbf{y}$ .

Remark. Helly’s theorem is about finite families, and the finiteness cannot simply be dropped. The closed half-lines $[k, \infty) \subseteq \mathbb{R}$ , for $k = 1, 2, 3, \dots$ , are convex, and any finitely many of them meet (at their largest $k$ ), but no real number lies in all of them. For compact convex sets the infinite version does hold; Exercise (C2: Helly’s theorem for a sequence of compact sets) proves it for a sequence of sets.

With these results the chapter has its combinatorial foundation. §03 turns to geometry: a point outside a closed convex set can be separated from it by a hyperplane.

18.2.5. Exercises

A. Check your understanding

Exercise (A1)

(a) State Theorem 18.2.2.
(b) True or false: every point in the convex hull of ten points of $\mathbb{R}^2$ is a convex combination of three of them. Justify your answer.
(c) True or false: the convex hull of a closed subset of $\mathbb{R}^2$ is closed. Justify your answer.
(d) True or false: any four points of $\mathbb{R}^3$ have a Radon partition. Justify your answer.
(e) Is the list $(\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3)$ in $\mathbb{R}^3$ affinely independent? Is $(\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_1 + \mathbf{e}_2 - \mathbf{e}_3, \mathbf{e}_3)$ ?
(f) Which facts from Chapter 16’s list of imported analysis does Corollary 18.2.3 use, and where?

Solution.

(a) If $\dim V = n$ and $S \subseteq V$ , every point of $\operatorname{conv} S$ is a convex combination of an affinely independent list of points of $S$ , and so of at most $n + 1$ points of $S$ .
(b) True, by Theorem 18.2.2 with $n = 2$ : at most three are needed, and if fewer are used, a point can be added with weight $0$ .
(c) False. The warning in this section gives $S = \{(0, 1)\} \cup \{(x, 0) : x \in \mathbb{R}\}$ , closed, with $(1, 1)$ a limit of points of $\operatorname{conv} S$ not in $\operatorname{conv} S$ .
(d) False. Radon’s theorem (Theorem 18.2.4) needs $n + 2 = 5$ points in $\mathbb{R}^3$ , and four can fail. The points $\mathbf{0}, \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$ are affinely independent, since $\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$ are linearly independent (Lemma 18.2.1 (a)). A point common to the hulls of two disjoint groups of them would give two convex combinations with equal value, and subtracting them gives a relation with coefficients adding up to $0$ and not all zero, which is an affine dependence. So there is no Radon partition; Exercise (C3: The counts are sharp) carries this out for $n + 1$ affinely independent points in general.
(e) Yes: it is linearly independent, and a linearly independent list is affinely independent. The second list is affinely dependent: $\mathbf{e}_1 + \mathbf{e}_2 - (\mathbf{e}_1 + \mathbf{e}_2 - \mathbf{e}_3) - \mathbf{e}_3 = \mathbf{0}$ with coefficients $1, 1, -1, -1$ , which add up to $0$ .
(f) (A3), the compactness of closed bounded sets, for the weights in part (a); and (A4), the extreme value theorem, for the maximum over $K$ in part (b). Part (a) also uses the hypothesis that $K$ is compact, once for each of the $n + 1$ points.

B. Practice

Exercise (B1: Shortening a combination)

In $\mathbb{R}^2$ , let $\mathbf{x}_1 = (0, 0)$ , $\mathbf{x}_2 = (4, 0)$ , $\mathbf{x}_3 = (4, 4)$ , $\mathbf{x}_4 = (0, 4)$ , and $\mathbf{x} = \tfrac1{10}\mathbf{x}_1 + \tfrac2{10}\mathbf{x}_2 + \tfrac3{10}\mathbf{x}_3 + \tfrac4{10}\mathbf{x}_4 .$

(a) Compute $\mathbf{x}$ , and find an affine dependence among $\mathbf{x}_1, \dots, \mathbf{x}_4$ .
(b) Use the method of Theorem 18.2.2 to write $\mathbf{x}$ as a convex combination of three of the points.
(c) Apply the method with the dependence multiplied by $-1$ . Which point is dropped now? Hence $\mathbf{x}$ lies in two different triangles with corners among the $\mathbf{x}_i$ .

Solution.

(a) $\mathbf{x} = \tfrac2{10}(4, 0) + \tfrac3{10}(4, 4) + \tfrac4{10}(0, 4) = (\tfrac{8 + 12}{10}, \tfrac{12 + 16}{10}) = (2, \tfrac{14}5)$ . The corners of a square satisfy $\mathbf{x}_1 - \mathbf{x}_2 + \mathbf{x}_3 - \mathbf{x}_4 = (0 - 4 + 4 - 0, 0 - 0 + 4 - 4) = \mathbf{0}$ , with $1 - 1 + 1 - 1 = 0$ . So $\boldsymbol{\uplambda} = (1, -1, 1, -1)$ .
(b) The positive coefficients are at $\mathbf{x}_1$ and $\mathbf{x}_3$ , with ratios $\tfrac{1/10}{1} = \tfrac1{10}$ and $\tfrac{3/10}{1} = \tfrac3{10}$ . So $s = \tfrac1{10}$ , attained at $\mathbf{x}_1$ , and the new weights are $\mathbf{t} - s\boldsymbol{\uplambda} = (0, \tfrac3{10}, \tfrac2{10}, \tfrac5{10})$ . Check: $\tfrac3{10}(4, 0) + \tfrac2{10}(4, 4) + \tfrac5{10}(0, 4) = (\tfrac{12 + 8}{10}, \tfrac{8 + 20}{10}) = (2, \tfrac{14}5)$ , and the weights add up to $1$ . So $\mathbf{x} \in \operatorname{conv}\{\mathbf{x}_2, \mathbf{x}_3, \mathbf{x}_4\}$ .
(c) With $-\boldsymbol{\uplambda} = (-1, 1, -1, 1)$ , the positive coefficients are at $\mathbf{x}_2$ and $\mathbf{x}_4$ , with ratios $\tfrac2{10}$ and $\tfrac4{10}$ . So $s = \tfrac2{10}$ , attained at $\mathbf{x}_2$ , and the weights become $\mathbf{t} + s\boldsymbol{\uplambda} = (\tfrac3{10}, 0, \tfrac5{10}, \tfrac2{10})$ . Check: $\tfrac5{10}(4, 4) + \tfrac2{10}(0, 4) = (2, \tfrac{20 + 8}{10}) = (2, \tfrac{14}5)$ . Now $\mathbf{x}_2$ is dropped, and $\mathbf{x} \in \operatorname{conv}\{\mathbf{x}_1, \mathbf{x}_3, \mathbf{x}_4\}$ . The two answers are consistent: the triangle with corners $\mathbf{x}_2, \mathbf{x}_3, \mathbf{x}_4$ is the part of the square where $x + y \ge 4$ , the triangle with corners $\mathbf{x}_1, \mathbf{x}_3, \mathbf{x}_4$ is the part where $y \ge x$ , and $(2, \tfrac{14}5)$ satisfies both. The shorter combination produced by Carathéodory’s theorem is not unique; it depends on the dependence used and on its sign.

Exercise (B2: Radon partitions in the plane)

Find a Radon partition, and a point common to the two hulls, for each list of four points in $\mathbb{R}^2$ . Justify your answer.

(a) $(0, 0), (4, 0), (0, 4), (1, 1)$ .
(b) $(0, 0), (3, 1), (1, 3), (4, 4)$ .

Solution. Label the points $\mathbf{x}_1, \dots, \mathbf{x}_4$ in the order given, and follow the proof of Theorem 18.2.4.

(a) The equations $\sum_i\lambda_i\mathbf{x}_i = \mathbf{0}$ , $\sum_i\lambda_i = 0$ read $4\lambda_2 + \lambda_4 = 0$ , $4\lambda_3 + \lambda_4 = 0$ , $\lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 = 0$ . Taking $\lambda_4 = 4$ gives $\lambda_2 = \lambda_3 = -1$ and $\lambda_1 = -2$ . So $I = \{4\}$ , $J = \{1, 2, 3\}$ , $\sigma = 4$ , and $\mathbf{y} = \mathbf{x}_4 = (1, 1) = \tfrac24(0, 0) + \tfrac14(4, 0) + \tfrac14(0, 4) .$ The fourth point lies inside the triangle of the other three.
(b) The equations read $3\lambda_2 + \lambda_3 + 4\lambda_4 = 0$ , $\lambda_2 + 3\lambda_3 + 4\lambda_4 = 0$ , and $\sum_i \lambda_i = 0$ . Subtracting the first two gives $\lambda_2 = \lambda_3$ , and then $4\lambda_2 + 4\lambda_4 = 0$ , so $\lambda_4 = -\lambda_2$ and $\lambda_1 = -\lambda_2 - \lambda_3 - \lambda_4 = -\lambda_2$ . Taking $\lambda_2 = -1$ gives $\boldsymbol{\uplambda} = (1, -1, -1, 1)$ . So $I = \{1, 4\}$ , $J = \{2, 3\}$ , $\sigma = 2$ , and $\mathbf{y} = \tfrac12(0, 0) + \tfrac12(4, 4) = (2, 2) = \tfrac12(3, 1) + \tfrac12(1, 3) .$ The two diagonals of the quadrilateral cross at $(2, 2)$ .

Exercise (B3: Linear functionals on a polygon)

Let $V$ be a finite-dimensional real vector space with a norm, and $\mathbf{x}_1, \dots, \mathbf{x}_m \in V$ .

(a) Prove that $\{\mathbf{x}_1, \dots, \mathbf{x}_m\}$ is compact, and deduce that $P = \operatorname{conv}\{\mathbf{x}_1, \dots, \mathbf{x}_m\}$ is compact.
(b) Prove that every linear functional $\varphi$ on $V$ attains its maximum over $P$ at one of the points $\mathbf{x}_i$ .
(c) Find the maximum and the minimum of $\varphi(x, y) = 2x - y$ over the triangle $\operatorname{conv}\{(1, 0), (3, 1), (0, 2)\}$ of Example (Deciding membership in a triangle).

Solution.

(a) Let $(\mathbf{y}_k)$ be a sequence in the finite set. Some $\mathbf{x}_i$ occurs as $\mathbf{y}_k$ for infinitely many $k$ , since there are only $m$ candidates, and those terms form a constant subsequence, which converges to $\mathbf{x}_i$ , a point of the set. So the set is compact, and $P$ is compact by Corollary 18.2.3 (a).
(b) By Corollary 18.2.3 (b), the maximum of $\varphi$ over $P$ equals its maximum over $\{\mathbf{x}_1, \dots, \mathbf{x}_m\}$ , which is $\max_i\varphi(\mathbf{x}_i)$ , attained at an $\mathbf{x}_i$ with the largest value.
(c) The values at the corners are $\varphi(1, 0) = 2$ , $\varphi(3, 1) = 5$ , $\varphi(0, 2) = -2$ . By (b), the maximum over the triangle is $5$ , at $(3, 1)$ . Applying (b) to $-\varphi$ , the minimum is $-2$ , at $(0, 2)$ .

C. Going deeper

Exercise (C1: Carathéodory in the affine hull)

Let $V$ be a real vector space, $S \subseteq V$ non-empty, and suppose $\operatorname{aff} S$ has dimension $d$ (Definition 18.1.5).

(a) Prove that every affinely independent list of points of $S$ has at most $d + 1$ entries.
(b) Hence prove that every point of $\operatorname{conv} S$ is a convex combination of at most $d + 1$ points of $S$ .
(c) Let $S = \{(t, t, t) : 0 \le t \le 1\} \cup \{(2, 2, 2)\} \subseteq \mathbb{R}^3$ . What bound does Theorem 18.2.2 give, and what bound does (b) give?

Solution.

(a) By Proposition 18.1.4, $\operatorname{aff} S = \mathbf{x}_0 + U$ with $\dim U = d$ . If $(\mathbf{y}_0, \dots, \mathbf{y}_m)$ is an affinely independent list in $S$ , then each $\mathbf{y}_i$ lies in $\mathbf{x}_0 + U$ , so each difference $\mathbf{y}_i - \mathbf{y}_0 = (\mathbf{y}_i - \mathbf{x}_0) - (\mathbf{y}_0 - \mathbf{x}_0)$ lies in $U$ . By Lemma 18.2.1 (a) the $m$ differences are linearly independent, and they lie in the $d$ -dimensional space $U$ , so $m \le d$ by Theorem 1.6.3 (a).
(b) By Theorem 18.2.2, each point of $\operatorname{conv} S$ is a convex combination of an affinely independent list of points of $S$ , which has at most $d + 1$ entries by (a).
(c) Here $n = 3$ , so Theorem 18.2.2 gives $4$ . All of $S$ lies on the line $\operatorname{span}(\mathbf{1})$ , and $S$ contains two distinct points, so $\operatorname{aff} S$ is that line and $d = 1$ ; (b) gives $2$ . Indeed $\operatorname{conv} S$ is the segment from $\mathbf{0}$ to $(2, 2, 2)$ , and each of its points is a convex combination of the two endpoints.

Exercise (C2: Helly’s theorem for a sequence of compact sets)

Let $V$ be a real vector space of dimension $n$ with a norm, and let $C_1, C_2, C_3, \dots$ be a sequence of compact convex subsets of $V$ such that every $n + 1$ of them have a common point.

(a) Prove that a compact set $K$ is closed.
(b) Prove that for each $m \ge 1$ there is a point $\mathbf{y}_m \in C_1 \cap \dots \cap C_m$ .
(c) Prove that $\bigcap_{k \ge 1} C_k \ne \emptyset$ .
(d) Explain where the argument fails for the closed half-lines $[k, \infty)$ of the remark after Theorem 18.2.5.

Hint for (c): all the $\mathbf{y}_m$ lie in $C_1$ .

Solution.

(a) Let $\mathbf{x}_k \to \mathbf{x}$ with $\mathbf{x}_k \in K$ . By compactness, a subsequence converges to some $\mathbf{x}' \in K$ . It also converges to $\mathbf{x}$ , as a subsequence of a convergent sequence, and a limit is unique: $\left\| \mathbf{x} - \mathbf{x}' \right\| \le \left\| \mathbf{x} - \mathbf{x}_{k_j} \right\| + \left\| \mathbf{x}_{k_j} - \mathbf{x}' \right\| \to 0$ , so $\mathbf{x} = \mathbf{x}'$ by (N1). Hence $\mathbf{x} \in K$ .
(b) For $m \le n$ , the sets $C_1, \dots, C_m$ , together with $C_{m+1}, \dots, C_{n+1}$ , are $n + 1$ of the sets, and a common point of all of them lies in $C_1 \cap \dots \cap C_m$ . For $m \ge n + 1$ , Theorem 18.2.5 applies to the convex sets $C_1, \dots, C_m$ .
(c) Every $\mathbf{y}_m$ lies in the compact set $C_1$ , so a subsequence $\mathbf{y}_{m_j}$ converges to some $\mathbf{y}$ . Fix $k$ . For $m_j \ge k$ , $\mathbf{y}_{m_j} \in C_k$ , and $C_k$ is closed by (a); the terms with $m_j \ge k$ form a sequence in $C_k$ converging to $\mathbf{y}$ , so $\mathbf{y} \in C_k$ . As $k$ was arbitrary, $\mathbf{y} \in \bigcap_k C_k$ .
(d) Steps (a) and (b) survive for $C_k = [k, \infty)$ with $n = 1$ : the sets are closed, and $\mathbf{y}_m = m$ lies in the first $m$ of them. Step (c) fails, because $C_1 = [1, \infty)$ is not compact: the sequence $\mathbf{y}_m = m$ has no convergent subsequence, and the points escape to infinity instead of accumulating at a common point.

Exercise (C3: The counts are sharp)

Let $V$ be a real vector space of dimension $n$ , and let $(\mathbf{x}_0, \dots, \mathbf{x}_n)$ be affinely independent.

(a) Prove that each point of $\operatorname{conv}\{\mathbf{x}_0, \dots, \mathbf{x}_n\}$ has exactly one expression $\sum_i t_i\mathbf{x}_i$ with $\mathbf{t} \in \Delta_{n+1}$ .
(b) Deduce that $\frac1{n+1}\sum_i \mathbf{x}_i$ is not a convex combination of any $n$ of the points. (This recovers Example (The bound is attained).)
(c) Prove that $\mathbf{x}_0, \dots, \mathbf{x}_n$ have no Radon partition, so that $n + 2$ in Theorem 18.2.4 cannot be lowered.

Solution.

(a) If $\sum_i t_i\mathbf{x}_i = \sum_i t_i'\mathbf{x}_i$ with $\mathbf{t}, \mathbf{t}' \in \Delta_{n+1}$ , then $\sum_i (t_i - t_i')\mathbf{x}_i = \mathbf{0}$ and $\sum_i (t_i - t_i') = 1 - 1 = 0$ . By affine independence every $t_i - t_i' = 0$ .
(b) The point has the expression with all weights $\tfrac1{n+1}$ . A convex combination of $n$ of the points is an expression of the form in (a) with the omitted point given weight $0$ . By the uniqueness in (a), it would have to coincide with the all- $\tfrac1{n+1}$ expression, which has no zero weight.
(c) Suppose $I, J$ are disjoint, non-empty, and $\sum_{i \in I} a_i\mathbf{x}_i = \sum_{j \in J} b_j\mathbf{x}_j$ with non-negative weights, each family adding up to $1$ . Then $\sum_{i \in I} a_i\mathbf{x}_i - \sum_{j \in J} b_j\mathbf{x}_j = \mathbf{0}$ is a relation among the $\mathbf{x}_i$ whose coefficients add up to $1 - 1 = 0$ ; an index lying in neither set gets coefficient $0$ , and no index lies in both, since $I \cap J = \emptyset$ . By affine independence, all these coefficients are $0$ , so every $a_i = 0$ , contradicting $\sum_{i \in I} a_i = 1$ . Hence no Radon partition exists.