What is the maximum number of Tverberg’s partitions?

Posted on October 24, 2023 by Gil Kalai

The problem presented in this post was discussed in my recent lecture “New types of order types” in the workshop on discrete convexity and geometry in Budapest, a few weeks ago. The lecture described various results and questions including the question: Is there a notion of “order type” based on Tverberg’s theorem.   I hope to come back to these questions and results soon. (The lecture also included a poll among the audience about the Erdos-Szekeres conjecture: the outcome was that 12 believe the conjecture and 4 disbelieve.) The present post is based on conversations with Moshe White.

Tverberg’s theorem is among my favorite mathematical theorems; over the years, we devoted eight posts to results and problems around Tverberg’s theorem and mentioned the theorem in a few other places. In 2008 we devoted a post to seven open problems around Tverberg’s theorem. In the meanwhile, two of the problems were settled and major progress was made on a third one. We devoted two posts (I, II) to the  background and proof of Tverberg’s theorem.

Here is a link to my 1999 lecture: “An invitation to Tverberg’s theorem” in the 1999 conference “visions in mathematics towards 2000“. Let me also mention Imre Barany’s new proof of Tverberg’s theorem which includes ingredients from Tverberg’s 1965 proof and yet is quite simple and enlightening.

Tverberg’s theorem

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 J_1,J_2,\dots, J_r of \{1,2,\dots,m\} such that

\cap _{k=1}^r conv (x_i: i \in J_k) \ne \emptyset.

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

The maximum number of Tverberg’s partitions

Before asking about the maximum number of Tverberg’s partition let me mention a well-known problem about the minimum:

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. Let’s denote this minimum by m(d,r).

(Here we consider unordered partitions. For ordered partitions we need to multiply by r!.)  It is quite interesting that there are quite a few different configurations for which this minimum is attained. We discussed many examples by Moshe White and by Boris Bukh, Po-Shen Loh, and Gabriel Nivasch in this post.

What about configurations with the maximum number of Tverberg’s partitions? Here we need to assume that the points are “generic”;

Problem 1: What is the maximum number of Tverberg partitions for (generic) (d+1)(r-1)+1 points in \mathbb R^d. Let us denote the answer by M(d,r).

Here is a variant of the problem:

Problem 2: Given d(r-1)+1 points in \mathbb R^d in a generic position, what is the maximum number of partitions to r parts such that the positive hulls will have a point in common. Let us denote the answer by P(d,r).

(It is reasonable to think that P(d,r) \le M(d+1,r) but I don’t have proof.)

The Gaussian model and a lower bound (for a variation of the problem)

Let x_1,x_2,\dots, x_m be points in R^d, m = (r-1)d+1, and consider an assignment of signs s (i) \in \{-1,1\}, i=1,2,\dots,m. Consider a partition into r parts J_1,J_2,\dots J_r such that

\sum \{\lambda_i  s(i) x_i: i \in J_1\} = \sum \{\lambda_i s(i) x_i: i \in J_2\}=\cdots = \sum \{\lambda_i s(i) x_i: i \in J_r \}.

We will consider only partitions for which 1 \le |J_k| \le d, and let N(d,r) denote the number of such (unordered) partitions. N(d,r) \le m^r.

Now, let’s choose x_1,x_2,\dots,x_m to be independent Gaussian vectors.

Claim 1: (almost surely) for every such partition J_1,J_2,\dots J_r there are unique signs such that our equalities hold.

Claim 2: The probability for an equality to hold is the same for every choice of signs.

Therefore the expected number of partitions for the all one signs is at least

N(d,r)/2^m, so P(d,r) \le N(d,r)/2^m.

When d is large, N(d,r) is pretty close to m^r/r!, so we get \frac {1}{r!}(d/2)^m. This bound is likely to apply for $M(d-1,r)$ and if so we will get that

M(d,r) < \frac {1}{r!} (d/2)^m,

compared to

m(d,r) > (d/e)^m,

that Sierksma’s conjecture gives. It is not outrageous to conjecture that \frac {1}{r!}(d/2)^m gives the right asymptotics for M(d,r) when d is large.

In the third paper of his Ph. D. thesis, Moshe White had theoretical and empirical results regarding the Radon behavior of Gaussian points in the plane and higher dimensions. (This study inspired the above argument regarding Problem 2.)  Let me describe some empirical results regarding the possible behaviors of Tverberg’s partitions for seven points in the plane.

Seven points in the plane

The following picture (by Moshe White) presents the 11 types of configurations of 7 points in the plane, the first non-trivial case of Tverberg’s theorem for three parts. The blue lines between the types correspond to “moves” of Barany’s new proof. There are three configurations with 4 partitions (the minimum) and one configuration with seven partitions (the maximum).

tverberg-7atverberg-7b
janos-gil

This entry was posted in Combinatorics, Convexity, Geometry, Open problems and tagged . Bookmark the permalink.

2 Responses to What is the maximum number of Tverberg’s partitions?

  1. Gil Kalai says:
    October 24, 2023 at 2:14 pm

    Actually, it looks that indeed P(d,r) \le M(d+1,r) because conditioning on the origin not being in the convex hull the two problems coincide and if the origin is in the convex hull there is no partition into intersecting cones at all.

    Reply

  2. Pingback: Updates and Plans IV | Combinatorics and more

Leave a comment