Tverberg's theorem for unions of convex sets: Sharp bounds and colored extensions

Abstract

Let $f_r(d,s_1,\dots ,s_r)$ be the least $N$ such that every $N$-point set $P\subseteq {\mathbb{R}}^d$ has an $r$-partition $P=P_1\bigsqcup \cdots \bigsqcup P_r$ with the following property: whenever $C_i\supseteq P_i$ is a union of at most $s_i$ convex sets, one has ${\bigcap }_{i=1}^r{C}_i\ne \varnothing$. A recent breakthrough of Alon and Smorodinsky proved that $f_r(d,s,\dots ,s)\le cd{r}^2{s}^r\log r\log (e{s}^r)$ for an absolute constant $c>0$. In this paper, we determine the asymptotic order in two principal ranges: $f_2(2,s,s)=\Theta (s^2)$, and $f_r(d,s,\dots ,s)={\Theta }_{d,r}(s^r\log s)$ for every fixed $d,r$ with $d\ge r+2$. The first one determines the order of the extremal function proposed by Kalai from the 1970s. Together, the two results show a sharp dependence on the dimension: for two parts, the logarithmic factor disappears in the plane but is necessary in every fixed dimension $d\ge 4$. Beyond these sharp results, when $r\ge d+1$ we improve the upper bound of Alon and Smorodinsky by proving both $f_r(d,s,\dots ,s)\le c_{d}r{s}^r\log (er{s}^r)$ and $f_r(d,s,\dots ,s)\le c_d{r}^{d+2}{s}^{d+1}\log (ers)$ through a local Helly-type argument. We also prove $f_r(d,s,\dots ,s)>s^{\min \{r,d\}}$ for every $d\ge 2$. Finally, we study two colored analogues. The direct Bárány--Larman-type extension, in which one seeks $r$ disjoint rainbow sets chosen from $d+1$ color classes, fails as soon as two convex pieces are allowed. Nevertheless, a different extension does hold: given sufficiently many prescribed $r$-point classes, one can split every class completely among the $r$ final parts while retaining the required intersection property.

23 pages. A new result was added: $f_2(2,s,s)=\Theta (s^2)$