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
This entry was posted in math.CA, math.CO and tagged . Bookmark the permalink.

One Response to Colorful Caratheodory Theorem

  1. Pingback: Tverberg’s Theorem (and a Bit of Tensor Products) | 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