Ugrás a tartalomhoz

## Convex Geometry

Csaba Vincze (2013)

University of Debrecen

3.2 Tverberg's theorem

## 3.2 Tverberg's theorem

In this section we discuss a generalization of Radon's lemma. The theorem was first proved in 1966 by Helge Arnulf Tverberg. We present a proof due to Karanbir Sarkaria (Combinatorics and more, http://gilkalai.wordpress.com) based on the colorful Carathéodory's theorem 3.1.

Theorem 3.2.1 Let D be the set consisting of the elements

 ${v}_{1},\mathrm{\dots },{v}_{m}$

in the coordinate space of dimension n. If m is at least

 $\left(r-1\right)\left(n+1\right)+1$

then D can be partitioned into r pairwise disjoint subsets such that their convex hulls intersect each other.

Proof Without loss of generality we can suppose that

 $m=\left(r-1\right)\left(n+1\right)+1.$

Consider the vectors v(1), ..., v(k) as the elements in the coordinate space of dimension n+1 by adding a new coordinate to each vector in such a way that the sum of the coordinates is just one. Let us choose a collection of vectors w(1), ..., w(r) in the coordinate space of dimension r - 1 such that

 ${w}_{1}+\mathrm{\dots }+{w}_{r}=0$ (3.2)

is the only linear relation among them up to a non-zero multiplicative constant and define the tensorial product

 ${v}_{i}\otimes {w}_{j}$

as a matrix

 ${\left(\begin{array}{lllll}{v}_{i}^{1}{w}_{j}^{1}& {v}_{i}^{1}{w}_{j}^{2}& .& .& {v}_{i}^{1}{w}_{j}^{r-1}\\ & & & & \\ {v}_{i}^{2}{w}_{j}^{1}& {v}_{i}^{2}{w}_{j}^{2}& .& .& {v}_{i}^{2}{w}_{j}^{r-1}\\ & & & & \\ .& .& .& .& .\\ .& .& .& .& .\\ .& .& .& .& .\\ & & & & \\ {v}_{i}^{n+1}{w}_{j}^{1}& {v}_{i}^{n+1}{w}_{j}^{2}& .& .& {v}_{i}^{n+1}{w}_{j}^{r-1}\\ & & & & \end{array}\right)}_{\left(n+1\right)×\left(r-1\right)}.$

It can be considered as an element in the coordinate space of dimension d=(n+1)(r - 1). Let

 ${H}_{1}=\left\{{v}_{1}\otimes {w}_{j}|j=1,...,r\right\},$

 ${H}_{2}=\left\{{v}_{2}\otimes {w}_{j}|j=1,...,r\right\},$

 $.$

 $.$

 $.$

 ${H}_{m}=\left\{{v}_{m}\otimes {w}_{j}|j=1,...,r\right\}.$

It can be easily seen that

 $0=\sum _{j=1}^{r}{v}_{i}\otimes {w}_{j}={v}_{i}\otimes \left(\sum _{j=1}^{r}{w}_{j}\right)$

and, consequently, the origin is just the center lying in the convex hulls of H(i)'s. Since m=d+1 the colorful Charathéodory theorem says that

 $0=\sum _{k=1}^{m}{\lambda }_{k}{h}_{k},$ (3.3)

where h(k) is in H(k) for any index k. The partition is realized in the following way:

 ${D}_{1}=\left\{{v}_{k}|{h}_{k}={v}_{k}\otimes {w}_{1}\right\},$

 ${D}_{2}=\left\{{v}_{k}|{h}_{k}={v}_{k}\otimes {w}_{2}\right\},$

 $.$

 $.$

 $.$

 ${D}_{r}=\left\{{v}_{k}|{h}_{k}={v}_{k}\otimes {w}_{r}\right\}.$

We can obviously write equation 3.3 into the form

 $0=\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}{v}_{k}\otimes {w}_{1}+\mathrm{\dots }+\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}{v}_{k}\otimes {w}_{r}.$ (3.4)

If we consider equation 3.4 as a system of equations for the rows of the matrices we have, for example, that

 $0=\left(\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}{v}_{k}^{1}\right){w}_{1}+\mathrm{\dots }+\left(\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}{v}_{k}^{1}\right){w}_{r}.$ (3.5)

In a similar way (for the second row)

 $0=\left(\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}{v}_{k}^{2}\right){w}_{1}+\mathrm{\dots }+\left(\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}{v}_{k}^{2}\right){w}_{r}$ (3.6)

and so on. This means by equation 3.2 that

 ${v}^{j}:=\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}{v}_{k}^{j}=\sum _{{v}_{k}\in {D}_{2}}{\lambda }_{k}{v}_{k}^{j}=\mathrm{\dots }=\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}{v}_{k}^{j}$ (3.7)

for any indices j=1, ..., n+1. Therefore

 $v:=\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}{v}_{k}=\sum _{{v}_{k}\in {D}_{2}}{\lambda }_{k}{v}_{k}=\mathrm{\dots }=\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}{v}_{k}.$ (3.8)

Since the sums of the coordinates of the elements v(1), ..., v(n+1) are one we have that[4]

 ${v}^{1}+\mathrm{\dots }+{v}^{n+1}=:\lambda =\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}=\sum _{{v}_{k}\in {D}_{2}}{\lambda }_{k}=\mathrm{\dots }=\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}.$

On the other hand

 $1=\sum _{{v}_{k}\in {D}_{1}}{\lambda }_{k}+\sum _{{v}_{k}\in {D}_{2}}{\lambda }_{k}+\mathrm{\dots }+\sum _{{v}_{k}\in {D}_{r}}{\lambda }_{k}$

and, consequently, λ=1/r. Finally

 $rv:=\sum _{{v}_{k}\in {D}_{1}}\left(r{\lambda }_{k}\right){v}_{k}=\sum _{{v}_{k}\in {D}_{2}}\left(r{\lambda }_{k}\right){v}_{k}=\mathrm{\dots }=\sum _{{v}_{k}\in {D}_{r}}\left(r{\lambda }_{k}\right){v}_{k},$ (3.9)

where (for example)

 $\sum _{{v}_{k}\in {D}_{1}}\left(r{\lambda }_{k}\right)=r\sum _{{v}_{k}\in {D}_{1}}\left({\lambda }_{k}\right)=r\frac{1}{r}=1.$

Therefore rv is in all the convex hulls conv D(1), conv D(2), ..., conv D(r) as was to be proved. ▮

Excercise 3.2.2 Use the technic of Sarkaria's proof to find the partition of the elements

 ${v}_{1}=\left(1,1\right),{v}_{2}=\left(2,4\right),{v}_{3}=\left(4,6\right),{v}_{4}=\left(6,4\right),{v}_{5}=\left(5,1\right),$

 ${v}_{6}=\left(7,-1\right),{v}_{7}=\left(3,-1\right)$

in the coordinate plane into three disjoint subsets.

Figure 26: A partition into three disjoint subsets.

Hint. First of all note that n=2, r=3 and m=7. Consider the vectors v(1), ..., v(7) as the elements in the coordinate space of dimension 3 by adding a new coordinate to each vector in such a way that the sum of the coordinates is just one:

 ${v}_{1}=\left(1,1,-1\right),{v}_{2}=\left(2,4,-5\right),{v}_{3}=\left(4,6,-9\right),{v}_{4}=\left(6,4,-9\right),$

 ${v}_{5}=\left(5,1,-5\right),{v}_{6}=\left(7,-1,-5\right),{v}_{7}=\left(3,-1,-1\right).$

On the other hand let

 ${w}_{1}=\left(1,0\right),{w}_{2}=\left(0,1\right),{w}_{3}=\left(-1,-1\right).$

We have that

 ${v}_{1}\otimes {w}_{1}=\left(\begin{array}{ll}1& 0\\ 1& 0\\ -1& 0\\ & \end{array}\right),{v}_{1}\otimes {w}_{2}=\left(\begin{array}{ll}0& 1\\ 0& 1\\ 0& -1\\ & \end{array}\right),{v}_{1}\otimes {w}_{3}=\left(\begin{array}{ll}-1& -1\\ -1& -1\\ 1& 1\\ & \end{array}\right)$

are the elements in H(1). In a similar way

 ${v}_{2}\otimes {w}_{1}=\left(\begin{array}{ll}2& 0\\ 4& 0\\ -5& 0\\ & \end{array}\right),{v}_{2}\otimes {w}_{2}=\left(\begin{array}{ll}0& 2\\ 0& 4\\ 0& -5\\ & \end{array}\right),{v}_{1}\otimes {w}_{3}=\left(\begin{array}{ll}-2& -2\\ -4& -4\\ 5& 5\\ & \end{array}\right),$

 ${v}_{3}\otimes {w}_{1}=\left(\begin{array}{ll}4& 0\\ 6& 0\\ -9& 0\\ & \end{array}\right),{v}_{3}\otimes {w}_{2}=\left(\begin{array}{ll}0& 4\\ 0& 6\\ 0& -9\\ & \end{array}\right),{v}_{3}\otimes {w}_{3}=\left(\begin{array}{ll}-4& -4\\ -6& -6\\ 9& 9\\ & \end{array}\right),$

 ${v}_{4}\otimes {w}_{1}=\left(\begin{array}{ll}6& 0\\ 4& 0\\ -9& 0\\ & \end{array}\right),{v}_{4}\otimes {w}_{2}=\left(\begin{array}{ll}0& 6\\ 0& 4\\ 0& -9\\ & \end{array}\right),{v}_{4}\otimes {w}_{3}=\left(\begin{array}{ll}-6& -6\\ -4& -4\\ 9& 9\\ & \end{array}\right),$

 ${v}_{5}\otimes {w}_{1}=\left(\begin{array}{ll}5& 0\\ 1& 0\\ -5& 0\\ & \end{array}\right),{v}_{5}\otimes {w}_{2}=\left(\begin{array}{ll}0& 5\\ 0& 1\\ 0& -5\\ & \end{array}\right),{v}_{5}\otimes {w}_{3}=\left(\begin{array}{ll}-5& -5\\ -1& -1\\ 5& 5\\ & \end{array}\right),$

 ${v}_{6}\otimes {w}_{1}=\left(\begin{array}{ll}7& 0\\ -1& 0\\ -5& 0\\ & \end{array}\right),{v}_{6}\otimes {w}_{2}=\left(\begin{array}{ll}0& 7\\ 0& -1\\ 0& -5\\ & \end{array}\right),{v}_{6}\otimes {w}_{3}=\left(\begin{array}{ll}-7& -7\\ 1& 1\\ 5& 5\\ & \end{array}\right),$

 ${v}_{7}\otimes {w}_{1}=\left(\begin{array}{ll}3& 0\\ -1& 0\\ -1& 0\\ & \end{array}\right),{v}_{5}\otimes {w}_{2}=\left(\begin{array}{ll}0& 3\\ 0& -1\\ 0& -1\\ & \end{array}\right),{v}_{5}\otimes {w}_{3}=\left(\begin{array}{ll}-3& -3\\ 1& 1\\ 1& 1\\ & \end{array}\right)$

are the elements in H(2), ..., H(7), respectively. Observe that

 $0=\frac{5}{24}{v}_{1}\otimes {w}_{1}+\frac{1}{18}{v}_{2}\otimes {w}_{3}+\frac{5}{54}{v}_{3}\otimes {w}_{1}+\frac{1}{6}{v}_{4}\otimes {w}_{2}+\frac{5}{18}{v}_{5}\otimes {w}_{3}+$

 $\frac{4}{27}{v}_{6}\otimes {w}_{1}+\frac{1}{6}{v}_{7}\otimes {w}_{2}$

and the partition is

 ${D}_{1}=\left\{{v}_{1},{v}_{3},{v}_{6}\right\},{D}_{2}=\left\{{v}_{4},{v}_{7}\right\},{D}_{3}=\left\{{v}_{2},{v}_{5}\right\}.$