Sarkaria’s Proof of Tverberg’s Theorem 1

Helge Tverberg

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 \lambdas 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_js 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_js. Ahla.

helly

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_is 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 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 halfspaceH^+. Indeed, if  u was a point in S in the interior of H^- then the angle between [u,z] and [x,z] would be less than 90 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_is. 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!

barany

Imre Barany

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

About these ads
This entry was posted in Convexity and tagged , . Bookmark the permalink.

15 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. I found this site from searching on Google and just wanted to say thank you for this interesting webpage on weight loss. Thanks again!

  11. 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.

  12. Pingback: Colorful Caratheodory Theorem | Math by Matt

  13. marcossarini says:

    Nice summary!

    In the proof of the Colorful Caratheodory, it could start by stating that the sets S_i can be assumed finite, so that the existence of $z$ is clear. Also, the 180 degrees should be 90. Finally, the word “latex” appears where it shouldn’t.

    GK: Many thanks, corrected!

    • taiwo ewuola says:

      Thanks. It is a very nice proof.

      Taiwo.O. EWUOLA, Algebraic Geometry / Combinatorics, Department of Mathematics, University of Ibadan, Ibadan Nigeria.

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