A 64-Rectangle Counterexample to Wegner's Conjecture and LP Gaps up to $5/2$
Wegner conjectured that every finite family $\mathcal R$ of axis-parallel rectangles satisfies $τ(\mathcal R)\le 2ν(\mathcal R)-1$, where $ν$ is the packing number and $τ$ is the piercing number. Ajwani, Gajjala, Raman, and Ray recently disproved this by constructing a triangle-free counterexample on $2196\cdot 8^9$ rectangles and, using a computer-assisted package-and-port recursion, obtained a standard LP gap of $17891/8064$ for Maximum Independent Set of Rectangles. We give a simpler and hand-checkable counterexample with $64$ rectangles. It is built from an eight-rectangle gadget whose…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.11318
curl -X POST /api/v1/records/arxiv/2607.11318/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.11318/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'