Paper Info
Title
From a (<Emphasis Type="Italic">p</Emphasis>, 2)-Theorem to a Tight (<Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-Theorem
Abstract
A family \(\mathcal {F}\) of sets is said to satisfy the (p, q)-property if among any p sets of \(\mathcal {F}\) some q have a non-empty intersection. 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 \(q \ge d+1\), can be pierced by a fixed number (independent of the size of the family) \(f_d(p,q)\) of points. The minimum such piercing number is denoted by \(\mathsf {HD} _d(p,q)\). Already in 1957, Hadwiger and Debrunner showed that whenever \(q>\frac{d-1}{d}\,p+1\) the piercing number is \(\mathsf {HD} _d(p,q)=p-q+1\); no tight bounds on \(\mathsf {HD} _d(p,q)\) were found ever since. While for an arbitrary family of compact convex sets in \(\mathbb {R}^d\), \(d \ge 2\), a (p, 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific classes. The best-studied among them is the class of axis-parallel boxes in \(\mathbb {R}^d\), and specifically, axis-parallel rectangles in the plane. Wegner (Israel J Math 3:187–198, 1965) and (independently) Dol’nikov (Sibirsk Mat Ž 13(6):1272–1283, 1972) used a (p, 2)-theorem for axis-parallel rectangles to show that \(\mathsf {HD} _\mathrm{{rect}}(p,q)=p-q+1\) holds for all \(q \ge \sqrt{2p}\). These are the only values of q for which \(\mathsf {HD} _\mathrm{{rect}}(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 classes with Helly number 2, even without assuming that the sets in the class are convex or compact. To demonstrate the strength of this method, we show that \(\mathsf {HD} _{d\text {-box}}(p,q)=p-q+1\) holds for all \(q > c' \log ^{d-1} p\), and in particular, \(\mathsf {HD} _\mathrm{{rect}}(p,q)=p-q+1\) holds for all \(q \ge 7 \log _2 p\) (compared to \(q \ge \sqrt{2p}\), obtained by Wegner and Dol’nikov more than 40 years ago). In addition, for several classes, we present improved (p, 2)-theorems, some of which can be used as a bootstrapping to obtain tight (p, q)-theorems. In particular, we show that any class \(\mathcal {G}\) of compact convex sets in \(\mathbb {R}^d\) with Helly number 2 admits a (p, 2)-theorem with piercing number \(O(p^{2d-1})\), and thus, satisfies \(\mathrm {HD}_{\mathcal {G}}(p,q) = p-q+1\), for a universal constant c.
Year
DOI
Venue
2018
10.1007/s00454-018-0048-3
Symposium on Computational Geometry
Keywords
Field
DocType
(p,q)-Theorem, Hadwiger–Debrunner numbers, Axis-parallel rectangles, Convexity, Helly-type theorems, 52A37
Discrete mathematics,Combinatorics,Regular polygon,Mathematics,Bounded function
Conference
Volume
Issue
ISSN
63
4
1432-0444
Citations 
PageRank 
References 
0
0.34
11
Authors
2
Name
Order
Citations
PageRank
Chaya Keller134.52
Shakhar Smorodinsky242243.47