Tight colorful no-dimensional Tverberg theorem

Abstract

We study colorful no-dimensional Tverberg-type problems and obtain several optimal results. A colorful no-dimensional Tverberg-type theorem provides a bound on a radius $R$ such that, for any pairwise disjoint $k$-element subsets $Q_1,\dots ,Q_n$ of a normed space, there exists a partition of $Q_1\cup \cdots \cup Q_n$ into disjoint transversals $\{P_1,\dots ,P_k\}$ for which a ball of radius $R$ intersects the convex hull of each $P_i$ ($1\le i\le k$). Our methods are deterministic and dimension-free, and they are unified by optimizing two functionals: a quadratic \emph{selection} functional whose local maximizers produce a complete system of disjoint transversals, and a convex \emph{intersection} functional that certifies a common point. First, in the Euclidean setting we bound $R$ in terms of the Chebyshev radii (minimal enclosing-ball radii) of the color classes $Q_1,\dots ,Q_n$. A key observation is a ``combinatorial'' subadditivity of the squared Chebyshev radius: given sequences $X=(x_1,\dots ,x_k)$ and $Y=(y_1,\dots ,y_k)$ of points in a Euclidean space, contained in balls of radii $R_X$ and $R_Y$ (not necessarily with the same center), one can reenumerate $Y$ so that the pointwise-sum sequence $Z=(x_1+y_1,\dots ,x_k+y_k)$ is contained in a ball of radius $R_Z$ satisfying \[ R_Z^2 \le R_X^2 + R_Y^2 . \] As a corollary, we obtain the best-possible bound \[ R \le \frac{1}{\sqrt{2n}}\sqrt{\frac{k-1}{k}}\, \max_{1\le i\le n} \operatorname{diam}(Q_i). \] Our algorithm returns the desired disjoint transversals in overall time $\mathcal{O}(n{k}^3)$. Second, we develop a complementary approach based on the inter-color diameter and extend the framework to obtain no-dimensional colorful Tverberg-type results in the hyperbolic setting and in Banach spaces.

v3: 18 pages. Added a new co-author. Paper completely rewritten with new results (Theorem 1.3, Theorem 1.4, Lemma 4.3, etc.)