Colorful Caratheodory Theorem

A couple posts ago, I wrote a post on Radon’s theorem in combinatorial geometry. My goal is ultimately to prove a generalization of Radon’s theorem due to Helge Tverberg and not surprisingly called Tverberg’s theorem. I won’t be presenting Tverberg’s original proof but instead a simpler one due to Karanbir Sarkaria. Sarkaria’s proof of Tverberg’s theorem will make use of a generalization of Carathéodory’s theorem due to I. Bárány and known as the Colorful Carathéodory Theorem (CCT). I did not know about Bárány’s result until coming across it in a post on Gil Kalai’s blog, and my presentation will follow his with a few modifications to accommodate my own mathematical idiosyncrasies.

First, we’ll prove an elementary lemma on projections onto convex, closed subsets of Banach spaces, which will simplify the exposition of the proof of the CCT.

Lemma. Let $C$ be a closed convex subset of a Banach space $X$ . If $x\notin C$ , there exists a unique element $x^{*}\in C$ such that $\left\|x-x^{*}\right\|=d=\inf_{z\in C}\left\|x-z\right\|$ . Moreover, $x^{*}$ is uniquely characterized by the inequality

$\displaystyle\langle{x-x^{*},y-x^{*}}\rangle\leq 0,\indent\forall y\in C$

Proof. For any $z,z'\in C$ , we have by the parallelogram law that

$\begin{array}{lcl}\displaystyle\left\|z-z'\right\|^{2}=\left\|(z-x)+(x-z')\right\|^{2}&=&\displaystyle2\left[\left\|z-x\right\|^{2}+\left\|z'-x\right\|^{2}\right]-\left\|z+z'-2x\right\|^{2}\\&=&\displaystyle 2\left[\left\|z-x\right\|^{2}+\left\|z'-x\right\|^{2}\right]-4\left\|\dfrac{z+z'}{2}-x\right\|^{2}\\&\leq&\displaystyle 2\left[\left\|z-x\right\|^{2}+\left\|z'-x\right\|^{2}\right]-4d^{2},\end{array}$

since $\frac{z+z'}{2}\in C$ by convexity. By definition of infimum, there exists a sequence $(z_{n})_{n=1}^{\infty}$ in $C$ such that $\left\|z_{n}-x\right\|\downarrow d$ . I claim that this sequence is Cauchy and therefore has a limit in $C$ . Indeed, for any $n,m\in\mathbb{Z}^{\geq 1}$ ,

$\displaystyle\left\|z_{n}-z_{m}\right\|^{2}\leq2\left[\left\|z_{n}-x\right\|^{2}+\left\|z_{m}-x\right\|^{2}\right]-4d^{2}\longrightarrow 4d^{2}-4d^{2}=0$

as $n,m\rightarrow\infty$ . Define $x^{*} := \lim_{n \rightarrow\infty}z_{n}$ . It follows from the continuity of the norm that $\left\|y-x\right\|=d$ .

For uniqueness, suppose $y,y'\in C$ satisfy $\left\|y-x\right\|=d=\left\|y'-x\right\|$ . Then

$\displaystyle\left\|y-y'\right\|^{2}\leq 2\left[\left\|y-x\right\|^{2}+\left\|y'-x\right\|^{2}\right]-4d^{2}=2\left[d^{2}+d^{2}\right]-4d^{2}=0$ ,

which implies that $y=y'$ .

Let $y\in C$ with $y\neq x^{*}$ and $t\in [0,1]$ . Then

$\begin{array}{lcl}\displaystyle\left\|x-(x^{*}+t(y-x^{*})\right\|^{2}&=&\displaystyle\left\|x-x^{*}\right\|^{2}-2t\langle{x-x^{*},y-x^{*}}\rangle+t^{2}\left\|y-x^{*}\right\|^{2}\\&=&\displaystyle\left\|x-x^{*}\right\|^{2}+\left\|y-x^{*}\right\|^{2}\left(t-\frac{\langle{x-x^{*},y-x^{*}}\rangle}{\left\|y-x^{*}\right\|^{2}}\right)^{2}-\left|\langle{x-x^{*},y-x^{*}}\rangle\right|^{2}\end{array}$

If $\langle{x-x^{*},y-x^{*}}\rangle>0$ , then there exists a positive $t\in (0,1)$ such that $\left\|x-(x^{*}+t(y-x^{*}))\right\|^{2}<\left\|x-x^{*}\right\|^{2}$ , which contradicts the definition of $x^{*}$ .

Suppose that $x^{**}\in C$ also satisfies the inner product inequality. Then

$\displaystyle0\geq\langle{x-x^{**},x^{*}-x^{**}}\rangle=\underbrace{-\langle{x-x^{*},x^{**}-x^{*}}\rangle}_{\geq 0}+\left\|x^{*}-x^{**}\right\|^{2}$ ,

which implies that $\left\|x^{*}-x^{**}\right\|=0$ . $\Box$

Finally, the Colorful Carathéodory Theorem:

Theorem. (I. Bárány) Let $S_{1},\cdots,S_{d+1}$ be subsets of $\mathbb{R}^{d}$ . If $x\in\text{co}(S_{1})\cap\cdots\cap\text{co}(S_{d+1})$ , then there exist points $x_{1}\in S_{1},\cdots,x_{d+1}\in S_{d+1}$ such that $x\in\text{co}(x_{1},\cdots,x_{d+1})$ .

According to Gil Kalai’s excellent post on the result, it’s called colorful because we can identify the sets $S_{1},\cdots,S_{d+1}$ as colors and interpret the conclusion of the theorem as the point $x$ can be written as a convex combination of a point of each color.

Proof. Suppose that $x\in\text{co}(S_{1})\cap\cdots\cap\text{co}(S_{d+1})$ . By restricting our attention to the points of which $x$ can be written as a convex combination, we may assume that $S_{1},\cdots,S_{d+1}$ are finite sets. Set

$\displaystyle d:=\inf_{{x_{j}\in S_{j}}\atop{1\leq j\leq d+1}}\left\{\left\|x-z\right\|: z\in\text{co}(x_{1},\cdots,x_{d+1})\right\}$

By the projection theorem for closed convex sets, there exists a unique $z\in\text{co}(x_{1},\cdots,x_{d+1})$ , for points $x_{j}\in S_{j}$ , such that $\left\|x-z\right\|=d$ . Suppose that $z\neq x$ and therefore $d>0$ .

Let $H$ denote the hyperplane through $z$ which is orthogonal to the vector $x-z$ (i.e. $H=\left\{y\in\mathbb{R}^{d}:\langle{y,x-z}\rangle=\langle{z,x-z}\rangle\right\}$ . Define closed half-planes by

$\displaystyle H^{-}:=\left\{y\in \mathbb{R}^{d}:\langle{y,x-z}\rangle\leq\langle{z,x-z}\rangle\right\},\indent {H}^{+}:=\left\{y\in\mathbb{R}^{d}:\langle{y,x-z}\rangle\geq \langle{z,x-z}\rangle\right\}$

Since $x\notin S$ , we have that $x$ lies in the interior of $H^{+}$ . By the lemma, we have that $S\subset H^{-}$ . I claim that $z\in\text{co}\left\{x_{i}: 1\leq i\leq d+1,x_{i}\in H\right\}$ . Indeed, since $\langle{x_{i},x-z}\rangle\leq\langle{z,x-z}\rangle$ for all $1\leq i\leq d$ , we obtain that

$\displaystyle\langle{z,x-z}\rangle=\sum_{{1\leq i\leq d+1}\atop{x_{i}\in H}}\langle{\alpha_{i}x_{i},x-z}\rangle+\sum_{{1\leq i\leq d+1}\atop{x_{i}\notin H}}\langle{\alpha_{i}x_{i},x-z}\rangle>\langle{z,x-z}\rangle$ ,

if there exists $x_{i}\in H^{-}\setminus H$ , which is a contradiction. Since $H$ is a $(d-1)$ -dimensional affine subspace, we can apply Carathéodory’s theorem the setting of $\mathbb{R}^{d-1}$ , to obtain that $z$ belongs to the convex hull of $d$ of the $x_{j}$ :

$\displaystyle z\in\text{co}(x_{1},\cdots,x_{j-1},x_{j+1},\cdots,x_{d+1})$

Since $x\in\text{co}(S_{j})$ by hypothesis and $x$ belongs to the interior of $H^{+}$ , we have that $S_{j}\not\subset H^{-}$ and therefore there exists $x'_{j}\in S_{j}$ belonging to the interior of $H^{+}$ . Define the set $S'$ by

$\displaystyle S':=\text{co}(x_{1},\cdots,x_{j-1},x'_{j},x_{j+1},\cdots,x_{d+1})$

Note that both $z,x'_{j}$ are in $S'$ . Since $\langle{x'_{j}-z,x-z}\rangle>0$ , have that

$\displaystyle\langle{tx'_{j}+(1-t)z-z,x-z}\rangle>0\Longleftrightarrow tx'_{j}+(1-t)z\in\text{int}H^{+},\indent\forall t\in(0,1]$

But by the lemma, this implies that $\left\|x-z\right\|>\inf_{z'\in S'}\left\|x-z'\right\|\geq\inf_{z'\in S}\left\|x-z'\right\|$ , which is a contradiction. $\Box$

About these ads

One Response to Colorful Caratheodory Theorem

Pingback: Tverberg’s Theorem (and a Bit of Tensor Products) | Math by Matt