Attila Por’s Universality Result for Tverberg Partitions

In this post  I would like to tell you about three papers and three theorems. I am thankful to Moshe White and Imre Barany for helpful discussions.

a) Universality of vector sequences and universality of Tverberg partitions, by Attila Por;

Theorem (Por’s universality result, 2018): Every long enough sequence of points in general position in $\mathbb R^d$  contains a subsequence of length n whose Tverberg partitions are exactly the so called rainbow partitions.

b) Classifying unavoidable Tverberg partitions, by Boris BukhPo-Shen LohGabriel Nivasch

Theorem (Bukh, Loh, and Nivasch, 2017): Let $H$ be a tree-like $r$-uniform simple hypergraph with $d+1$ edges and $n=(d+1)(r-1)+1$ edges. It is possible to associate to the vertices of each such hypergraph H a set X of n points in $\mathbb R^d$ so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is $(r-1)!^d$. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

c) On Tverberg partitions, by Moshe White

Theorem (White, 2015): For any partition $a_1,a_2,\dots ,a_r: 1 \le a_i\le d+1$ of $n$, there exists a set $X \subset \mathbb R^d$ of $n$  points, such that every Tverberg partition of $X$  induces the same partition on $n$ given by the parts $a_1,\dots,a_r$. Moreover, the number of Tverberg’s partitions of $X$ is $(r-1)!^d$

See the original abstracts for the papers at the end of the post.

Radon’s and Tverberg’s theorems and Sierksma’s conjecture

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.

We devoted a post to seven open problems related to Tverberg’s theorem, and one of them was:

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’s construction with $(r-1)!^d$ Tverberg’s partition is obtained by taking $(r-1)$ copies of each vertex of a simplex containing the origin in its interior, and adding the origin itself. A configuration of $(r-1)(d+1)+1$ points in $R^d$ with precisely $((r-1)!)^d$ Tverberg partitions to $r$ parts is called a Sierksma Configuration.

White’s Theorem

In 2015 Moshe White proved the following theorem which was an open problem for many years. White’s construction was surprisingly simple.

Theorem 1 (White, 2015):  For any partition $a_1,a_2,\dots ,a_r: 1 \le a_i\le d+1$ of $n$, there exists a set $X \subset \mathbb R^d$ of $n$  points, such that every Tverberg partition of $X$  induces the same partition on $n$ given by the parts $a_1,\dots,a_r$. Moreover, the number of Tverberg’s partitions of $X$ is $(r-1)!^d$

Bukh, Loh, and Nivasch’s  examples via staircase convexity.

Five tree-like simple hypergraphs that correspond to configurations of 11 points in 4-dimensional space.

Start with a tree-like hypergraph H of d+1 blocks of size r like the five examples in the Figure above. The intersection of every two blocks has at most one element. The union of all blocks has n=(d+1)(r-1)+1 elements.

A rainbow coloring of a r-uniform hypergraph H is a coloring of the vertices of H with r colors so that the vertices of every edge is colored by all r colors.

Theorem 2 (Bukh, Loh, and Nivasch): It is possible to associate to the vertices of each such hypergraph H a set X of n points in $\mathbb R^d$ so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is $(r-1)!^d$. (Here, we consider two colorings as the same if they differ by a permutation of the colors.)

For a star-like hypergraph where all blocks have a vertex in common we get the original Sierksma’s example. (Example (d) above.) White’s examples are obtained by considering such hypergraphs where there exists an edge $A$ such that all edges have non empty intersection with $A$. (Examples (c), (d), and (e) above).

Rainbow colorings of our five examples

Tverberg’s partitions for stretched points on the moment curve

It is natural to consider $n$ points on the moment curve $x(t)=(t,t^2,\dots, t^d)$. It turns out that the set of Tverberg’s partitions for points on the moment curve depend on the precise location of the points. By stretched points on the moment curve I mean that  you take the points $x(t_1), x(t_2), \dots x(t_n)$ where $t_1 << t_2 << \dots t_n$, namely $t_2$ is much much larger than $t_1$ and $t_3$ is much much much much larger than $t_2$, etc. etc. In this case, the configuration corresponds to a path $H$: you let the vertices be $\{1,2,\dots,n\}$ and the edges are sets of the form $\{(k-1)(r-1)+1, (k-1)(r-1)+2,\dots , k(r-1)+1\}$. A stretched configuration of points on the moment curve has the property that every subset is also a stretched configuration of points on the moment curve.

The importance of Tverberg’s partitions for stretched points on the moment curve was realized by Barany and Por, by Bukh, Loh, and Nivasch, and by Perles and Sidron (See their paper Tverberg Partitions of Points on the Moment Curve), and perhaps by others as well.

Por’s universality result

Por’s universality theorem asserts that in terms of Tverberg partitions every large enough configuration of points in general position in $R^d$ contains a configuration whose Tverberg partitions are those of a stretched configuration of $n$ points on the moment curve! Por’s  universality result was conjectured independently by Bukh, Loh, and Nivasch, (and they gave some partial results) and by Por himself.

Theorem 3 (Por’s universality result, 2018): Every long enough sequence of points in $\mathbb R^d$ in general position contains a subsequence  of length n whose Tverberg partitions are exactly the so called rainbow partitions.

Por actually proved an apparently stronger statement: We can find a subsequence $Y$ so the conclusion holds not only for $Y$ but also for every subsequence $Z$ of $Y$

Staircase Convexity

The work of Bukh, Loh, and Nivasch relied on an important method of “staircase convexity”. An earlier 2001 application of the method (where it was introduced) was for lower bounds on weak epsilon nets by Bukh, Matousek, and Nivasch (Here are links to the paper, and to slides from a talk by Boris Bukh. See also this post and this one of the weak epsilon net problem.) Roughly the idea is this: consider a stretched grid where the sequence of coordinates are very very fast growing. When you choose configuration of points in such a grid, questions regarding their convex hulls translate to purely combinatorial problems.

Stairconvex sets explained by Boris Bukh

Erdos Szekeres in the plane and higher dimensions

The planar case

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that ES(n) is finite.

The finiteness of ES(n) can be stated as follows: Given a sequence of N points in general position in the plane $x_1,x_2, \dots , x_N$  there is a subsequence $1_i,x_2, \dots , x_n$ such that the line segments $[x_i,x_k]$ and $[x_j,x_\ell ]$ intersect. With this statement, the Erdős and Szekeres’ theorem can be seen as identifying a universal set of points in term of its Radon partitions (or equivalently in terms of its order type).

In high dimensions

In higher dimensions we can define $ES_d(n)$ and replace “in convex position” by “in cyclic position”. The finiteness of $ES_d(n)$ (with terrible bounds) follows easily from various Ramsey results. In a series of papers very good lower and upper bounds where obtained:  Imre BaranyJiri MatousekAttila Por: Curves in R^d intersecting every hyperplane at most d+1 timesMarek EliášJiří MatoušekEdgardo Roldán-PensadoZuzana Safernová: Lower bounds on geometric Ramsey functions; Marek Elias, Jiri Matousek: Higher-order Erdos–Szekeres theorems .

Por’s result

Por’s result can be seen as a far-reaching strengthening of the finiteness of $ES_d(n)$.

Further Discussion:

High order order types?

Can you base a higher-order notion of “order types” on Tverberg partitions?

The order type of a sequence of $n$ points affinely spanning $R^d$, is the described by the vector of signs (0, 1 or -1) of volume of simplices described by subsequences of length $d+1$. Equivalently the order type can be described by the minimal Radon partitions of the points.

1. We can first ask if we can base a notion of higher order types on Tverberg’s partitions to $r$ parts where $r>2$.
2. Next we can ask for an associated notion of “higher order oriented matroids.” (Oriented matroids in the usual sense are abstract order types which coincide with Euclidean order types for every subsequence of $d+3$ points.)
3. A natural question regarding these “higher order types is: If a sequence of points in strong general position is Tverberg-equivalent to stretched points on the moment curve, does it apply to all of its subsequences?

Another way to consider “higher” order types is to enlarge the family by to start with a family of points add to it all Radon points of minimal Radon’s partition and consider the order type of the new configuration. (This operation can be repeated $r$ times.) See this paper of Michael Kallay on point sets which contain their Radon points.

Staircase convexity order types

Understanding order types of configuration of points on stretched grids of Bukh et al. is a very interesting problem. It is interesting to understand such configurations that are not in general position as well. (In particular, which matroids are supported on the stretched grid?) Of course, the method may well have many more applications.

Fantastically strong forms of Sierksma’s conjecture

Is the following true: For every sequence $T$ of $n=(r-1)(d+1)+1$ points in $R^d$ there is a Sierksma’s configuration $S$ of $n$ points so that every Tverberg’s partition of  $S$ is a Tverberg’s partition of $T$?

An even stronger version is:

Does every sequence $T$ of $(r-1)(d+1)+1$ points in $R^d$ there is a tree-like simple hypergraph so that all the rainbow coloring of $H$ correspond to Tverberg partitions of the sequence? If true this will be a fantastically strong version of Sierksma’s conjecture.

Is the Erdős-Szekeres’ conjecture outrageous?

Erdős and Szekeres proved in 1935 that $ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}$, and in 1960, they showed that $ES(n) \ge 2^{n-2}+1$, and conjectured this to be optimal. Despite the efforts of many researchers, until recently no improvement in the order of magnitude has ever been made on the upper bound over  81 years. A  recent breakthrough result by Andrew Suk (Here are links to the paper, and to our post discussing the result) asserts that $ES(n)=2^{n+o(n)}$. Sometime ago I asked over MO a question on outrageous mathematical conjectures and perhaps the conjecture that  $ES(n) = 2^{n-2}+1$ on the nose is an example.

Original Abstracts

Universality of vector sequences and universality of Tverberg partitions, by Attila Por;

Classifying unavoidable Tverberg partitions, by Boris Bukh, Po-Shen Loh, Gabriel Nivasch

On Tverberg partitions, by Moshe White

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

6 Responses to Attila Por’s Universality Result for Tverberg Partitions

1. eppstein says:

(Reposted from a comment I left on Gil’s G+ post)

Staircase convexity itself may have been introduced in the Bukh et al paper that you mention, but the correspondence between the “lines” defining it (the boundaries of lower-left and lower-right quadrants) and straight lines can already be found in Middendorf, Matthias, and Pfeiffer, Frank. 1992. The max clique problem in classes of string-graphs. Discrete Math., 108(1–3), 365–372.

There’s also a chapter about the same staircase geometry in my recent book Forbidden Configurations in Discrete Geometry, which includes a polynomial time algorithm for recognizing (general position) order types of configurations of points on stretched grids.

2. dsp says:

I don’t understand precisely why the Erdos-Szekeres result is equivalent to the statement in terms of intersections of line segments between points in a general position set. Could you tell me more about this?

• Gil Kalai says:

To say that $m$ points in general position are in convex position is equivalent to the assertion that all radon partitions of every four of the points are of type (2,2), namely the line segment of two of the points crosses the line segment of the other two.

If we order the points cyclically in their order as vertices of the convex hull then the the (2,2) Radom partition is described by interlacing indices.

3. Gil Kalai says:

Let me mention that while the examples Bukh, Loh, and Nivasch gives more general cases of configurations meeting the Sierksma’s bound it is not clear if they actually extends White examples. (And it is not clear, how to ask the question this seems to require some higher-order-type definition).

Another remarks is that perhaps the paper by Perles and Sidron that deals with the higher notions of “general position” can be the basis for higher notions of order types.