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 contains a subsequence of length n whose Tverberg partitions are exactly the so called rainbow partitions.
b) Classifying unavoidable Tverberg partitions, by Boris Bukh, Po-Shen Loh, Gabriel Nivasch
Theorem (Bukh, Loh, and Nivasch, 2017): Let be a tree-like -uniform simple hypergraph with edges and edges. It is possible to associate to the vertices of each such hypergraph H a set X of n points in so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is . (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 of , there exists a set of points, such that every Tverberg partition of induces the same partition on given by the parts . Moreover, the number of Tverberg’s partitions of is
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 be points in , . Then there is a partition of such that .
The (much easier) case 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 -partitions of a set of points in is at least .
Gerard Sierksma’s construction with Tverberg’s partition is obtained by taking copies of each vertex of a simplex containing the origin in its interior, and adding the origin itself. A configuration of points in with precisely Tverberg partitions to parts is called a Sierksma Configuration.
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 of , there exists a set of points, such that every Tverberg partition of induces the same partition on given by the parts . Moreover, the number of Tverberg’s partitions of is
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 so that the Tverberg partitions of X correspond precisely to rainbow coloring of the hypergraph H. Moreover, the number of rainbow coloring is . (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 such that all edges have non empty intersection with . (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 . 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 where , namely $t_2$ is much much larger than and is much much much much larger than , etc. etc. In this case, the configuration corresponds to a path : you let the vertices be and the edges are sets of the form . 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 contains a configuration whose Tverberg partitions are those of a stretched configuration of 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 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 so the conclusion holds not only for but also for every subsequence of .
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 there is a subsequence such that the line segments and 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 and replace “in convex position” by “in cyclic position”. The finiteness of (with terrible bounds) follows easily from various Ramsey results. In a series of papers very good lower and upper bounds where obtained: Imre Barany, Jiri Matousek, Attila Por: Curves in R^d intersecting every hyperplane at most d+1 times; Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado, Zuzana Safernová: Lower bounds on geometric Ramsey functions; Marek Elias, Jiri Matousek: Higher-order Erdos–Szekeres theorems .
Por’s result can be seen as a far-reaching strengthening of the finiteness of .
High order order types?
Can you base a higher-order notion of “order types” on Tverberg partitions?
The order type of a sequence of points affinely spanning , is the described by the vector of signs (0, 1 or -1) of volume of simplices described by subsequences of length . Equivalently the order type can be described by the minimal Radon partitions of the points.
- We can first ask if we can base a notion of higher order types on Tverberg’s partitions to parts where .
- 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 points.)
- 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 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 of points in there is a Sierksma’s configuration of $n$ points so that every Tverberg’s partition of is a Tverberg’s partition of ?
An even stronger version is:
Does every sequence of points in there is a tree-like simple hypergraph so that all the rainbow coloring of 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 , and in 1960, they showed that , 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 . Sometime ago I asked over MO a question on outrageous mathematical conjectures and perhaps the conjecture that on the nose is an example.