From a (p,2)-theorem to a tight (p,q)-theorem

DOI10.4230/LIPICS.SOCG.2018.51MaRDI QIDQ5115819zbMATH OpenFDO

Authors Chaya Keller, Shakhar Smorodinsky

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1712.04552

zbMATH Keywords

convexitytransversalsaxis-parallel rectangles\((p,2)\)-theorem\((p,q)\)-theorem

Mathematics Subject Classification ID

Helly-type theorems and geometric transversal theory (52A35)

Abstract: A family $F$ of sets is said to satisfy the $(p,q)$-property if among any $p$ sets of $F$ some $q$ intersect. The celebrated $(p,q)$-theorem of Alon and Kleitman asserts that any family of compact convex sets in $mathbb{R}^d$ that satisfies the $(p,q)$-property for some $qgeqd+1$, can be pierced by a fixed number $f_d(p,q)$ of points. The minimum such piercing number is denoted by $H{D}_d(p,q)$. Already in 1957, Hadwiger and Debrunner showed that whenever $q>fracd-1dp+1$ the piercing number is $H{D}_d(p,q)=p-q+1$; no exact values of $H{D}_d(p,q)$ were found ever since. While for an arbitrary family of compact convex sets in $mathbb{R}^d$, $dgeq2$, a $(p,2)$-property does not imply a bounded piercing number, such bounds were proved for numerous specific families. The best-studied among them is axis-parallel rectangles in the plane. Wegner and (independently) Dol'nikov used a $(p,2)$-theorem for axis-parallel rectangles to show that $H{D}_{mathrmrect}(p,q)=p-q+1$ holds for all $q>sqrt2p$. These are the only values of $q$ for which $H{D}_{mathrmrect}(p,q)$ is known exactly. In this paper we present a general method which allows using a $(p,2)$-theorem as a bootstrapping to obtain a tight $(p,q)$-theorem, for families with Helly number 2, even without assuming that the sets in the family are convex or compact. To demonstrate the strength of this method, we obtain a significant improvement of an over 50 year old result by Wegner and Dol'nikov. Namely, we show that $H{D}_{mathrmd-box}(p,q)=p-q+1$ holds for all $q>c^{\prime }lo{g}^{d-1}p$, and in particular, $H{D}_{mathrmrect}(p,q)=p-q+1$ holds for all $qgeq7lo{g}_{2}p$ (compared to $qgeqsqrt2p$ of Wegner and Dol'nikov). In addition, for several classes of families, we present improved $(p,2)$-theorems, some of which can be used as a bootstrapping to obtain tight $(p,q)$-theorems.

Recommendations

• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
• Bounding the piercing number
• Transversal numbers for hypergraphs arising in geometry
• On piercing numbers of families satisfying the \((p,q)_{r}\) property
• Improved bounds on the Hadwiger-Debrunner numbers

Cites work

• scientific article; zbMATH DE number 3145756 (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?)
• A Ramsey-Type Result for Convex Sets
• A note on smaller fractional Helly numbers
• A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture
• A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
• Approximation algorithms for maximum independent set of pseudo-disks
• Bounded VC-dimension implies a fractional Helly theorem
• Colourful and fractional \((p,q)\)-theorems
• Convex sets in the plane with three of every four meeting
• Covering and coloring problems for relatives of intervals
• Covering boxes by points
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• On point covers of parallel rectangles
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Piercing axis-parallel boxes
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Piercing translates and homothets of a convex body
• Transversal numbers for hypergraphs arising in geometry
• Transversal numbers of translates of a convex body
• Über eine Variante zum Hellyschen Satz
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

Cited in

(7)

• Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
• On Wegner's inequality for axis-parallel rectangles
• The (p, q) property in families of d-intervals and d-trees
• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
• Passage to the limit \(\mathbb{P}_ 2\longrightarrow\mathbb{P}_ 1\)
• Bounding the piercing number
• Colourful and fractional \((p,q)\)-theorems

This page was built for publication: From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem

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