Wegner conjectured in 1965 that every finite family $\mathcal R$ of axis-parallel rectangles satisfies $\tau(\mathcal R)\le 2\nu(\mathcal R)-1$, where $\tau(\mathcal R)$ is the minimum number of piercing points and $\nu(\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 $\nu=16$ and $\tau\ge 32$.
More generally, for every $\varepsilon>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-\varepsilon$. The same families satisfy $\tau(\mathcal R)\ge (5/2-\varepsilon)\nu(\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\"unbaum (On a coloring problem, Mathematica Scandinavica, 1960) that required more than $10^8$ rectangles.
The initial proof was found with the help of GPT-5.5 Pro with the authors presenting a rough outline and GPT-5.5 Pro did the hard work of working out the details. The proof we present however, is entirely human generated - where we distill the key ideas in the construction of the machine generated proof. The resulting counter-example is much simpler and smaller than that generated by GPT-5.5 Pro.
This is joint work with Deepak Ajwani, Rishikesh Gajjala and Saurabh Ray.
Bio: Rajiv Raman is an associate professor at IIIT-Delhi. He obtained his PhD from the University of Iowa, and then spent some time as a postdoc at the Max-Planck Institute in Saarbrucken and at the Centre for Discrete Mathematics and Applications, University of Warwick.
