A 64-Rectangle Counterexample to Wegner’s Conjecture and LP Gaps up to 5/2

Jul 16, 2026

Upload by Aurelia

Wegner’s conjecture in geometric transversal theory, formulated in 1965, posits τ(R) ≤ 2ν(R) − 1 for axis-parallel rectangle families. This work strengthens a recent negative resolution by constructing an explicit counterexample using only 64 rectangles. A recursive composition of an eight-rectangle labeled gadget yields packing–piercing obstructions, improves the best known clique-LP integrality gap to 73/32 at level three, and produces fractional solutions whose values converge to (5/2)ν. The resulting rectangle families attain packing–piercing ratios arbitrarily close to 5/2 from below.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages39

Reading Time1 h 38 min

Abstract

Introduction

Our contributions

arXiv :2607 . 11318v1 [math .CO] 13 Jul 2026 A 64-Rectangle Counterexample to Wegner’s Conjecture and LP Gaps up to 5/2 Aranya Kumar Bal Abstract Since its formulation in 1965, Wegner’s conjecture has been one of the central open problems in geometric transversal theory, profoundly influencing research on geometric intersection graphs, packing and piercing, and approximation algorithms. The recent breakthrough of Ajwani, Gajjala, Raman, and Ray settled the conjecture in the negative by constructing the first counterexample, consisting of 2196 · 89 axis-parallel rectangles using a package-and-port construction alongside a computer-assisted proof, and also established an integrality gap of 17891/8064 ≈ 2.21 for the standard LP relaxation of the Maximum Independent Set of Rectangles problem. In this paper, we substantially strengthen this breakthrough by giving an explicit and conceptually simple counterexample using only 64 rectangles. Whereas the previous counterexample relied on a large construction with a computer-assisted proof, ours is derived from a small geometric gadget with a recursive composition principle alongside a hand-checkable proof, making the obstruction to Wegner’s conjecture transparent. Our construction starts from an eight-rectangle gadget whose independent sets admit an injective assignment to four ordered labels. Combining four horizontal and four vertical copies of this gadget yields the 64-rectangle counterexample. Iterating the same horizontal-vertical construction produces a recursive family Pr satisfying ν(Pr ) = 42r . Already at the second level, the standard clique relaxation has value exceeding 2ν(P2 ) , while at the third level it achievesan integrality gap of 73/32, improving on the previous best value of 17891/8064 . We further construct explicit recursive fractional solutions whose values converge to (5/2)ν(Pr), together with piercing sets of size exactly (5/2)ν(Pr) at every level. Consequently, both the clique-LP gap and the packing-piercing ratio of the recursive family converge to 5/2, yielding rectangle families with packing-piercing ratios arbitrarily close to 5/2 from below. Finally, by taking disjoint unions with isolated rectangles, we show that every rational number in [1 , 5/2) occurs both as a standard LP gap for Maximum Independent Set of Rectangles and as a packing-piercing ratio of a suitable rectangle family. 1 Introduction Let R be a finite family of closed axis-parallel rectangles in the plane. Write ν (R) for the maximum size of a pairwise disjoint subfamily and τ(R) for the minimum number of points required to intersect every rectangle. In 1965, Wegner [Weg65] conjectured that τ (R) ≤ 2ν(R) − 1. Over the past six decades, this conjecture has been one of the central open problems in geometric transversal theory. Beyond its intrinsic appeal, it has profoundly influenced the study of geometric intersection graphs, rectangle packing and piercing, combinatorial optimization, and approximation algorithms. A considerable body of evidence supported Wegner’s conjecture and suggested that the proposed bound was essentially best possible. Fon-Der-Flaass and Kostochka [FDFK93] proved that no universal coefficient below 5/3 is possible, while a construction of Jelínek, reported by Correa, Feuilloley, Pérez-Lantero, and Soto [CFPLS15], gives τ (R) = 2ν(R) − 4 for every ν (R) ≥ 4. Chen and Dumitrescu [CD20] further investigated the sharpness of Wegner’s inequality, and Correa et al. [CFPLS15] studied the special case of diagonal-intersecting rectangles, where the packing-piercing gap is known to lie between 2 and 4. Together with steadily improving general upper bounds, these results made the existence of a counterexample appear increasingly unlikely. The conjecture was finally settled by Ajwani, Gajjala, Raman, and Ray [AGRR26] in the negative, who constructed the first counterexample and, in the same work, established an integrality gap of 17891/8064 > 2.21 fo

FAQs

What does Wegner’s conjecture state for axis-parallel rectangles?

For a finite family R of closed axis-parallel rectangles, Wegner’s conjecture states τ(R) ≤ 2ν(R) − 1, where ν(R) is the maximum size of a pairwise disjoint subfamily and τ(R) is the minimum number of points needed to intersect every rectangle.

How does this paper improve on the previously known counterexample?

It gives an explicit, conceptually simple counterexample using only 64 rectangles, replacing large computer-assisted constructions with a recursive geometric gadget and a hand-checkable combinatorial proof.

What LP gap and packing–piercing ratio does the recursive construction approach?

The construction yields clique-LP gaps and packing–piercing ratios that converge to 5/2, producing rectangle families whose packing–piercing ratios are arbitrarily close to 5/2 from below.

Jul 16, 2026

Upload by Aurelia