Seven Problems Around Tverberg’s Theorem

Posted on December 23, 2008 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. 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$ .

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.

Update: In 2015 the topological Tverberg Conjecture was refuted. See this post.

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

Update: This conjecture was proved when $r+1$ is a prime by Blagojecic Matschke and Ziegler

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.

Update (Apri 2019): Here is a 1999 videotaped lecture that I gave on Invitation to Tverberg’s theorem.

This entry was posted in Combinatorics, Convexity, Open problems and tagged Colorful Tverberg Theorem, topological Tverberg theorem, Tverberg's theorem. Bookmark the permalink.

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

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

Reply
Gil Kalai says:

August 7, 2009 at 12:19 pm

Regarding Conjecture 2, I wonder if configurations where the sum equals zero has some special role. Perhaps the following is true: Start with any configurtion A such that $\sum T_r(A) >0$ , then there is a small perturbation A’ so that $\sum T_r(A')=0$ and $T_r(A') \le T_r(A)$ for every $r$ .

Maybe we can even choose A’ to have the property tht for every partition of the set A, the dimension of intersection of the convex hull of the parts does not increase when we move from A to A’.

Reply
Kristal Cantwell says:

August 7, 2009 at 9:41 pm

There is a problem which I have heard referred to as a Radon relative in which you are given 8 points the problem is to partition them into three sets which form two triangles and a line segment such that the line segment intersects both triangles. As I recall at the time I saw it I thought I could solve it. I don’t know its history or if it is still open or if there is a class of related problems or who originated it.

Reply
Gil says:

August 8, 2009 at 12:53 pm

Kristal, indeed it sounds like a Radon type problem. (There are many, and good references are two survey articles by J Eckhoff.) Where are the 8 points in the plane? in space?

Reply
Kristal Cantwell says:

August 8, 2009 at 6:51 pm

I think one survey article by Eckhoff is in the handbook of convex geometry: Helly, Radon, and Caratheodory type theorems. Where is the other one? The points are in the plane.

Reply
Gil says:

August 8, 2009 at 10:11 pm

Dear Kristal, here is the other: Eckhoff, Jürgen Radon’s theorem revisited. Contributions to geometry (Proc. Geom. Sympos., Siegen, 1978), pp. 164–185, Birkhäuser, Basel-Boston, Mass., 1979.

Reply
Gil Kalai says:

February 15, 2011 at 10:02 am

Two conjectures in the list have now been solved. The colorful Tverberg conjecture (for prime numbers of parts) conjecture was proved by Pavle Blagojecic, Benjamin Matschke, and Guenter Ziegler using topological methods. A counterexample to Eckhoff’s partition conjecture was found by Boris Bukh.

Reply
Gil Kalai says:

April 11, 2011 at 1:56 pm

Let me mention that the following weaker form of the conjecture in question 2 is also open and interesting: For every $A \subset R^d$ , $\sum_{r=1}^{|A|} {\rm dim}~conv (T_r(A)) \ge 0$ .

Reply
Pingback: Some old and new problems in combinatorics and geometry | Combinatorics and more
Pingback: My Mathematical Dialogue with Jürgen Eckhoff | Combinatorics and more
Pingback: From Oberwolfach: The Topological Tverberg Conjecture is False | Combinatorics and more
dinostraurio says:

April 27, 2016 at 8:35 pm

Dear Professor Kalai, Boris’ refutation has been in the arXive since 2010 but never became published… is it really true? had you read it and checked the details your self?
I aks because I don’t think it is correct; the argument, at least, has some holes which I do not know how to fill out… even for the simplest case k=3 is not clear how to build the example…

Reply
- Boris Bukh says:
  
  April 29, 2016 at 3:12 am
  
  This is Boris here: As far as I am aware, the paper is correct. I would very much appreciate reports of any mistakes, either by e-mail or in public here. The paper was accepted subject to me carrying revisions asked by the referee. Besides fixing some typos, these revisions included removal of Sections 3 and 4. I was quite frustrated by these demands. Due to personal reasons, instead of pushing back against these changes then, I let the paper linger. I would still appreciate being informed of the “holes” you mention so that I can either fill them, or withdraw the paper. Thanks.
  
  (GK: Many thanks, Boris, for some technical reason beyond my understanding this comment was swallowed until today (May 10) )
  
  Reply
  - Gil Kalai says:
    
    May 11, 2016 at 6:44 pm
    
    Dear Boris, I feel that this is a rare case that I would have asked the editors to reconsider the referee’s suggestion regarding Sections 3 and 4. (Of course, Sections 3 and 4 also make a lovely separate paper on their own.)
  - dinostraurio says:
    
    July 13, 2016 at 9:35 pm
    
    Hi Boris, sorry for the delay, but for personal reasons I was offline for a while…
    
    First of all, in your definition of nerves, there are some obvious holes: you never define the universe of your sets, however this is not deep and I can guess what you meen in each case. Then, in property (n1) you say that nerves are “downsets”… it is obvious that a Tverberg 3-partition implies three Radon 2-partitions… but, ¿what does it means a 1-partition? ¿is the conv({})≠{}?
    
    On lemma 7, where “the magic is done”, you define X=N and claim that P \subset X, but N \subset 2^P so in the best case, P \element X… So, at least, the proposition as written is not what you claim to prove…
    
    Next, in the counterexample, I was trying to follow the details for k=3 (n=7), the first non-trivial example, but I got nowhere 😦
    In my humble opinion there should be an argument of the following style:
    
    “let X={x1, … ,x7} be 7 arbitrary points and A,B,C an arbitrary 3-partition of X. Then, since bla bla bla, conv(A)\cap conv(B) \cap conv(C) = {}”
    
    … but I cannot see such argument… it may be helpful if you can clarify some questions for this specific example:
    
    ¿how many points does the example has? ¿how many subsets of these are convex?
    
    Finally, I agree with Gil: the other results would do a nice separate paper…
  - Boris Bukh says:
    
    July 20, 2016 at 12:06 pm
    
    Property (N1) does not mention Tverberg partitions at all. It asserts that if we have a collection of convex sets with non-trivial intersection, then any subcollection also has non-trivial intersection. Of course, this is true also without the convexity assumption.
    
    Regarding the number of points: the construction in Lemma 7 creates a convexity space with |N| points where N is the nerve. The nerves in question are HUGE though. More precisely, look at the proof of theorem 2 in Section 2. Let K=3(k-1)+1. There are K of A-families, 3*binom(K,4) B-families and binom(K,2) C-families. We then apply the closure operator (denoted by hat) to each of these families, to obtain A-hat, B-hat, C-hat families. Then N consists of these families and their subfamilies. For example, each C-hat-family has size 2^K-(binom(K,2)-1)-K-1=2^K-K(K+1)/2, and so there are 2^{2^K-K(K+1)/2} subfamilies of each C-hat-family. Each of them gives a point in the resulting convexity space. For k=3, we thus get 2^100 points from each C-set alone. That is a lot of points!
    
    It is very likely that one can significantly reduce the size of these counterexamples. Back when I wrote the paper, I believed I could reduce the number of points somewhat by making the construction somewhat messier, but I saw no way to reduce the number of points to polynomial in k, say.
    
    I hope this answers your questions. Let me know if you have more.
  - Boris Bukh says:
    
    July 21, 2016 at 10:24 am
    
    Upon rereading your question, I realized that I did not answer your question about the inclusion X ⊃ P. Now that I re-read it, I see that I explained it poorly in the proof. Formally, it is incorrect to say that the set X defined by X=N satisfies X ⊃ P. Instead what I should have said (and what is given by the proof) is that there is a subset P’ of X and a bijection between P and P’ such that this bijection induced a bijection between N and N(P’). This bijection is given by the map φ: P -> X constructed in the proof.
    
    To obtain the promised conclusion of the lemma 7, as we can just apply a suitable bijection X->Y to map the pair (X,P’) to a pair (Y,P). (And rename Y to X in the current notation of the Lemma.)
anon says:

May 11, 2016 at 6:26 pm

Removal of sections 3 and 4? Strange, it’s not like the paper is excessively long as it is.

Reply
Pingback: Optimal Colorful Tverberg’s Theorem by Blagojecic, Matschke, and Ziegler | Combinatorics and more
Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more
Pingback: Attila Por’s Universality Result for Tverberg Partitions | Combinatorics and more
Pingback: News on Fractional Helly, Colorful Helly, and Radon | Combinatorics and more
Pingback: What is the maximum number of Tverberg’s partitions? | Combinatorics and more

	Arturo Merino, Torst… on Updates from Cambridge
	ryeguy10 on Updates from Cambridge
	Gil Kalai on Updates from Cambridge
	Gil Kalai on Updates from Cambridge
	Rivki on Updates from Cambridge
	Sandy H on Updates from Cambridge
	ryeguy10 on Updates from Cambridge
	Updates from Cambrid… on Random Circuit Sampling: Fouri…
	Gil Kalai on Random Circuit Sampling: Fouri…
	Gil Kalai on Random Circuit Sampling: Fouri…
	kodlu on Random Circuit Sampling: Fouri…
	kodlu on Random Circuit Sampling: Fouri…