On Wegner's inequality for axis-parallel rectangles (Q2005682): Difference between revisions

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\).