Karanbir Sarkaria
4. Sarkaria’s proof:
Tverberg’s theorem (1965): Let be points in , . Then there is a partition of such that .
Proof: We can assume that . First suppose that the points belong to the -dimensional affine space in of points with the property that the sum of all coordinates is 1. Next consider another -dimensional vector space and vectors in , such that is the only linear relation among the s. (So we can take as the standard basis in and . )
Now we consider the tensor product .
Nothing to be scared of: can be regarded just as the -dimensional vector space of d+1 by matrices. We can define the tensor product of two vectors and , as the (rank-one) matrix .
Consider in U the following sets of points:
…
…
Note that 0 is in the convex hull of every . Indeed it is the sum of the elements in . (And thus . )
By the Colorful Caratheodory Theorem we can choose one point from every so that 0 is in the convex hull of . Therefore,
, where , for every , and .
We can see now how things are unfolding. Suppose that . Write
for .
The required Tverberg partition will be .
To see this we rewrite our last relation as
+ + +
This is a linear relation between d+1 by matrices and if we consider the th row of the matrices and denote by the th coordinate of , we get a linear combination of the form
This is a linear combination between the vectors . But we made an assumption how such a linear combination looks like!
is (up to multiplication by a non-zero real number) the only linear relation among the s.
This means that the expressions are all the same. And therefore,
the vectors are all the same for .
The sum of the coordinates of each is 1. And therefore if we sum all the coordinates for , for any , $we obtain that are all the same (and hence equal ). Multiplying by we get that belongs to the convex hull . Since all the 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 cannot have 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 the two half spaces of affine functionals that are positive on and of affine functionals that are negative on . (So the hyperplane associated to is of those affine functionals which vanish on .) 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 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.
Pingback: Sarkaria’s Proof of Tverberg’s Theorem 1 « Combinatorics and more
Quite a few typos corrected. Thanks Moti!
Pingback: Seven Problems Around Tverberg’s Theorem « Combinatorics and more
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 😉
Dear Ricardo, very nice result! is the pape available on line (on your homepage or arxive)?
I have to update my home page ;(
Done 🙂
Click to access Tverberg-tolerance.pdf
Pingback: Una demostración del teorema de Tverberg « Blog de Pablo
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.
Dear Nitin, yes this is correct!
Pingback: Tverberg’s Theorem (and a Bit of Tensor Products) | Math by Matt
Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more
Pingback: Attila Por’s Universality Result for Tverberg Partitions | Combinatorics and more
Pingback: What is the maximum number of Tverberg’s partitions? | Combinatorics and more