Seven Problems Around Tverberg’s Theorem

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

Sarkaria’s Proof of Tverberg’s Theorem 2

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_i$s. (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

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