Tverberg partitions with less than (r-1)(d+1)+1 points

Question

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $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 bound of $(r-1)(d+1)+1$ in the theorem is sharp because there are point configurations with $(r-1)(d+1)$ points that do not have a Tverberg partition of length $r$.

My question is about lowering this bound by imposing some structure to the points. That is: if we have a full dimensional point configuration $S$ with $m$ points in $R^d$ such that $m\leq(r-1)(d+1)$, can we put conditions on $S$ which still guaratee the existence of a Tverberg partition of length $r$?

Gil Kalai has some very nice posts on the Tverberg Theorem in his blog: http://gilkalai.wordpress.com/2008/11/24/sarkarias-proof-of-tverbergs-theorem-1/ , http://gilkalai.wordpress.com/2008/11/26/sarkarias-proof-of-tverbergs-theorem-2/ and http://gilkalai.wordpress.com/2008/12/23/seven-problems-around-tverbergs-theorem/ .

Answer 1

This is an excellent question but we know very little about such conditions. As Boris Bukh remarked the issue is about points in special positions, because for points in sufficiently general position, even the affine hulls of parts for every partition to r parts will have an empty intersection. However, configurations of points in special positions are of great interest in combinatorial geometry.

Let me start with an example. Suppose you have $2d+2$ points in $R^d$. This is one less than the number of points required to a Tverberg partition with three parts. Of course, one condition that guarantee a Tverberg 3-partition is that all the points (or all the points except one) belongs to a $(d-1)$ dimensional affine space. It is conjectured, more generally, that:

If the dimension of Radon points for a set of $2d+2$ points in $R^d$ is not $d$ then there is a Tevrberg partition to three parts.

The general conjecture in this direction (that I made in 1974) is: 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 $latex X$. We call these points Tverberg points of order $r$.

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

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

Thus, if you have a set of points so that the dimension of (r-1)-Tverberg points is below what can be expected in the generic case, then there is a nonempty Tverberg partition to r parts. There are various strengthening and weakening of this conjecture. It was proved by Kadari (unpublished except his M Sc thesis in Hebrew from the early 90s) for the plane.

There are few more things that can be said:

1) While the computational complexity of finding a Tverberg 3-partition for $2d+3$ points is unknown, the computational complexity of finding a Tverberg 3 partition for less points is NP-hard. As observed by Shmuel Onn 3 edge-colorability of cubic graphs reduces to finding such a Tverberg partition.

2) It will be interesting to come with a topological strengthening of the above conjecture.

3) The conjecture about $2d+2$ points in $R^d$ motivated and is related to the graph-theoretic conjecture (which turned out to be false) in this Overflow question.

4) There are some related questions regarding the $r$-core and intermediate notions. The $r$-core of a set of $n$ points is the intersection of all subsets of $n-r+1$ points. $r$-Tverberg points are contained in the $r$-core. It is natural to ask when is the $r$-core nonempty. (For the Tverberg number te $r$-core is nonempty by a simple application of Helly's theorem.) For a set (or multiset) $X$ of $n$ points in $\mathbb R^d$ and for $i,j$ such that $i+j=r$ we can consider $T[i,j](X)$ the intersection of all Tverberg points for $i$ parts for all subsets of $n-j+1$ points. This is an intermediate notion between the $r$-core and Tverberg points of order $r$.

5) The first section of my paper Combinatorics with a Geometric Flavor gives more information and connections.