A Tverberg-type problem of Kalai: Two negative answers to questions of Alon and Smorodinsky, and the power of disjointness
Wenchong Chen, Gennian Ge, Yang Shu, Zhouningxin Wang, Zixiang Xu · 2025
Read A Tverberg-type problem of Kalai: Two negative answers to questions of Alon and Smorodinsky, and the power of disjointness by Wenchong Chen, Gennian Ge, Yang Shu, Zhouningxin Wang, Zixiang Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20770.txt.
Introduction
Wenchong Chen, Gennian Ge, Yang Shu, Zhouningxin Wang, and Zixiang Xu settle two open questions on a Tverberg type problem posed by Kalai in the nineteen seventies. The problem asks how many points force a split into groups whose widened convex covers must share a common point.
A recent breakthrough gave a general upper bound and singled out whether key cases could be improved to linear growth or to polynomial growth. Both hopes fail here, the team proves an exponential lower bound that matches the upper bound up to a small log factor for large settings. Their build blends a scalloped flat pattern with products of regular polygons on a high dimensional torus, showing how demanding groups stay apart helps force the bound.
Catalog record
| CREATOR | Wenchong Chen, Gennian Ge, Yang Shu, Zhouningxin Wang, Zixiang Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-20770
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Tverberg-type problem of Kalai: Two negative answers to questions of Alon and Smorodinsky, and the power of disjointness Wenchong Chen, Gennian Ge, Yang Shu, Zhouningxin Wang, Zixiang Xu Abstract Let f r ( d , s 1 , … , s r ) f_{r}(d,s_{1},\ldots,s_{r}) denote the least integer n n such that every n n -point set P ⊆ ℝ d P\subseteq\mathbb{R}^{d} admits a partition P = P 1 ⊔ ⋯ ⊔ P r P=P_{1}\sqcup\cdots\sqcup P_{r} with the property that for any choice of s i s_{i} -convex sets C i ⊇ P i C_{i}\supseteq P_{i} ( i ∈ [ r ] ) (i\in[r]) one necessarily has ⋂ i = 1 r C i ≠ ∅ \bigcap_{i=1}^{r}C_{i}\neq\emptyset , where an s i s_{i} -convex set means a union of s i s_{i} convex sets. A recent breakthrough by Alon and Smorodinsky establishes a general upper bound f r ( d , s 1 , … , s r ) = O ( d r 2 log r ⋅ ( ∏ i = 1 r s i ) ⋅ log ( ∏ i = 1 r s i ) ) . f_{r}(d,s_{1},\dots,s_{r})=O\Big(dr^{2}\log r\cdot\Big(\prod_{i=1}^{r}s_{i}\Big)\cdot\log\Big(\prod_{i=1}^{r}s_{i}\Big)\Big). Specializing to r = 2 r=2 resolves the problem of Kalai from the 1970s. They further singled out two particularly intriguing questions: whether f 2 ( 2 , s , s ) f_{2}(2,s,s) can be improved from O ( s 2 log s ) O(s^{2}\log s) to O ( s ) O(s) , and whether there is a polynomial upper bound f r ( d , s , … , s ) ≤ Poly ( r , d , s ) f_{r}(d,s,\ldots,s)\leq\operatorname{Poly}(r,d,s) . We answer both in the negative by showing the exponential lower bound f r ( d , s , … , s ) > s r f_{r}(d,s,\ldots,s)>s^{r} for any r ≥ 2 , s ≥ 1 r\geq 2,s\geq 1 and d ≥ 2 r − 2 d\geq 2r-2 , which matches the upper bound up to a multiplicative log s \log{s} factor for sufficiently large s s . Our construction combines a scalloped planar configuration with a direct product of regular s s -gon on the high-dimensional torus ( 𝕊 1 ) r − 2 (\mathbb{S}^{1})^{r-2} . Perhaps surprisingly, if we additionally require that within each block the s i s_{i} convex sets are pairwise disjoint, the picture changes markedly. Let F r ( d , s 1 , … , s r ) F_{r}(d,s_{1},\ldots,s_{r}) denote this disjoint-union variant of the extremal function. • We show that F 2 ( 2 , s , s ) = O ( s log s ) F_{2}(2,s,s)=O(s\log s) by performing controlled planar geometric transformations, and constructing an auxiliary graph whose planarity yields the upper bound. • We show when s s is large, F r ( d , s , … , s ) F_{r}(d,s,\ldots,s) can be bounded by O r , d ( s ( 1 − 1 2 d ( d + 1 ) ) r + 1 ) O_{r,d}\bigg(s^{\big(1-\frac{1}{2^{d}(d+1)}\big)r+1}\bigg) and O d ( r 3 log r ⋅ s 2 d + 3 ) O_{d}(r^{3}\log{r}\cdot s^{2d+3}) respectively. This builds on a novel connection between the geometric obstruction and hypergraph Turán numbers, in particular, a variant of the Erdős box problem. 1 Introduction 1.1 Background Tverberg-type intersection phenomena lies at the heart of combinatorial convexity: one seeks structural conditions under which different organized parts of a finite set of points must meet. The classical starting point is Radon’s theorem [ 24 ] , which states that every set of d+2 points in \mathbb{R}^{d} can be split into two parts whose convex hulls intersect; the bound is tight. A far-reaching generalization is Tverberg’s theorem [ 26 ] : for integers d\geq 1 and r\geq 2 , any set of (r-1)(d+1)+1 points in \mathbb{R}^{d} admits a partition into r parts whose convex hulls have a common point. This threshold is also sharp. Tverberg’s result has spawned a vast literature, including colorful, fractional, and topological extensions [ 3 , 5 , 6 , 8 , 9 , 10 , 21 , 22 , 23 , 27 ] , with broad connections across various fields [ 1 , 13 , 25 ] ; see the surveys [ 7 , 15 ] and references therein. Motivated by Radon’s viewpoint, Kalai in the 1970s [ 18 ] advocated a different axis of generalization: instead of requiring each part to contribute a single convex hull, allow each part to be a union of few convex sets . This leads to Radon and Tverberg-type questions for unions of convex sets, asking for thresholds that force two or more such unions to meet. The significance of this extension lies in its practical relevance, as many real-world objects are not perfectly convex but can be approximated by unions of convex components. In this vein, Alon and Smorodinsky made a recent breakthrough using an extended VC-dimension argument tailored to unions of halfspaces: among other results, they solved the two-part (“Radon-type”) problem for unions of few convex sets and developed an r -part framework in \mathbb{R}^{d} [ 2 ] . After this, Kalai [ 18 ] stated that this now looks to him like a very promising direction in discrete geometry. To systematize the r -part problems for unions of convex sets, we adopt the following master parameter. For integers r\geq 2 and s_{1},\dots,s_{r}\geq 1 , define f_{r}(d,s_{1},\ldots,s_{r}) to be the least integer n such that every n -point set P\subseteq\mathbb{R}^{d} admits a partition P=P_{1}\sqcup\cdots\sqcup P_{r} with the property that for any choice of s_{i} -convex sets C_{i}\supseteq P_{i} (i\in[r]) one necessarily has \bigcap_{i=1}^{r}C_{i}\neq\emptyset, where an s_{i} -convex set is a union of s_{i} convex sets. Within this framework, Radon’s theorem [ 24 ] is equivalent to f_{2}(d,1,1)=d+2 and Tverberg’s theorem [ 26 ] is equivalent to f_{r}(d,1,\ldots,1)=(r-1)(d+1)+1. This quantity encapsulates the Radon case and its Tverberg-type extensions for unions of convex sets, and it will be the central object of research in this paper. 1.2 The results and questions of Alon and Smorodinsky The earliest finiteness result toward Kalai’s problem is due to Bárány and Kalai, who showed via a clever Ramsey-theoretic argument that f_{2}(d,s_{1},s_{2}) is always finite, albeit with an enormous bound as a function of d,s_{1},s_{2} , which relies on another quantitative result of Conlon, Fox, Pach, Sudakov and Suk [ 11 ] , see [ 17 ] . A recent breakthrough of Alon and Smorodinsky [ 2 ] provides the currently best general upper bound for the Tverberg-type intersection problem in the context of unions of convex sets. Theorem 1.1 ( [ 2 ] ) . For integers d\geq 1 , r\geq 2 , and s_{1},\dots,s_{r}\geq 1 , there exists a constant c>0 such that f_{r}(d,s_{1},\dots,s_{r})\leq cdr^{2}\log r\Big(\prod_{i=1}^{r}s_{i}\Big)\log\Big(\prod_{i=1}^{r}s_{i}\Big)\Bigr.. Specializing Theorem 1.1 to the two-part case ( r=2 ) yields a near-optimal answer to Kalai’s original question. Beyond their main upper bound, Alon and Smorodinsky [ 2 ] also record a number of refined estimates in special regimes. For example, in the planar case