On Wegner's inequality for axis-parallel rectangles (Q2005682): Difference between revisions
From MaRDI portal
Latest revision as of 19:18, 23 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On Wegner's inequality for axis-parallel rectangles |
scientific article |
Statements
On Wegner's inequality for axis-parallel rectangles (English)
0 references
8 October 2020
0 references
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\).
0 references
\((p
0 references
q)\)-property
0 references
axis-parallel rectangle
0 references
largest empty box
0 references
Wegner's conjecture
0 references
piercing number
0 references
matching number
0 references
0 references
0 references