{"id":"arxiv/2607.11318","url":"https://arxiv.org/abs/2607.11318","tags":["math.CO","cs.DM"],"score":0,"title":"A 64-Rectangle Counterexample to Wegner's Conjecture and LP Gaps up to $5/2$","domain":"math.CO","source":"arxiv","authors":["Aranya Kumar Bal"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}