Abstract
This paper presents a new variation of Tverberg's theorem. Given a discrete set $S$ of $\mathbb{R}^d$, we study the number of points of $S$ needed to guarantee the existence of an $m$-partition of the points such that the intersection of the $m$ convex hulls of the parts contains at least $k$ points of $S$. The proofs of the main results require new quantitative versions of Helly's and Carathéodory's theorems.
Introduction
In 1966, Helge Tverberg proved a fundamental result in combinatorial geometry: any set of points in $\mathbb{R}^d$ of sufficient size can be partitioned into $m$ subsets such that the convex hulls of these subsets share a common point. While the classical Tverberg theorem is a cornerstone of the field, it operates in a continuous space where the intersection point can exist anywhere in $\mathbb{R}^d$.
This research extends the theorem into discrete settings, such as integer lattices ($\mathbb{Z}^d$), and introduces a quantitative requirement: the intersection must contain not just one point, but at least $k$ points from a specific discrete set $S$. This work bridges the gap between discrete geometry and quantitative Helly-type theorems, providing new bounds for these "Tverberg numbers."
Theoretical Framework: The Helly-Tverberg Connection
The authors' primary methodological breakthrough is linking Tverberg-type problems to Helly-type problems. Helly's Theorem typically relates the intersection of a family of convex sets to the intersections of its smaller subfamilies. By establishing a relationship between the Helly number ($H_S$) of a discrete set and its Tverberg number ($T_S$), the authors provide a framework for calculating the points required for complex partitions.
Key Methodological Tools
- $k$-Hollow Sets: The researchers utilize the concept of "hollow" sets—convex sets whose interiors contain fewer than $k$ points of $S$. These are essential for establishing the upper bounds of the Helly and Tverberg numbers.
- Colorful Carathéodory Lemma: The paper develops a new discrete, quantitative, and "colorful" version of Carathéodory’s theorem. This allows for the selection of points from distinct "color classes" (subsets) to form a convex hull that still contains a specific target set $K$.
- Point Depth: The authors employ the notion of point depth—the minimum number of points from a set $A$ contained in any half-space that includes a specific point $p$. They demonstrate that if a set $P$ has sufficient depth relative to $A$, the convex hull of $A$ must contain $P$.
Key Results and Insights
The paper provides the first general bounds for Tverberg numbers over arbitrary discrete sets with finite Helly numbers.
The General Bound
For any discrete set $S$ with a finite Helly number $H_S(k)$, the Tverberg number is bounded by: $$T_S(m, k) \leq H_S(k)(m-1)kd + k$$ This formula allows researchers to immediately derive Tverberg bounds if the Helly number for a specific discrete set is known.
Integer Lattices and Concrete Examples
For the $d$-dimensional integer lattice $\mathbb{Z}^d$, the authors improved existing bounds, showing that: $$T_{\mathbb{Z}^d}(m) \leq (m-1)d2^d + 1$$ To illustrate the difference between continuous and discrete requirements, consider the real plane ($\mathbb{R}^2$):
- Classical Tverberg: 7 points are sufficient to guarantee a 3-partition with a common intersection.
- Discrete Tverberg ($\mathbb{Z}^2$): To guarantee that the intersection contains at least one integer point, 25 points are required.
Non-Monotonicity
A surprising insight highlighted in the paper is the non-monotonicity of quantitative Helly numbers for lattices. In some instances, requiring a larger intersection (e.g., $k+1$ points) actually requires fewer initial points in the subfamily than requiring a smaller intersection ($k$ points), a counter-intuitive result that complicates the search for tight bounds.
Limitations and Future Directions
While this work provides significant upper bounds, the authors note that the "tightness" of these bounds—how close they are to the absolute minimum required points—remains an open question.
Furthermore, the authors propose the Colorful Discrete Quantitative Tverberg Theorem (Conjecture 4.2). While they have successfully proved the non-colorful version, the colorful version—where points are pre-assigned to groups and each partition must be a "rainbow" set containing one point from each group—remains a challenge for future combinatorial research. This work serves as a discrete counterpart to the authors' parallel research into continuous quantitative Tverberg theorems, which focus on the volume or diameter of intersections rather than point counts.
Summary updated