Seven Problems Around Tverberg’s Theorem

bergen-2005-sinisa-helge-rade-imre

Imre Barany, Rade Zivaljevic, Helge Tverberg, and Sinisa Vrecica 

Recall the beautiful theorem of Tverberg: (We devoted two posts (I, II) to its background and proof.)

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.

The (much easier) case r=2 of Tverberg’s theorem is Radon’s theorem.

 

1. Eckhoff’s Partition Conjecture

Eckhoff raised the possibility of finding a purely combinatorial proof of Tverberg’s theorem based on Radon’s theorem. He considered replacing the operation : “taking the convex hull of a set A” by an arbitrary closure operation.

Let X  be a set endowed with an abstract closure operation X \to cl(X). The only requirements of the closure operation are:

(1) cl(cl (X))=cl(X) and

(2) A \subset B implies cl(A) \subset cl (B).

Define t_r(X) to be the largest size of a (multi)set in X which cannot be partitioned into r parts whose closures have a point in common.

Eckhoff’s Partition Conjecture: For every closure operation t_r \le t_2 \cdot (r-1).

If X is the set of subsets of R^d and cl(A) is the convex hull operation then Radon’s theorem asserts that t_2(X)=d+1 and Eckhoff’s partition conjecture would imply Tverberg’s theorem. Update (December 2010): Eckhoff’s partition conjecture was refuted by Boris Bukh. Here is the paper.  

2. The dimension of Tverberg’s points

For a set A, denote by T_r(A) those points in R^d which belong to the convex hull of r pairwise disjoint subsets of X. We call these points Tverberg points of order r.

Conjecture (Kalai, 1974): For every A \subset R^d , \sum_{r=1}^{|A|} {\rm dim} T_r(A) \ge 0.

Continue reading

Sarkaria’s Proof of Tverberg’s Theorem 2

karanbir 

Karanbir Sarkaria

4. Sarkaria’s proof:

Tverberg’s theorem (1965): Let v_1, v_2,\dots, v_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 (v_i: i \in S_j) \ne \emptyset.

Proof: We can assume that m=(r-1)(d+1)+1. First suppose that the points v_1, v_2,\dots,v_m belong to the d-dimensional affine space H in V=R^{d+1} of points with the property that the sum of all coordinates is 1. Next consider another (r-1)-dimensional vector space W and r vectors in W, w_1,w_2, \dots, w_r  such that w_1+w_2+\dots +w_r = 0  is the only linear relation among the w_is. (So we can take w_1,\dots w_{r-1} as the standard basis in R^{r-1} and w_r=-w_1-w_2-\dots-w_r. )

Now we consider the tensor product V \otimes W.

Nothing to be scared of: U=V \otimes W can be regarded just as the (d+1)(r-1)-dimensional vector space of d+1  by r-1 matrices. We can define the tensor product  x \otimes y of two vectors x = (x_1,x_2,\dots,x_{d+1}) \in V and y =(y_1,y_2,\dots,y_{r-1}) \in W, as the (rank-one) matrix (x_i \cdot y_j)_{1 \le i \le d+1,1 \le j \le r-1}.

Consider in U the following sets of points:

S_1 = \{v_1 \otimes w_j: j=1,2,\dots r \}

S_2 = \{v_2 \otimes w_j: j=1,2,\dots r \}

S_i = \{v_i \otimes w_j: j=1,2,\dots r \}

S_m = \{v_m \otimes w_j: j=1,2,\dots r \}.

Note that 0 is in the convex hull of every S_i. Indeed it is the sum of the elements in S_j. (And thus 0=1/r(v_i \otimes w_1+ v_i \otimes w_2 + \dots + v_i \otimes w_r). )

By the Colorful Caratheodory Theorem we can  Continue reading

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! Continue reading