Sarkaria’s Proof of Tverberg’s Theorem 2

By Gil Kalai

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 choose one point $s_i$ from every $S_i$ so that 0 is in the convex hull of $s_1,s_2,\dots, s_m$ . Therefore,

$0 = \sum \lambda_i s_i$ , where $0 \le \lambda_i \le 1$ , for every $i, 1 \le i \le m$ , and $\sum_{i=1}^m \lambda_i=1$ .

We can see now how things are unfolding. Suppose that $s_i = v_i \otimes w_{j_i}$ . Write

$\Omega_k = \{i:j_i=k \}$ for $k=1,2,\dots r$ .

The required Tverberg partition will be $\Omega_1,\Omega_2,\dots, \Omega_r$ .

To see this we rewrite our last relation as

$0 = \sum \{ \lambda_i v_i \otimes w_1 : i \in \Omega_1 \}$ + $\sum \{ \lambda_i v_i \otimes w_2 : i \in \Omega_2 \}$ + $\dots$ + $\sum \{ \lambda_i v_i \otimes w_r : i \in \Omega_r \}.$

This is a linear relation between d+1 by $r-1$ matrices and if we consider the $k$ th row of the matrices and denote by $v_i[k]$ the $k$ th coordinate of $v_i$ , we get a linear combination of the form

$\sum_{j=1}^r \sum \{ \lambda_i v_i[k] : i \in \Omega_j\} w_j = 0$

This is a linear combination between the vectors $w_1,w_2, \dots, w_r$ . But we made an assumption how such a linear combination looks like!

$w_1+w_2+\dots+w_r = 0$ is (up to multiplication by a non-zero real number) the only linear relation among the $w_i$ s.

This means that the $r$ expressions $y_j[k] = \sum \{ \lambda_i v_i[k]: i \in \Omega_j \}$ are all the same. And therefore,

the $r$ vectors $y_j = \sum \{ \lambda_i v_i: i \in \Omega_j \}$ are all the same for $j=1,2,3\dots,r$ .

The sum of the coordinates of each $v_i$ is 1. And therefore if we sum all the coordinates for $y_j$ , for any $j$ , $we obtain that $\sum \{\lambda_i: i \in \Omega_j\}$ are all the same (and hence equal $1/r$ ). Multiplying by $r$ we get that $r\cdot y_j$ belongs to the convex hull $conv \{v_i: i \in \Omega_j\}$ . Since all the $y_j$ s are equal we are done! Sababa.

(The presentation is based on a simplified version by Shmuel Onn of the original one.)

5. Dual versions

Radon’s theorem is equivalent to the following statement: The complement of n+1 linear hyperplanes in $R^n$ cannot have $2^{n+1}$ connected components. In other words, you can choose one open half space for every hyperplane so that their intersection will be empty. (This is one of the most fundamental facts about arrangements of hyperplanes; next comes an easy upper bound for the number of regions in the complement when the number of hyperplanes is arbitrary, and next comes the famous Zaslavsky’s theorem which describes the number of regions as a function of the intersection lattice of the hyperplanes.) To see the connection associate to every $v_i$ the two half spaces of affine functionals that are positive on $v_i$ and of affine functionals that are negative on $v_i$ . (So the hyperplane associated to $v_i$ is of those affine functionals which vanish on $v_i$ .) Now, every non-Radon partition corresponds to a non-empty intersection of such half-spaces.

What about Tverberg’s theorem? Instead of hyperplanes it looks that we have strange objects whose complements have $r$ connected components rather than two. (They look like tropical hyperplanes, any connection?) So Tverberg’s theorem seems to translates to a statement about regions in the complement of several such “hyperplanes”.

Tags: Karanbir Sarkaria, Tverberg's theorem

This entry was posted on November 26, 2008 at 12:50 am and is filed under Convexity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Sarkaria’s Proof of Tverberg’s Theorem 2”

Sarkaria’s Proof of Tverberg’s Theorem 1 « Combinatorics and more Says:
November 28, 2008 at 11:46 pm
[...] and more Gil Kalai’s blog « Bad Advice; An Answer to an Old Trivia Question Sarkaria’s Proof of Tverberg’s Theorem 2 [...]
Gil Kalai Says:
December 9, 2008 at 12:10 am
Quite a few typos corrected. Thanks Moti!
Seven Problems Around Tverberg’s Theorem « Combinatorics and more Says:
December 23, 2008 at 10:53 pm
[...] the beautiful Theorem of Tverberg: (We devoted two posts (I, II) to its background and [...]

Combinatorics and more