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 nonempty 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 > (d1)/d p+1 the piercing number is {HD}_d(p,q)=pq+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 beststudied among them is axisparallel boxes in R^d, and specifically, axisparallel rectangles in the plane. Wegner (1965) and (independently) Dol'nikov (1972) used a (p,2)theorem for axisparallel rectangles to show that {HD}_{rect}(p,q)=pq+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}_{dbox}(p,q)=pq+1 holds for all q > c' log^{d1} p, and in particular, {HD}_{rect}(p,q)=pq+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^{2d1}), and thus, satisfies {HD}_{F}(p,q)=pq+1 for all q>cp^{11/(2d1)}, 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:151:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8764},
URN = {urn:nbn:de:0030drops87640},
doi = {10.4230/LIPIcs.SoCG.2018.51},
annote = {Keywords: (p,q)Theorem, convexity, transversals, (p,2)theorem, axisparallel rectangles}
}
Keywords: 

(p,q)Theorem, convexity, transversals, (p,2)theorem, axisparallel rectangles 
Collection: 

34th International Symposium on Computational Geometry (SoCG 2018) 
Issue Date: 

2018 
Date of publication: 

08.06.2018 