Convex Hulls and Topology

Theorem. (Carathéodory’s theorem) Suppose that A \subset X and its convex hull \text{co}(A) has finite dimension m. Then each point x\in\text{co}(A) is the convex combination of at most m+1 points in A.

Proof. For each x \in \text{co}(A), we can write x = \sum_{j=0}^{n}\lambda_{j}x_{j}, where \lambda_{j} > 0 and x_{j} \in A (distinct points). I claim that n\leq m. Suppose n > m. Set B := \left\{x_{0},\cdots,x_{n}\right\}. Then since B \subset A, we have that

\displaystyle\dim(\text{aff}(B)) \leq\dim(\text{aff}(A))=m\leq n-1,

which implies that x_{1} - x_{0},\cdots,x_{n}-x_{0} are linearly dependent in the translated linear space giving \text{aff}(A). Hence, there exist coefficients \alpha_{1},\cdots,\alpha_{n} \in \mathbb{R}, not all zero, such that \sum_{j=1}^{n}\alpha_{j}(x_{j} - x_{0}) = 0. Rearranging, we obtain

\displaystyle0=\underbrace{-\left(\sum_{j=1}^{n}\alpha_{j}\right)}_{:= \alpha_{0}}x_{0}+\sum_{j=1}^{n}\alpha_{j}x_{j}

Observe that \sum_{j=0}^{n}\alpha_{j} = 0, so there exists some k, 0 \leq k \leq n, such that \alpha_{k} > 0. Therefore we can choose t > 0 such that \beta_{j} := \lambda_{j} - t\alpha_{j} \geq 0, for 0 \leq j \leq n, and \beta_{j} = 0 for at least one j. Hence,

\displaystyle x=\sum_{j=0}^{n}\lambda_{j}x_{j}=\sum_{j=0}^{n}(\beta_{j}+t\alpha_{j})x_{j}=\sum_{j=0}^{n}\beta_{j}x_{j}+t\sum_{j=0}^{n}\alpha_{j}x_{j}=\sum_{{j \neq k}}\beta_{j}x_{j},

since \sum_{j=0}^{n}\alpha_{j}x_{j} = 0 by construction. Since \sum_{j=0}^{n}\alpha_{j} = 0, we obtain that

\displaystyle\sum_{j=0}^{n}\beta_{j} = \sum_{j=0}^{n}\lambda_{j} + t\sum_{j=0}^{n}\alpha_{j} = 1,

which implies that x is a convex combination of n-1 points in A. \Box

Lemma. If U is a convex set in a linear normed space, then both \text{int}(U) and \overline{U} are convex.

Proof. Suppose x,y \in \overline{U}. Then there exist sequences (x_{n})_{n=1}^{\infty}, (y_{n})_{n=1}^{\infty} \subset U such that x_{n} \rightarrow x, y_{n} \rightarrow y. For \lambda \in [0,1], we then have that

\displaystyle\lambda x+(1-\lambda) y=\lim_{n\rightarrow\infty }\lambda x_{n}+(1-\lambda)y_{n}\in\overline{U}

To see that \text{int}(U) is convex, let x,y \in U and choose \epsilon > 0 such that u \in B_{\epsilon}(0) \Rightarrow x+u, y+u \in U . Since \text{int} U \subset U, \lambda x + (1-\lambda)y \in U, so that, for u \in B_{\epsilon}(0),

\displaystyle\lambda x+(1-\lambda)y+u=\lambda (x+u)+(1-\lambda)(y+u)\in U,

since x+u,y+u \in U and U is convex by hypothesis. \Box

Lemma. If U is an open set in a linear normed space X, then \text{co}(U) is open. If X is finite dimensional and K \subset X is compact, then \text{co}(K) is compact.

Proof. Let x =\sum_{j=0}^{m}\lambda_{j}x_{j} be the convex combination of points in U. For each j = 0,\cdots,m, there exists r_{j} > 0 such that B_{r_{j}}(x_{j}) \subset U. Choose \epsilon > 0 such that \epsilon \leq \min_{0 \leq j \leq m} x_{j} . For u \in B_{\epsilon}(0), x_{j} + u \in U \ \forall j, and therefore

\displaystyle x+u=\sum_{j=0}^{m}\lambda_{j}x_{j}+\left(\sum_{j=0}^{m}\lambda_{j}\right)u=\sum_{j=0}^{m}\lambda_{j}(x_{j}+u)\in\text{co}(U)

Now suppose that X is a n-dimensional linear normed space and K \subset X is compact. Define a function f by

\begin{array}{lcl}\displaystyle f:\left\{(\lambda_{0},\cdots,\lambda_{n},x_{0},\cdots,x_{n})\in\mathbb{R}^{n+1}\times K^{n+1}:x_{j}\in K,\lambda_{j}\in[0,1], \sum_{j=0}^{n}\lambda_{j}=1\right\}\rightarrow X,\\\displaystyle f(\lambda_{0},\cdots,\lambda_{n},x_{0},\cdots,x_{n}):=\sum_{j=0}^{n}\lambda_{j}x_{j}\end{array}

f is evidently a continuous map, and by Carathéodory’s theorem, the image of f is \text{co}(K). By repeated application of the Bolzano-Weierstrass theorem, we see that the domain of f is compact. Hence, the image of f is compact, which shows that \text{co}(K) is compact. \Box

While the convex hull of an open set is again open, as shown above, the convex hull of a closed subset of a linear normed space need not be closed. Indeed, consider the set in \mathbb{R}^{2} given by E: \left\{(0,0)\right\}\cup\left\{(1,n)\in\mathbb{Z}^{2}: n\geq 0\right\}. It is evident that E^{c} is open, hence E is closed. I claim that

\displaystyle\text{co}(E)=\left\{(x,y)\in\mathbb{R}^{2}: 0\leq x\leq 1, 0\leq y<\infty\right\}\setminus\left\{(0,y)\in\mathbb{R}^{2}: y>0\right\}=:F

To see that F is closed, we show that F^{c} is not open. The point (0,1)\notin F, but for any \epsilon > 0 given, we can choose n\in\mathbb{Z}^{\geq 1} sufficiently large so that \frac{1}{n}<\epsilon and therefore the convex combination

\displaystyle\left|\frac{n-1}{n}(0,0)+\frac{1}{n}(1,n)-(0,1)\right|<\epsilon

We now show that F is convex. Fix (x_{1},y_{1}),(x_{2},y_{2})\in F and let \lambda\in[0,1]. Then

\displaystyle\min\left\{x_{1},x_{2}\right\}\leq\lambda x_{1}+(1-\lambda)x_{2}\leq\max\left\{x_{1},x_{2}\right\},\indent\min\left\{y_{1},y_{2}\right\}\leq\lambda y_{1}+(1-\lambda)y_{2}\leq\max\left\{y_{1},y_{2}\right\}

which implies that \lambda (x_{1},y_{1})+(1-\lambda)(x_{2},y_{2})\in F. Hence, \text{co}(E)\subset F. For the reverse inclusion, fix a convex combination \sum_{k=1}^{n}\lambda_{k}(x_{k},y_{k}). Since x_{k}\in\left\{0,1\right\}, it is immediate that \sum_{k=1}^{n}\lambda_{k}x_{k}\in [0,1]. Analogously,

\displaystyle\sum_{k=1}^{n}\lambda_{k}y_{k}=\sum_{{1\leq k\leq n}\atop{\lambda_{k}\neq 0}}\lambda_{k}y_{k}\geq 0,

with equality if and only if all the \lambda_{k} are zero.

It’s worth mentioning that every closed set in \mathbb{R} has closed convex hull. This result is immediate from an elementary lemma.

Lemma. Let E\subsetneq\mathbb{R} be a nonempty closed, convex subset. Then exactly one of the following holds:

  1. E= [a,b], where -\infty<a\leq b<\infty;
  2. E=(-\infty,b], where -\infty<b<\infty;
  3. E=[a,\infty), where -\infty<a<\infty.

Proof. Fix a nonempty closed, convex subset E\subsetneq\mathbb{R}. Define a:=\inf E and b:=\sup E. Suppose first that E is bounded, so that a and b are both finite. Since E is closed, a\in E and b\in E, so that E=[a.b].

Now suppose that E is unbounded. If a=\inf E is finite, then \sup E=\infty and E=[a,\infty). If b=\sup E is finite, then \inf E=-\infty and E=(-\infty,b]. \Box

It is not a coincidence that we had to consider a closed set whose convex hull was unbounded in order to demonstrate that the convex hull of a closed set need not be closed. Indeed, a consequence of Carathéodory’s theorem is that the convex hull of a compact set K in a finite-dimensional normed space is also compact. Since the Heine-Borel theorem equates compactness with closed and bounded (in finite-dimensional spaces), a closed set E such that \text{co}(E) is not closed is necessarily unbounded.

Advertisements
This entry was posted in math.CA, math.GT and tagged , . Bookmark the permalink.

One Response to Convex Hulls and Topology

  1. Pingback: Helly’s Theorem and Applications | Math by Matt

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s