Gil Kalai’s blog

## Sarkaria’s Proof of Tverberg’s Theorem 1

Posted on November 24, 2008 by

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

### Like this:

This entry was posted in Convexity and tagged Helly type theorems, Tverberg's theorem. Bookmark the permalink.

### 13 Responses to Sarkaria’s Proof of Tverberg’s Theorem 1

1. Pingback: Tverberg’s theorem « Konrad Swanepoel’s blog

2. NH says:

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)”

3. Gil Kalai says:

Thanks, NH! Corrected.

4. Pingback: Seven Problems Around Tverberg’s Theorem « Combinatorics and more

5. a says:

Thanks Gil !!!!
the Ahla, Sababa and Walla are very cute too

6. Pingback: Colloquium at Berlin « Combinatorics and more

7. Pingback: Colorful Caratheodory Revisited « Combinatorics and more

8. Pingback: Radon Related Problem 3 « Euclidean Ramsey Theory

9. Austin says:

In the proof of the Colorful Carathéodory Theorem, is there necessarily some “z” achieving the minimum distance as stated?

I think not, unless we assume that the sets S_i are finite. However, we should be able to do this with no loss of generality: since x is a convex combination of points from S_i (for each i), we may assume S_i to consist of only those points which contribute to that combination. Yes?

10. Gil says:

Right!

11. Phyllis Hazlegrove says:

I found this site from searching on Google and just wanted to say thank you for this interesting webpage on weight loss. Thanks again!

12. Natalya Vivona says:

Thank you very much for the post!
Many guys always have no idea why they couldn’t burn fat or have a better figure. The point is they finding for a magic bullet which brings them what they desire immediately meanwhile all they should do is reading useful posts like this as well as implement the training.

13. Pingback: Colorful Caratheodory Theorem | Math by Matt

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 141, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9167280197143555, "perplexity_flag": "head"}