Sarkaria’s Proof of Tverberg’s Theorem 1

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 be points in , . Then there is a partition of such that .  (Such a partition is called a Radon partition.)

Proof: Since the points are affinely dependent. Namely, there are coefficients, not all zero,   such that and . Now we can write and , and note that

(*) ,

and also . This last sum is positive because not all the s are equal to zero. We call it .

To exhibit a convex combination of which is equal to a convex combination in just divide relation (*) by . 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 , , of convex sets in , if every 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 if every of the sets have a point in common then there is a point in common to them all. Let . In words, is a point that belongs to all the s except perhaps to . We assumed that such a point exists for every .

Now we can apply Radon’s theorem: Consider the Radon partition of the points, namely a partition of such that .  Let . Since belongs to the convex hull of   and every for belongs to every for every not in we obtain that belongs to every for not in . By the same argument belongs to every for not in . Since and are disjoint, the point belongs to all 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 , if then for some , .

Like for Radon’s theorem, there is a simple linear algebra proof. We can assume that is finite; we start with a presentation of as a convex combination of vectors in , and if we can use an affine dependency among the vectors in 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 be points in , . Then there is a partition of such that .

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 points in in a “generic” position then for every partition into 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 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 “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 be sets in . Suppose that . Then there are , , such that .

Note that when all the sets are equal we return to Caratheodory’s theorem. (Why is it called colorful? Because we can think of the different s as representing different colors and the conclusion will be that 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 between and where , , . Suppose that realizes this distance, and suppose by contradiction that , i.e., . Write .

Now consider the hyperplane through the point which is perpendicular to the line through and . The point  belongs to the interior of one closed halfspace and we first note that belongs to the other closed halfspace. Indeed, if   was a point in in the interior of then the angle between [] and [] would be less than 90 degrees and a point on the interval [] very close to  would be at a shorter distance from than . This is impossible.

It follows that . By Caratheodory’s theorem (in dimension ),  is in the convex hull of of the s. In other words: , , for some .

Let’s look now at . Is it possible that ? No! This is impossible since . Therefore, there is such that belongs to the interior of . Consider now  . Both and belong to . Since is in the interior of so is the half open interval , and a point on this interval very close to will be closer to than . This is a contradiction. Sababa!

Imre Barany

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