Bounding the Piercing Number

Noga Alon, Gil KalaiDiscret. Comput. Geom 1995 · DOI

Original publication header from Discrete & Computational Geometry (1995).

In the landscape of discrete geometry, Helly's Theorem stands as a foundational pillar. It posits that for a finite family of convex sets in $d$-dimensional space, if every $d+1$ sets have a non-empty intersection, then the entire family must share a common point. However, the mathematical community long wondered what happens when this condition is relaxed. What if, instead of every $d+1$ sets intersecting, we only know that among any $p$ sets, some $q$ of them share a common point?

This relaxation leads to the $(p, q)$ problem. In 1992, Noga Alon and Daniel Kleitman famously proved the Hadwiger-Debrunner $(p, q)$ conjecture, showing that for convex sets, if $p \ge q \ge d+1$, the "piercing number"—the minimum number of points required to hit every set in the family—is bounded by a constant depending only on $p, q,$ and $d$.

In their 1995 paper, "Bounding the Piercing Number," Noga Alon and Gil Kalai extended this breakthrough to even more complex geometric scenarios: families of sets formed by the union of multiple convex sets and the problem of piercing sets with hyperplanes rather than points.

Expanding the Scope: Unions and Hyperplanes

Alon and Kalai addressed two primary questions that pushed the boundaries of the original $(p, q)$ theorem:

  1. Unions of Convex Sets: Does a bounded piercing number still exist if the sets in the family are not strictly convex, but are instead each a union of up to $k$ convex sets?
  2. Hyperplane Transversals: Can we bound the number of hyperplanes (e.g., lines in 2D, planes in 3D) needed to intersect every set in a family, given a $(p, q)$ property for hyperplane transversals?

These questions are significant because they move away from the "pure" convexity that Helly-type theorems usually rely on, exploring the combinatorial limits of intersection properties.

The "General Technique"

The authors formalized a powerful three-step framework that has since become a standard methodology for proving piercing theorems in combinatorial geometry.

1. The Fractional Piercing Theorem

The first step involves showing that if a large fraction of $r$-element subfamilies are pierceable (i.e., they have a common intersection), then there exists a single element—be it a point or a hyperplane—that hits a significant, fixed fraction of the entire family. This "fractional" version of the problem is often more tractable than the "integral" version.

2. Linear Programming (LP) Duality

Using the minimax theorem from linear programming, the authors convert the fractional piercing result into a weighted version. This step demonstrates that for any arbitrary distribution of weights assigned to the sets in the family, there exists an element (point or hyperplane) that hits a "heavy" portion of the family (a portion whose total weight exceeds a certain threshold $\epsilon$).

3. Weak $\epsilon$-Nets

The final piece of the puzzle is the existence of "weak $\epsilon$-nets." These are small sets of points or hyperplanes guaranteed to intersect any "heavy" set in the family. By combining the weighted piercing result with the existence of these nets, the authors arrive at a finite, constant bound for the total piercing number of the entire family.

Key Insights and Results

The paper's results are encapsulated in several major theorems that provide structural bounds for these geometric families.

  • Theorem 1.1 (Unions of Sets): For any family of sets where each set is a union of at most $k$ compact convex sets in $\mathbb{R}^d$, if the $(p, q)$ property holds for $p \ge q \ge d+1$, the piercing number is bounded by a constant $c(k, p, q, d)$. This shows that the "complexity" of the sets (being unions) does not destroy the existence of a global piercing bound.
  • Theorem 1.3 (Hyperplane Transversals): For a family of compact convex sets in $\mathbb{R}^d$, if among any $p$ sets, $q$ share a common hyperplane transversal ($p \ge q \ge d+1$), then all sets can be met by a set of at most $C(p, q, d)$ hyperplanes. This is particularly striking because hyperplane transversals do not possess a finite Helly number in the traditional sense, yet they still obey $(p, q)$ bounds.
  • Helly Order: The authors introduced the concept of "Helly order" for unions of sets. While these unions don't have a simple Helly number like $d+1$, they possess a finite Helly order, meaning their intersection patterns remain predictable and bounded.

Limitations and the Path Forward

While the paper provides a definitive proof of existence for these constants, it leaves several practical and theoretical doors open. The constants $c$ and $C$ derived through this method are often non-constructive and astronomically large, leaving the search for tight bounds as an ongoing challenge.

Furthermore, the paper focuses on the "extreme" cases of piercing: 0-dimensional points and $(d-1)$-dimensional hyperplanes. The "intermediate" cases—such as piercing sets with lines or $k$-dimensional flats in higher-dimensional space—remain significantly more difficult. A specific open problem highlighted by the authors is whether a $(p, q)$ property for line transversals in 3D implies a bounded piercing number, a question that continues to drive research in the field today.

Summary updated

BibTeX
@article{alon1995bounding,
  author = {Noga Alon and Gil Kalai},
  title = {{Bounding the Piercing Number}},
  journal = {Discret. Comput. Geom.},
  year = {1995},
  doi = {10.1007/bf02574042},
}

Loading related content...

Figure