License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.51
URN: urn:nbn:de:0030-drops-87640
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8764/
Keller, Chaya ;
Smorodinsky, Shakhar
From a (p,2)-Theorem to a Tight (p,q)-Theorem
Abstract
A family F of sets is said to satisfy the (p,q)-property if among any p sets of 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 R^d that satisfies the (p,q)-property for some q >= d+1, can be pierced by a fixed number (independent on the size of the family) f_d(p,q) of points. The minimum such piercing number is denoted by {HD}_d(p,q). Already in 1957, Hadwiger and Debrunner showed that whenever q > (d-1)/d p+1 the piercing number is {HD}_d(p,q)=p-q+1; no exact values of {HD}_d(p,q) were found ever since.
While for an arbitrary family of compact convex sets in R^d, d >= 2, 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 boxes in R^d, and specifically, axis-parallel rectangles in the plane. Wegner (1965) and (independently) Dol'nikov (1972) used a (p,2)-theorem for axis-parallel rectangles to show that {HD}_{rect}(p,q)=p-q+1 holds for all q>sqrt{2p}. These are the only values of q for which {HD}_{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 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 show that {HD}_{d-box}(p,q)=p-q+1 holds for all q > c' log^{d-1} p, and in particular, {HD}_{rect}(p,q)=p-q+1 holds for all q >= 7 log_2 p (compared to q >= sqrt{2p}, obtained by Wegner and Dol'nikov more than 40 years ago).
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. In particular, we show that any family F of compact convex sets in R^d with Helly number 2 admits a (p,2)-theorem with piercing number O(p^{2d-1}), and thus, satisfies {HD}_{F}(p,q)=p-q+1 for all q>cp^{1-1/(2d-1)}, for a universal constant c.
BibTeX - Entry
@InProceedings{keller_et_al:LIPIcs:2018:8764,
author = {Chaya Keller and Shakhar Smorodinsky},
title = {{From a (p,2)-Theorem to a Tight (p,q)-Theorem}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8764},
URN = {urn:nbn:de:0030-drops-87640},
doi = {10.4230/LIPIcs.SoCG.2018.51},
annote = {Keywords: (p,q)-Theorem, convexity, transversals, (p,2)-theorem, axis-parallel rectangles}
}
|
Keywords: |
|
(p,q)-Theorem, convexity, transversals, (p,2)-theorem, axis-parallel rectangles |
|
Collection: |
|
34th International Symposium on Computational Geometry (SoCG 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.06.2018 |
