On Wegner's inequality for axis-parallel rectangles
type: Item
instance of: scholarly article
title: On Wegner's inequality for axis-parallel rectangles
zbMATH Open document ID: 1454.51014
author: Ke Chen
author: Adrian Dumitrescu
published in: Discrete Mathematics
publication date: 2020-10-08T00:00:00Z
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\).
reviewed by: Martin Lukarevski
Mathematics Subject Classification ID: 51M16
zbMATH DE Number: 7257924
zbMATH Keywords: \((p
zbMATH Keywords: q)\)-property
zbMATH Keywords: axis-parallel rectangle
zbMATH Keywords: largest empty box
zbMATH Keywords: Wegner's conjecture
zbMATH Keywords: piercing number
zbMATH Keywords: matching number
MaRDI profile type: Publication
full work available at URL: j.disc.2020.112091
OpenAlex ID: W3080579843
cites work: Intersection Graphs of Rectangles and Segments
cites work: On the size of the largest empty box amidst a point set
cites work: Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
cites work: Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
cites work: Research Problems in Discrete Geometry
cites work: Q4633902
cites work: Approximation algorithms for maximum independent set of pseudo-disks
cites work: Piercing axis-parallel boxes
cites work: Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
cites work: Q3029701
cites work: Intersection properties of boxes in \(R^ n\).
cites work: Q5661906
cites work: Piercing translates and homothets of a convex body
cites work: On the largest empty axis-parallel box amidst \(n\) points
cites work: Q5692705
cites work: Covering boxes by points
cites work: A variant of the Hadwiger-Debrunner \((p,q)\)-problem in the plane
cites work: Covering and coloring problems for relatives of intervals
cites work: Über eine Variante zum Hellyschen Satz
cites work: Intersection properties of families of convex \((n,d)\)-bodies
cites work: Piercing families of convex sets with the \(d\)-intersection property in \(\mathbb R^{d}\)
cites work: On point covers of parallel rectangles
cites work: On point covers of multiple intervals and axis-parallel rectangles
cites work: Convex sets in the plane with three of every four meeting
cites work: A Ramsey-Type Result for Convex Sets
cites work: Quasi-Monte-Carlo methods and the dispersion of point sequences
cites work: Piercing numbers in approval voting
cites work: Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
DOI: 10.1016/J.DISC.2020.112091
description: scientific article; zbMATH DE number 7257924