Seven Problems Around Tverberg’s Theorem


Imre Barany, Rade Zivaljevic, Helge Tverberg, and Sinisa Vrecica 

Recall the beautiful theorem of Tverberg: (We devoted two posts (I, II) to its background and proof.)

Tverberg Theorem (1965): Let x_1,x_2,\dots, x_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 (x_i: i \in S_j) \ne \emptyset.

The (much easier) case r=2 of Tverberg’s theorem is Radon’s theorem.


1. Eckhoff’s Partition Conjecture

Eckhoff raised the possibility of finding a purely combinatorial proof of Tverberg’s theorem based on Radon’s theorem. He considered replacing the operation : “taking the convex hull of a set A” by an arbitrary closure operation.

Let X  be a set endowed with an abstract closure operation X \to cl(X). The only requirements of the closure operation are:

(1) cl(cl (X))=cl(X) and

(2) A \subset B implies cl(A) \subset cl (B).

Define t_r(X) to be the largest size of a (multi)set in X which cannot be partitioned into r parts whose closures have a point in common.

Eckhoff’s Partition Conjecture: For every closure operation t_r \le t_2 \cdot (r-1).

If X is the set of subsets of R^d and cl(A) is the convex hull operation then Radon’s theorem asserts that t_2(X)=d+1 and Eckhoff’s partition conjecture would imply Tverberg’s theorem. Update (December 2010): Eckhoff’s partition conjecture was refuted by Boris Bukh. Here is the paper.  

2. The dimension of Tverberg’s points

For a set A, denote by T_r(A) those points in R^d which belong to the convex hull of r pairwise disjoint subsets of X. We call these points Tverberg points of order r.

Conjecture (Kalai, 1974): For every A \subset R^d , \sum_{r=1}^{|A|} {\rm dim} T_r(A) \ge 0.

Continue reading