Wegner’s piercing-versus-packing bound for rectangles

For a finite family of axis-parallel rectangles, let ν be the maximum number of pairwise disjoint rectangles and τ the minimum points needed to pierce every rectangle. Must τ≤2ν−1?

Why it matters and what counts as progress

Why it matters: Wegner’s conjecture compares disjointness with the global cost of hitting all rectangles.

What counts as progress: A proof of the bound or a rectangle family with certified packing and piercing numbers violating it; larger asymptotic τ/ν ratios strengthen a counterexample.

How the problem developed

1965 · Conjecture [1]
Klaus Wegner Posed the rectangle piercing question asking whether the transversal number τ is at most 2ν−1, where ν is the maximum number of pairwise disjoint rectangles.
2020 · Partial result [2]
Ke Chen and Adrian Dumitrescu Gave constructions attaining τ=2ν−1 for ν=2, 3 and 4, within the axis-parallel rectangle packing-versus-piercing problem.
16 Jun 2026 · Counterexample [3]
Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman and Saurabh Ray Gave an explicit family of axis-parallel rectangles violating Wegner's τ≤2ν−1 conjectured bound, beginning with 64 rectangles for which ν=16 and τ≥32.

AI contribution

Counterexamples to Wegner's Conjecture for Rectangles

Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman, Saurabh Ray

Ajwani, Gajjala, Raman and Ray give 64 axis-parallel rectangles with packing number 16 and piercing number at least 32, disproving Wegner’s proposed bound 2ν−1. Their package construction yields piercing and clique-LP ratios approaching 5/2.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull