{"id":"arxiv/2606.17854","url":"https://arxiv.org/abs/2606.17854","tags":["cs.CG","cs.DM","cs.DS","math.CO"],"score":0,"title":"Counterexamples to Wegner's Conjecture for Rectangles","domain":"cs.CG","source":"arxiv","authors":["Deepak Ajwani","Rishikesh Gajjala","Rajiv Raman","Saurabh Ray"],"reviews":0,"subject":"cs.CG","summary":"Wegner conjectured in 1965 that every finite family $\\mathcal R$ of axis-parallel rectangles satisfies $τ(\\mathcal R)\\le 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 $τ\\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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-16","reactions":{}}