TL;DR
This paper extends Tverberg's theorem, a cornerstone of combinatorial geometry, to discrete sets of points. It establishes quantitative bounds on the number of points required to guarantee an $m$-partition whose convex hulls intersect in at least $k$ points from the discrete set. This work introduces new quantitative versions of Helly's and Carathéodory's theorems, crucial for proving these discrete generalizations.
What Problem Does This Paper Address?
Tverberg's theorem (1966) states that for $n > (d+1)(m-1)$ points in $\mathbb{R}^d$, they can be partitioned into $m$ disjoint sets whose convex hulls have a common intersection point. This theorem is fundamental in combinatorial convex geometry. However, traditional Tverberg theorems deal with points in continuous space. This paper addresses the question of how these theorems behave when restricted to discrete sets of points, such as lattices (like $\mathbb{Z}^d$). Specifically, it seeks to quantify the number of points needed from a discrete set $S \subseteq \mathbb{R}^d$ to guarantee an $m$-partition such that the intersection of the $m$ convex hulls contains at least $k$ points from $S$. This "quantitative" aspect is key, moving beyond just guaranteeing existence to specifying how many points are needed.
Methods
The core of the paper lies in developing and utilizing quantitative versions of classical geometric theorems for discrete sets.
- Quantitative S-Tverberg Numbers ($T_S(m, k)$): This is the central concept. $T_S(m, k)$ is defined as the minimum number of points from a discrete set $S \subseteq \mathbb{R}^d$ that guarantees an $m$-partition whose convex hulls intersect in at least $k$ points of $S$.
- Quantitative S-Helly Numbers ($H_S(k)$): This is a crucial tool. $H_S(k)$ is the minimum number of convex sets in a family that, if every subfamily of size $H_S(k)$ has an intersection with $S$ containing at least $k$ points, then the entire family's intersection with $S$ contains at least $k$ points.
- Quantitative S-Carathéodory Theorems: The paper extends Carathéodory's theorem (any point in the convex hull of $S$ is a convex combination of at most $d+1$ points of $S$) to discrete settings, particularly "colorful" versions. This is essential for constructing the partitions.
- Quantitative Hoffman Numbers ($H'_S(k)$) and k-hollow sets: These are auxiliary concepts introduced to bound the S-Helly numbers, providing a bridge between geometric properties and combinatorial counts.
The main result (Theorem 1.4) establishes a relationship between these numbers: $T_S(m, k) \leq H_S(k)(m-1)kd + k$. The proofs involve intricate combinatorial arguments and leverage these newly defined quantitative geometric numbers.
Datasets
Not discussed in the paper. The paper focuses on theoretical results concerning discrete sets in $\mathbb{R}^d$, such as lattices ($\mathbb{Z}^d$) and their differences, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Discrete vs. Continuous Geometry: The paper highlights that extending continuous geometric theorems to discrete settings requires careful quantitative analysis. The "number of points needed" becomes a critical parameter.
- Interplay of Helly and Tverberg: A key insight is that the quantitative Tverberg number for a discrete set $S$ can be bounded by its quantitative Helly number. This suggests a deep connection between these two fundamental geometric concepts when applied to discrete structures.
- Generalization to Arbitrary Discrete Sets: While lattices are primary examples, the framework is designed to apply to any discrete set $S$ in $\mathbb{R}^d$, broadening the applicability of these theorems.
- "Colorful" Versions: The paper emphasizes the utility of "colorful" versions of Helly and Carathéodory theorems, which are instrumental in constructing the desired partitions and proving the main results.
Key Results
The paper's main contribution is Theorem 1.4:
- Theorem 1.4 (Discrete quantitative Tverberg): For a discrete set $S \subseteq \mathbb{R}^d$ with a finite quantitative S-Helly number $H_S(k)$, the quantitative S-Tverberg number $T_S(m, k)$ satisfies: $T_S(m, k) \leq H_S(k)(m-1)kd + k$.
This theorem provides an upper bound on the number of points from $S$ required to guarantee an $m$-partition whose convex hulls intersect in at least $k$ points of $S$.
Several corollaries illustrate the theorem's application:
- Corollary 1.1 (Quantitative Tverberg over $\mathbb{Z}^d$): For $S = \mathbb{Z}^d$, an explicit bound is given: $c(d, k) = (2d-2)\lceil 3(k+1)\rceil+2$ points are sufficient.
- Corollary 1.5 (Bounds for specific discrete sets): The paper provides bounds for $T_S(m)$ (where $k=1$) for various types of discrete sets, including differences of lattices and $\mathbb{Q}$-modules, leveraging known bounds on $H_S(k)$.
Limitations and Future Work
- Upper Bounds: The results are primarily upper bounds. Finding exact values for $T_S(m, k)$ and $H_S(k)$ for various discrete sets remains an open challenge.
- General Discrete Sets: While the framework applies to general discrete sets, the specific bounds derived often rely on properties of lattices or related structures.
- Continuous Analogues: The authors mention in their future directions that they are also presenting new results on continuous quantitative versions of these theorems in a related work.
- Colorful Discrete Tverberg Conjecture: The paper poses Conjecture 4.2, a colorful discrete quantitative Tverberg theorem, which aims to generalize the concept further by considering multiple families of points as color classes.
- Topological Tverberg Conjecture: The paper references the falsity of conjectured topological versions of Tverberg's theorem, indicating the complexity and evolving nature of this field.
Summary updated