Counterexamples to Wegner's Conjecture for Rectangles

Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman, Saurabh Ray

arXivarxiv/2606.17854Jun 16, 2026cs.CGscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.17854
curl -X POST /api/v1/records/arxiv/2606.17854/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.17854/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'