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 , , v m

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

( r - 1 ) ( n + 1 ) + 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 = ( r - 1 ) ( n + 1 ) + 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 + + 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 w j

as a matrix

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 ( n + 1 ) × ( r - 1 ) .

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

H 1 = { v 1 w j | j = 1 , . . . , r } ,

H 2 = { v 2 w j | j = 1 , . . . , r } ,

.

.

.

H m = { v m w j | j = 1 , . . . , r } .

It can be easily seen that

0 = j = 1 r v i w j = v i ( j = 1 r w j )

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 = k = 1 m λ 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 = { v k | h k = v k w 1 } ,

D 2 = { v k | h k = v k w 2 } ,

.

.

.

D r = { v k | h k = v k w r } .

We can obviously write equation 3.3 into the form

0 = v k D 1 λ k v k w 1 + + v k D r λ k v k 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 = ( v k D 1 λ k v k 1 ) w 1 + + ( v k D r λ k v k 1 ) w r .

(3.5)

In a similar way (for the second row)

0 = ( v k D 1 λ k v k 2 ) w 1 + + ( v k D r λ k v k 2 ) w r

(3.6)

and so on. This means by equation 3.2 that

v j : = v k D 1 λ k v k j = v k D 2 λ k v k j = = v k D r λ k v k j

(3.7)

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

v : = v k D 1 λ k v k = v k D 2 λ k v k = = v k D r λ 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 + + v n + 1 = : λ = v k D 1 λ k = v k D 2 λ k = = v k D r λ k .

On the other hand

1 = v k D 1 λ k + v k D 2 λ k + + v k D r λ k

and, consequently, λ=1/r. Finally

r v : = v k D 1 ( r λ k ) v k = v k D 2 ( r λ k ) v k = = v k D r ( r λ k ) v k ,

(3.9)

where (for example)

v k D 1 ( r λ k ) = r v k D 1 ( λ k ) = r 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 = ( 1,1 ) , v 2 = ( 2,4 ) , v 3 = ( 4,6 ) , v 4 = ( 6,4 ) , v 5 = ( 5,1 ) ,

v 6 = ( 7 , - 1 ) , v 7 = ( 3 , - 1 )

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 = ( 1,1 , - 1 ) , v 2 = ( 2,4 , - 5 ) , v 3 = ( 4,6 , - 9 ) , v 4 = ( 6,4 , - 9 ) ,

v 5 = ( 5,1 , - 5 ) , v 6 = ( 7 , - 1 , - 5 ) , v 7 = ( 3 , - 1 , - 1 ) .

On the other hand let

w 1 = ( 1,0 ) , w 2 = ( 0,1 ) , w 3 = ( - 1 , - 1 ) .

We have that

v 1 w 1 = 1 0 1 0 - 1 0 , v 1 w 2 = 0 1 0 1 0 - 1 , v 1 w 3 = - 1 - 1 - 1 - 1 1 1

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

v 2 w 1 = 2 0 4 0 - 5 0 , v 2 w 2 = 0 2 0 4 0 - 5 , v 1 w 3 = - 2 - 2 - 4 - 4 5 5 ,

v 3 w 1 = 4 0 6 0 - 9 0 , v 3 w 2 = 0 4 0 6 0 - 9 , v 3 w 3 = - 4 - 4 - 6 - 6 9 9 ,

v 4 w 1 = 6 0 4 0 - 9 0 , v 4 w 2 = 0 6 0 4 0 - 9 , v 4 w 3 = - 6 - 6 - 4 - 4 9 9 ,

v 5 w 1 = 5 0 1 0 - 5 0 , v 5 w 2 = 0 5 0 1 0 - 5 , v 5 w 3 = - 5 - 5 - 1 - 1 5 5 ,

v 6 w 1 = 7 0 - 1 0 - 5 0 , v 6 w 2 = 0 7 0 - 1 0 - 5 , v 6 w 3 = - 7 - 7 1 1 5 5 ,

v 7 w 1 = 3 0 - 1 0 - 1 0 , v 5 w 2 = 0 3 0 - 1 0 - 1 , v 5 w 3 = - 3 - 3 1 1 1 1

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

0 = 5 24 v 1 w 1 + 1 18 v 2 w 3 + 5 54 v 3 w 1 + 1 6 v 4 w 2 + 5 18 v 5 w 3 +

4 27 v 6 w 1 + 1 6 v 7 w 2

and the partition is

D 1 = { v 1 , v 3 , v 6 } , D 2 = { v 4 , v 7 } , D 3 = { v 2 , v 5 } .