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 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 kth row of the matrices and denote by v_i[k] the kth 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_is.

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_js 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”.   Update (from February 2011): A dual version for Tverberg’s theorem was described by Raman Sanyal.

 

About these ads
This entry was posted in Convexity and tagged , . Bookmark the permalink.

11 Responses to Sarkaria’s Proof of Tverberg’s Theorem 2

  1. Pingback: Sarkaria’s Proof of Tverberg’s Theorem 1 « Combinatorics and more

  2. Gil Kalai says:

    Quite a few typos corrected. Thanks Moti!

  3. Pingback: Seven Problems Around Tverberg’s Theorem « Combinatorics and more

  4. Ricardo Strausz says:

    Dear Gil, you may find interesting a new generalisation of Tverberg’s theorem that uses also Sarkaria’s ideas. You can find it now in DCG 47(3):455-460 (2012).
    I love this pages of yours ;)

  5. Gil Kalai says:

    Dear Ricardo, very nice result! is the pape available on line (on your homepage or arxive)?

  6. Pingback: Una demostración del teorema de Tverberg « Blog de Pablo

  7. Nitin Vaidya says:

    Nice article. I am new to this topic … from the above proof, it seems to me that Tverberg’s theorem should apply even if the v_i’s are NOT distinct. Is this correct? I am using this theorem to prove correctness of a distributed computing algorithm, and it so happens that the (r-1)(d+1)+1 points I have are not always distinct.

  8. Gil Kalai says:

    Dear Nitin, yes this is correct!

  9. Pingback: Tverberg’s Theorem (and a Bit of Tensor Products) | Math by Matt

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s