Seven Problems Around Tverberg’s Theorem

By Gil Kalai

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.

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$ .

Note that $\dim \emptyset = -1$ .

This conjecture includes Tverberg’s theorem as a special case: if $|A|=(r-1)(d+1)+1$ , $dim A =d$ , and $T_r (A)=\emptyset$ , then the sum in question is at most $(r-1)d + (|A|-r+1)(-1) = -1$ .

Akiva Kadari proved this conjecture (around 1980, unpublished) for planar configurations.

Akiva Kadari and Ziva Deutsch (both are my academic brothers).

3. The number of Tverberg’s partitions

Sierksma Conjecture: The number of Tverberg’s $r$ -partitions of a set of $(r-1)(d+1)+1$ points in $R^d$ is at least $((r-1)!)^d$ .

Gerard Sierksma

4. The Topological Tverberg Conjecture

Let $f$ be a continuous function from the $m$ -dimensional simplex $\sigma^m$ to $R ^d$ . If $m \ge (d+1)(r-1)$ then there are $r$ pairwise disjoint faces of $\sigma^m$ whose images have a point in common.

If $f$ is a linear function this conjecture reduces to Tverberg’s theorem.

The case $r=2$ was proved by Bajmoczy and Barany using the Borsuk-Ulam theorem. In this case you can replace the simplex by any other polytope of the same dimension. (This can be asked also for the general case.)

The case where $r$ is a prime number was proved in a seminal paper of Barany, Shlosman and Szucs. The prime power case was proved by Ozaydin (unpublished), Volovikov, and Sarkaria. For the prime power case, the proofs are quite difficult and are based on computations of certain characteristic classes.

5. Reay’s Relaxed Tverberg Condition

Moriah Sigron (right) and other participants in a lecture by Endre Szemeredi. (See further comment below.)

Let $t(d,r,k)$ be the smallest integer such that given $m$ points $x_1,x_2,\dots, x_m$ in $R^d$ , $m \ge t(d,r,k)$ there exists a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that every $k$ among the convex hulls $conv (x_i: i \in S_j)$ , $j=1,2,\dots,r$ have a point in common.

Reay’s “relaxed Tverberg conjecture“ asserts that that whenever $k >1$ , $t(d,r,k)= (d+1)(r-1)+1$ .

Micha A. Perles and Moriah Sigron have rather strong results in this direction, but at the same time Perles strongly believes that Reay’s conjecture is false, and he often mentions this special case:

Given 1,000,000 points in $R^{1000}$ , Tverberg’s theorem asserts that you can partition them into 1,000 parts whose convex hulls have a point in common. Now given 999,999 points in $R^{1000}$ is it always possible to divide them to 1,000 parts such that the convex hulls of every two of them will have a point in common? It is hard to believe that the answer is negative.

6. Colorful Tverberg theorems

Zivaljevic and Vrecica’s colorful Tverberg’s theorem asserts the following: Let $C_1,\cdots,C_{d+1}$ be disjoint subsets of $R^d$ , called colors, each of cardinality at least $t$ . A $(d+1)$ -subset $S$ of $\bigcup^{d+1}_{i=1}C_i$ is said to be multicolored if $S\cap C_i\not=\emptyset$ for $i=1,\cdots,d+1$ . Let $r$ be an integer, and let $T(r,d)$ denote the smallest value $t$ such that for every collection of colors $C_1,\cdots,C_{d+1}$ of size at least $t$ there exist $r$ disjoint multicolored sets $S_1,\cdots,S_r$ such that $\bigcap^r_{i=1}{\rm conv}\,(S_i)\not=\emptyset$ . Zivaljevic and Vrecica proved that $T(r,d)\leq 4r-1$ for all $r$ , and $T(r,d)\leq 2r-1$ if $r$ is a prime.

This theorem is one of the highlights of discrete geometry and topological combinatorics. The only known proofs for this theorem rely on topological arguments.

The colorful Tverberg conjecture asserts that $T(r,d)= r$ .

Let me mention another direction of moving from “colorful results” to analogous “matroidal results.” A set whose elements are colored with $r$ colors gives rise to a matroid where the rank of a set is the number of colors of elements in the set. So it is natural to consider an arbitrary matroid structure on the ground set and replace “multicolor set” by “a basis in the matroid”. For example, Barany’s colorful Caratheodory theorem was extended by Meshulam and me to a matroidal theorem. (With Barany and Meshulam we have some preliminary results on matroidal Tverberg theorems.)

7. The computational complexity of Tverberg’s theorem

Problem: Is there a polynomial-time algorithm to find a Tverberg partition when Tverberg’s theorem applies?

A positive answer will follow from a positive answer to:

Problem: Is there a polynomial algorithm for Barany’s colorful Caratheodory theorem?

The picture above (taken by Ofer Arbeli during a lecture by Endre Szemeredi at Hebrew University’s Institute for Advanced Study) shows how encouraging young babies (and even younger) to attend lectures, is instrumental in bringing Israeli mathematics and computer science to its leadership stature.

Tags: Colorful Tverberg Theorem, topological Tverberg theorem, Tverberg's theorem

This entry was posted on December 23, 2008 at 10:48 pm and is filed under Combinatorics, Convexity, Open problems. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Seven Problems Around Tverberg’s Theorem”

D. Eppstein Says:
December 24, 2008 at 5:03 am
There’s also the Tverberg version of halfspace depth, due to Rouseeuw and Hubert. As far as I remember it, it was: given (d+1)n points in R^d, there exists a hyperplane H, and a partition of the points into n subsets such that H cannot be moved to a vertical position without passing through at least one of the points of each subsets.

My co-authors and I had some partial results on this in arXiv:cs.CG/9809037 (DCG 2000) (showing that a partition into n subsets of this type is possible for sets of cn points for some c that is larger than d+1 but smaller than previously known) but as far as I know the full problem is still open.
Gil Kalai Says:
December 24, 2008 at 9:43 am
Thanks David. Let me mention again also the Tverberg-Vrecica conjecture offering a far reaching common extension of Tverberg’s theorem and Ham-sandwitches theorems.

Combinatorics and more