Sarkaria’s Proof of Tverberg’s Theorem 1

By Gil Kalai

Helge Tverberg

Ladies and gentlemen, this is an excellent time to tell you about the beautiful theorem of Tverberg and the startling proof of Sarkaria to Tverberg’s theorem (two parts). A good place to start is Radon’s theorem.

1. The theorems of Radon, Helly, and Caratheodory.

Radon’s theorem

Radon’s theorem: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ , $m \ge d+2$ . Then there is a partition $S,T$ of $\{1,2,\dots,m\}$ such that $conv(x_i: i \in S) \cap conv(x_i: i \in T)$ $\ne \emptyset$ . (Such a partition is called a Radon partition.)

Proof: Since $m>d+1$ the points $x_1,x_2, \dots, x_m$ are affinely dependent. Namely, there are coefficients, not all zero, $\lambda_1,\lambda_2,\dots,\lambda_m$ such that $\sum _{i=1}^m \lambda_i x_i = 0$ and $\sum _{i=1}^m \lambda_i=0$ . Now we can write $S=\{i:\lambda_i >0\}$ and $T = \{i: \lambda_i \le 0\}$ , and note that

(*) $\sum_{i \in S} \lambda_i x_i = \sum _{i \in T} (-\lambda_i) x_i$ ,

and also $\sum _{i \in S} \lambda_i = \sum_{i \in T} (-\lambda_i)$ . This last sum is positive because not all the $\lambda$ s are equal to zero. We call it $t$ .

To exhibit a convex combination of $x_i: i\in S$ which is equal to a convex combination in $x_i: i \in T$ just divide relation (*) by $t$ . Walla.

This trick of basing a partition on the signs of the coefficients repeats in other proofs. Take note!

Radon used his theorem to prove Helly’s theorem.

Helly’s theorem

Helly’s theorem: For a family $K_1,K_2,\dots, K_n$ , $n \ge d+1$ , of convex sets in $R^d$ , if every $d+1$ of the sets have a point in common then all of the sets have a point in common.

Proof: It is enough to show that when $n> d+1$ if every $n-1$ of the sets have a point in common then there is a point in common to them all. Let $x_k \in \cap\{K_j: 1\le j\le n, j \ne k\}$ . In words, $x_k$ is a point that belongs to all the $K_j$ s except perhaps to $K_k$ . We assumed that such a point $x_k$ exists for every $k$ .

Now we can apply Radon’s theorem: Consider the Radon partition of the points, namely a partition $S,T$ of $\{1,2,\dots,m\}$ such that $conv(x_i: i \in S) \cap conv(x_i: i \in T)$ $\ne \emptyset$ . Let $z \in$ $conv(x_i: i \in S) \cap conv (x_i: i \in T)$ . Since $z$ belongs to the convex hull of $conv (x_i: i \in S)$ and every $x_i$ for $i \in S$ belongs to every $K_j$ for every $j$ not in $S$ we obtain that $z$ belongs to every $K_j$ for $j$ not in $S$ . By the same argument $z$ belongs to every $K_j$ for $j$ not in $T$ . Since $S$ and $T$ are disjoint, the point $z$ belongs to all $K_j$ s. Ahla.

The proof of Helly’s theorem from Radon’s theorem as described on the cover of a book by Steven R. Lay

Caratheodory’s theorem

Caratheodory’s theorem: For $S \subset R^d$ , if $x \in conv (S)$ then $x \in conv (R)$ for some $R \subset S$ , $|R| \le d+1$ .

Like for Radon’s theorem, there is a simple linear algebra proof. We can assume that $S$ is finite; we start with a presentation of $x$ as a convex combination of vectors in $S$ , and if $|S|>d+1$ we can use an affine dependency among the vectors in $S$ to change the convex combination, forcing one coefficient to vanish.

Without further ado here is Tverberg’s theorem.

2. Tverberg’s Theorem

Tverberg Theorem (1965):Let $x_1,x_2,\dots, x_m$ be points in $R^d$ , $m \ge (r-1)(d+1)+1$ . Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset$ .

So Tverberg’s theorem is very similar to Radon’s theorem except that we want more than two parts!

The first thing to note is that Tverberg’s theorem is sharp. If you have only $(r-1)(d+1)$ points in $R^d$ in a “generic” position then for every partition into $r$ parts even the affine spans of the points in the parts will not have a point in common. (It is not entirely easy to prove it; and “generic” should be more than just “in general position.”)

The first proof of this theorem appeared in 1965. It was rather complicated and was based on the idea to first prove the theorem for points in some special position and then show that when you continuously changethe location of the points the theorem remains true. A common dream was to find an extension of the proof of Radon’s theorem, a proof which is based on the two types of numbers - positive and negative. Somehow we need three, four, or $r$ types of numbers. In 1981 Helge Tverberg found yet another proof of his theorem. This proof was inspired by Barany’s proof of the colored Caratheodory theorem (mentioned below) and it was still rather complicated. It once took me 6-7 hours in class to present it.

What could be the probability of hearing two new simple proofs of Tverberg’stheorem on the same day? While visiting the Mittag-Leffler Institute in 1992, I met Helge one day around lunch and he told me about a new proof that he found with Sinisa Vrecica. This is a proof that can be presented in class in 2 hours! It appeared (look here) along with a far-reaching conjecture (still unproved). Later in the afternoon I met Karanbir Sarkaria and he told me about a proof he found to Tverberg’s theorem which was absolutely startling. This is a proof you can present in a one hour lecture; it also somehow goes along with the dream of having $r$ “types” of numbers replacing the role of positive and negative real numbers. Another very simple proof of Tverberg’s theorem was found by Jean-Pierre Roudneff in 1999. (Here is Sarkaria’s homepage.)

3. Colorful Caratheodory

The Colorful Caratheodory Theorem (Barany): Let $S_1, S_2, \dots S_{d+1}$ be $d+1$ sets in $R^d$ . Suppose that $x \in conv(S_1) \cap conv (S_2) \cap conv (S_3) \cap \dots \cap conv (S_{d+1})$ . Then there are $x_1 \in S_1$ , $x_2 \in S_2$ , $\dots x_{d+1} \in S_{d+1}$ such that $x \in conv (x_1,x_2,\dots,x_{d+1})$ .

Note that when all the sets $S_i$ are equal we return to Caratheodory’s theorem. (Why is it called colorful? Because we can think of the different $S_i$ s as representing different colors and the conclusion will be that $x$ is in the convex hull of a set of points containing one point of each color. Indeed, colorful.)

Proof: We will consider the minimum distance $D$ between $x$ and $conv (x_1,x_2,\dots,x_{d+1})$ where $x_1 \in S_1$ , $x_2 \in S_2$ , $\dots x_{d+1} \in S_{d+1}$ . Suppose that $z \in conv (x_1,x_2, \dots, x_{d+1})$ realizes this distance, and suppose by contradiction that $z \ne x$ , i.e., $D>0$ . Write $S = conv (x_1,x_2,\dots,x_{d+1})$ .

Now consider the hyperplane $H$ through the point $z$ which is perpendicular to the line through latex $z$ and $x$ . The point $x$ belongs to the interior of one closed halfspace $H^-$ and we first note that $S$ belongs to the other closed halfspace $H^+$ . Indeed, if $u$ was a point in $S$ in the interior of $H^-$ then the anglebetween [ $u,z$ ] and [ $x,z$ ] would be less than 180 degrees and a point on the interval [ $z,u$ ] very close to $z$ would be at a shorter distance from $x$ than $z$ . This is impossible.

It follows that $z \in conv \{x_i: 1 \le i \le d+1, x_i \in H \}$ . By Caratheodory’s theorem (in dimension $d-1$ ), $z$ is in the convex hull of $d$ of the $x_i$ s. In other words: $z \in conv (x_1,x_2,\dots,x_{j-1}$ , $x_{j+1},\dots,x_{d+1})$ , for some $j$ .

Let’s look now at $S_j$ . Is it possible that $S_j \subset H^+$ ? No! This is impossible since $x \in conv(S_j)$ . Therefore, there is $x'_j \in S_j$ such that $x'_j$ belongs to the interior of $H^-$ . Consider now $S' = conv (\{x_1,x_2,\dots ,x_{j-1},x'_j,x_{j+1},x_{d+1}\})$ . Both $z$ and $x'_j$ belong to $S'$ . Since $x'_j$ is in the interior of $H^-$ so is the half open interval $(z,x'_j]$ , and a point on this interval very close to $z$ will be closer to $x$ than $z$ . This is a contradiction. Sababa!

Imre Barany

The next and last part with Sarkaria’s proof is here.

Tags: Helly type theorems, Tverberg's theorem

This entry was posted on November 24, 2008 at 5:21 pm and is filed under Convexity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

8 Responses to “Sarkaria’s Proof of Tverberg’s Theorem 1”

Tverberg’s theorem « Konrad Swanepoel’s blog Says:
November 26, 2008 at 11:54 am
[...] has a nice explanation of the beautiful theorems of Helly, Radon, Carathéodory, and Tverberg (here and here). I’m looking forward to the next [...]
NH Says:
November 28, 2008 at 7:16 am
Beautiful post, thank you.

Small typo: In the last paragraph, when you say “z \in conv(S_j)”, this should be “x \in conv(S_j)”
Gil Kalai Says:
November 28, 2008 at 10:03 am
Thanks, NH! Corrected.
Seven Problems Around Tverberg’s Theorem « Combinatorics and more Says:
December 23, 2008 at 10:49 pm
[...] the beautiful Theorem of Tverberg: (We devoted two posts (I, II) to its background and [...]
a Says:
December 25, 2008 at 2:04 am
Thanks Gil !!!!
the Ahla, Sababa and Walla are very cute too
Colloquium at Berlin « Combinatorics and more Says:
February 6, 2009 at 2:03 pm
[...] basic relation between Helly, Radon, and Caratheodory’s theorems. Those are described in this post We move to discuss several quantitative generalizations of the theorem. At first we will consider [...]
Colorful Caratheodory Revisited « Combinatorics and more Says:
March 15, 2009 at 11:13 am
[...] Let me just mention the colorful Caratheodory agai. (we discussed it among various Helly-type theorems in the post on Tverberg’s theorem.) [...]
Radon Related Problem 3 « Euclidean Ramsey Theory Says:
September 3, 2009 at 9:55 pm
[...] http://gilkalai.wordpress.com/2008/11/24/sarkarias-proof-of-tverbergs-theorem-1// [...]

Combinatorics and more