MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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

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

-
Not only there are examples of sets of $(r-1)(d+1)$ points with no Tverberg partition, but every set in sufficiently general position is such an example (by the dimension-counting). So, every condition that lowers the bound in Tverberg's theorem must necessarily be of the form "there is a particular kind of algebraic relation between the points", which does not sound all that natural geometrically. With that said, I do not know any results of this kind. – Boris Bukh Feb 18 2012 at 13:20
This is an excellent problem. Not much is known but there are few conjectures and results, I will try to answer later. – Gil Kalai Jan 31 at 12:33

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-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) The first section of my paper Combinatorics with a Geometric Flavor gives more information and connections.

-
 Dear Gil (and Boris), thanks for your answers. I imagined that more results of this kind would have been proved. Do you know where can I find Kadari's proof? – Arnau Feb 3 at 22:18 Dear Arnau, I am not aware of (but will be happy to lear about) other results directly on your question. Kadari's proof was not published except for his M Sc thesis (in Hebrew). – Gil Kalai Feb 5 at 17:06