2026/06/16 by Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman +1 · 2 voices
Computer Science · Mathematics · #cs.CG #cs.DM #cs.DS #math.CO
arxiv published 2026/06/16 · arxiv updated 2026/07/09
Wegner conjectured in 1965 that every finite family \mathcal R of axis-parallel rectangles satisfies τ(\mathcal R)≤ 2ν(\mathcal R)-1, where τ(\mathcal R) is the minimum number of piercing points and ν(\mathcal R) is the maximum size of a pairwise-disjoint subfamily. We disprove the conjecture by an explicit triangle-free family of 64 rectangles with ν=16 and τ≥ 32. More generally, for every ε>0, we construct triangle-free rectangle families for which the standard clique-LP relaxation for maximum independent set of rectangles has integrality gap at least 5/2-ε. The same families satisfy τ(\mathcal R)≥ (5/2-ε)ν(\mathcal R). We also prove that, on triangle-free rectangle families, this LP has gap at most 3. Our approach gives an example with axis-parallel segments instead of rectangles with integrality gap tending to 2. We also give a relatively small 4092-rectangle triangle-free family with chromatic number 6 improving the construction of Asplund and Grünbaum (On a coloring problem, Mathematica Scandinavica, 1960) that required more than 108 rectangles.