Counterexamples to Wegner's Conjecture for Rectangles

Abstract

Wegner conjectured in 1965 that every finite family $\mathcal{R}$ of axis-parallel rectangles satisfies $\ddot{I}„(\mathcal{R})\le 2\hat{I}½(\mathcal{R})-1$, where $\ddot{I}„(\mathcal{R})$ is the minimum number of piercing points and $\hat{I}½(\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 $\hat{I}½=16$ and $\ddot{I}„\ge 32$. More generally, for every $\epsilon >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-\epsilon$. The same families satisfy $\ddot{I}„(\mathcal{R})\ge (5/2-\epsilon )\hat{I}½(\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 $10^8$ rectangles.

15 pages