Lemmy: Bestiverse
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS BotMB to Lobste.rsEnglish · 1 month ago

A Counterexample to Wegner's Conjecture for Axis-Parallel Rectangles

arxiv.org

external-link
message-square
0
link
fedilink
1
external-link

A Counterexample to Wegner's Conjecture for Axis-Parallel Rectangles

arxiv.org

RSS BotMB to Lobste.rsEnglish · 1 month ago
message-square
0
link
fedilink
In 1965, Wegner conjectured that every finite family \(\mathcal R\) of axis-parallel rectangles in the plane satisfies \(τ(\mathcal R) \le 2ν(\mathcal R)-1\), where \(τ(\mathcal R)\) denotes the minimum number of points needed to pierce all rectangles in \(\mathcal R\), and \(ν(\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, \(τ(\mathcal R) \ge n/2 \ge 2ν(\mathcal R)\), contradicting Wegner's conjectured bound. We also give a slightly more general construction for which \(τ(\mathcal R) \ge 2.21ν(\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\).

Comments

alert-triangle
You must log in or # to comment.

Lobste.rs

lobsters

Subscribe from Remote Instance

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !lobsters@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

RSS Feed of lobste.rs

Source of the RSS Bot

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 17 users / day
  • 132 users / week
  • 401 users / month
  • 1.69K users / 6 months
  • 2 local subscribers
  • 391 subscribers
  • 15.3K Posts
  • 1.06K Comments
  • Modlog
  • mods:
  • patrick
  • RSS Bot
  • BE: 0.19.15
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org