Abstract
This paper presents sixteen quantitative versions of the classic Tverberg, Helly, & Caratheodory theorems in combinatorial convexity. Our results include measurable or enumerable information in the hypothesis and the conclusion. Typical measurements include the volume, the diameter, or the number of points in a lattice.
Introduction
In classical combinatorial convexity, theorems typically establish the existence of specific points or intersections. Carathéodory’s Theorem guarantees that a point in the convex hull of a set can be represented by a small subset of points; Helly’s Theorem ensures a global intersection if all small subfamilies intersect; and Tverberg’s Theorem guarantees that a large set can be partitioned into subsets with a common intersection point.
However, these results are qualitative. They do not specify the "size" of the resulting intersection—its volume, diameter, or the number of lattice points it contains. This paper bridges this gap by providing a unified quantitative framework, establishing lower bounds for these geometric properties. Such guarantees are critical for applications in optimization, data clustering, and computer science where non-emptiness is insufficient.
Methodology
The authors develop an interconnected theory using a hierarchical "building block" approach:
- Polytopal Approximation: Continuous results (volume and diameter) leverage the theory of approximating convex bodies with polytopes.
- Steinitz’s Theorem: The authors extend Steinitz’s theorem—a variation of Carathéodory’s dealing with the interior of convex hulls—to "colorful" versions.
- Restricted Convexity: Discrete results focus on intersections with specific subsets, such as the integer lattice $\mathbb{Z}^d$.
- Inductive Pipeline: The paper establishes a logical flow where quantitative Carathéodory results prove Helly-type results, which then yield Tverberg-type theorems.
Key Results and Insights
The research establishes sixteen quantitative versions of these core theorems, categorized into monochromatic and colorful versions across standard, continuous, and discrete domains.
A central insight is the "Thick Enough" requirement: for continuous quantitative Tverberg results, input sets must have convex hulls containing a ball of a certain radius to avoid degenerate cases with zero volume. Furthermore, the authors provide "colorful" versions, where points are selected from different sets (colors), a significantly more complex task than the monochromatic case.
Notable findings include:
- Theorem 1.4 (Continuous Helly): If every subfamily of a specific size has an intersection of volume $\ge 1$, the total intersection volume is at least $(1 + \epsilon)^{-1}$.
- Theorem 1.12 (Continuous Tverberg): The first result showing that, under thickness conditions, the intersection of partitioned hulls contains a ball of radius at least $d^{-2(d+1)}$.
- Corollary 1.21 (Integer Tverberg): An improved upper bound for the Tverberg number over the integer lattice $\mathbb{Z}^d$: $(m-1)d2^d + 1$.
Limitations and Future Work
Despite the comprehensive framework, several challenges remain. The "Colorful Discrete Quantitative Tverberg" theorem is currently an open problem (indicated by the "?" in the summary table), addressed by the authors' Conjecture 1.22. Additionally, some colorful Tverberg results are constrained by prime number requirements ($m+1$ must be prime) due to the topological methods employed. Finally, while the paper establishes theoretical bounds, the algorithmic complexity of finding these partitions in high-dimensional space remains a subject for future research.
Summary updated