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_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