A Tverberg-type problem of Kalai: Two negative answers to questions of Alon and Smorodinsky, and the power of disjointness

Abstract

Let $f_r(d,s_1,\dots ,s_r)$ denote the least integer $n$ such that every $n$-point set $P\subseteq {\mathbb{R}}^d$ admits a partition $P=P_1\cup \cdots \cup 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\ne \varnothing$, where an $s_i$-convex set means a union of $s_i$ convex sets. A recent breakthrough by Alon and Smorodinsky establishes a general upper bound $f_r(d,s_1,\dots ,s_r)=O(d{r}^2\log r{\prod }_{i=1}^r{s}_i\cdot \log ({\prod }_{i=1}^r{s}_i).$ Specializing to $r=2$ resolves the problem of Kalai from the 1970s. They further singled out two particularly intriguing questions: whether $f_2(2,s,s)$ can be improved from $O(s^2\log s)$ to $O(s)$, and whether $f_r(d,s,\dots ,s)\le Poly(r,d,s)$. We answer both in the negative by showing the exponential lower bound $f_r(d,s,\dots ,s)>s^r$ for any $r\ge 2$, $s\ge 1$ and $d\ge 2r-2$, which matches the upper bound up to a multiplicative $\log s$ factor for sufficiently large $s$. Our construction combines a scalloped planar configuration with a direct product of regular $s$-gon on the high-dimensional torus $({\mathbb{S}}^1{)}^{r-2}$. Perhaps surprisingly, if we additionally require that within each block the $s_i$ convex sets are pairwise disjoint, the picture changes markedly. Let $F_r(d,s_1,\dots ,s_r)$ denote this disjoint-union variant of the extremal function. We show: (1) $F_2(2,s,s)=O(s\log s)$ by connecting it to a suitable line-separating function in the plane; (2) when $s$ is large, $F_r(d,s,\dots ,s)$ can be bounded by $O_{r,d}(s^{(1-\frac{1}{2^d(d+1)})r+1})$ and $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.

22 pages, 5 figures. We are grateful to Shakhar Smorodinsky for pointing out that Theorem 4.8 in the previous version can be obtained from known results, which allows us to simplify the proof of Theorem 1.6