Abstract:In 1965, Wegner conjectured that every finite family \(\mathcal R\) of axis-parallel rectangles in the plane satisfies \(\tau(\mathcal R) \le 2\nu(\mathcal R)-1\), where \(\tau(\mathcal R)\) denotes the minimum number of points needed to pierce all rectangles in \(\mathcal R\), and \(\nu(\mathcal R)\) denotes the maximum size of a pairwise disjoint subfamily. Over the last six decades, the conjecture has motivated a long line of work: it has been verified for several special classes of rectangle families, and the best known general upper bounds have been progressively improved, but the conjecture itself had remained open. We give an explicit counterexample.
More precisely, we construct a triangle-free rectangle-intersection graph on \(n\) vertices whose independence number is at most \(n/4\). Since the graph is triangle-free, no point of the plane can lie in three rectangles; hence every piercing point hits at most two rectangles. Consequently, \(\tau(\mathcal R) \ge n/2 \ge 2\nu(\mathcal R)\), contradicting Wegner's conjectured bound. We also give a slightly more general construction for which \(\tau(\mathcal R) \ge 2.21\nu(\mathcal R)\). This shows that the standard point relaxation, equivalently the clique relaxation, for the Maximum Independent Set of Rectangles problem has integrality gap at least \(2.21\).
From: Rishikesh Gajjala [view email]
[v1]
Tue, 16 Jun 2026 12:26:17 UTC (29 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。