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 be a closed convex subset of a Banach space . If , there exists a unique element such that . Moreover, is uniquely characterized by the inequality
Proof. For any , we have by the parallelogram law that
since by convexity. By definition of infimum, there exists a sequence in such that . I claim that this sequence is Cauchy and therefore has a limit in . Indeed, for any ,
as . Define . It follows from the continuity of the norm that .
For uniqueness, suppose satisfy . Then
which implies that .
Let with and . Then
If , then there exists a positive such that , which contradicts the definition of .
Suppose that also satisfies the inner product inequality. Then
which implies that .
Finally, the Colorful Carathéodory Theorem:
Theorem. (I. Bárány) Let be subsets of . If , then there exist points such that .
According to Gil Kalai’s excellent post on the result, it’s called colorful because we can identify the sets as colors and interpret the conclusion of the theorem as the point can be written as a convex combination of a point of each color.
Proof. Suppose that . By restricting our attention to the points of which can be written as a convex combination, we may assume that are finite sets. Set
By the projection theorem for closed convex sets, there exists a unique , for points , such that . Suppose that and therefore .
Let denote the hyperplane through which is orthogonal to the vector (i.e. . Define closed half-planes by
Since , we have that lies in the interior of . By the lemma, we have that . I claim that . Indeed, since for all , we obtain that
if there exists , which is a contradiction. Since is a -dimensional affine subspace, we can apply Carathéodory’s theorem the setting of , to obtain that belongs to the convex hull of of the :
Since by hypothesis and belongs to the interior of , we have that and therefore there exists belonging to the interior of . Define the set by
Note that both are in . Since , have that
But by the lemma, this implies that , which is a contradiction.