On Wegner's inequality for axis-parallel rectangles

DOI10.1016/J.DISC.2020.112091MaRDI QIDQ2005682zbMATH OpenOpenAlexFDO

Authors Ke Chen, Adrian Dumitrescu

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2020.112091

zbMATH Keywords

\((paxis-parallel rectanglelargest empty boxmatching numberpiercing numberq)\)-propertyWegner's conjecture

Mathematics Subject Classification ID

Inequalities and extremum problems in real or complex geometry (51M16)

Review text

The inequality of the title is a conjecture by Wegner that relates the piercing number \(\tau(\mathcal{F})\) and the matching number \(\nu(\mathcal{F})\) of a family \(\mathcal{F}\) of axis-parallel rectangles in the plane by \[\tau(\mathcal{F})\leq 2\nu(\mathcal{F})-1.\] In the Introduction, the authors give a nice overview of the problem of finding the piercing number of a family of sets in \(\mathbb R^n\) with the \((p,q)\)-property: among every \(p\) sets in \(\mathcal{F}\) there exist \(q\) sets with non-empty intersection. Then they show that the Wegner conjecture is sharp for \(\nu(\mathcal{F})=4\) by exhibiting a family of rectangles with \(\tau=7\). The main tool used in the proof is a connection with the `maximum empty box problem'. Included are examples also for the previously known cases \(\nu(\mathcal{F})=2, 3\).

Recommendations

• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
• From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem
• Piercing axis-parallel boxes
• Independent and hitting sets of rectangles intersecting a diagonal line
• Bounding the piercing number

Cites work

• A Ramsey-Type Result for Convex Sets
• A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
• Approximation algorithms for maximum independent set of pseudo-disks
• Convex sets in the plane with three of every four meeting
• Covering and coloring problems for relatives of intervals
• Covering boxes by points
• scientific article; zbMATH DE number 4017764 (Why is no real title available?)
• scientific article; zbMATH DE number 3392482 (Why is no real title available?)
• scientific article; zbMATH DE number 2209723 (Why is no real title available?)
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Intersection Graphs of Rectangles and Segments
• Intersection properties of boxes in \(R^ n\).
• Intersection properties of families of convex (n,d)-bodies
• Maximum independent set of rectangles
• On point covers of multiple intervals and axis-parallel rectangles
• On point covers of parallel rectangles
• On the largest empty axis-parallel box amidst \(n\) points
• On the size of the largest empty box amidst a point set
• Piercing axis-parallel boxes
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Piercing families of convex sets with the \(d\)-intersection property in \(\mathbb R^{d}\)
• Piercing numbers in approval voting
• Piercing translates and homothets of a convex body
• Quasi-Monte-Carlo methods and the dispersion of point sequences
• Research Problems in Discrete Geometry
• Small-size -nets for axis-parallel rectangles and boxes
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
• Über eine Variante zum Hellyschen Satz

Cited in

(3)

• Fractional Helly theorem for Cartesian products of convex sets
• Lower bounds for piercing and coloring boxes
• Stabbing boxes with finitely many axis-parallel lines and flats

This page was built for publication: On Wegner's inequality for axis-parallel rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005682)