Tight Colorful No-Dimensional Tverberg Theorem

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 Q1,⋯,Qn of a normed space, there exists a partition of Q1∪⋯∪Qn into disjoint transversals {P1,⋯,Pk} for which a ball of radius R intersects the convex hull of each Pi (1≤i≤k). Our methods are deterministic and dimension-free, and they are unified by optimizing two functionals: a quadratic selection functional whose local maximizers produce a complete system of disjoint transversals, and a convex 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 Q1,⋯,Qn. A key observation is a “combinatorial” subadditivity of the squared Chebyshev radius: given sequences X=(x1,⋯,xk) and Y=(y1,⋯,yk) of points in a Euclidean space, contained in balls of radii RX and RY (not necessarily with the same center), one can reenumerate Y so that the pointwise-sum sequence Z=(x1+y1,⋯,xk+yk) is contained in a ball of radius RZ satisfying (Formula presented.) As a corollary, we obtain the best-possible bound (Formula presented.) Our algorithm returns the desired disjoint transversals in overall time O(nk3). 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.