2017/12/12 by Keller, Chaya, Smorodinsky, Shakhar · 2 citations
#52A37 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1712.04552
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 ℝd that satisfies the (p,q)-property for some q ≥ d+1, can be pierced by a fixed number fd(p,q) of points. The minimum such piercing number is denoted by HDd(p,q). Already in 1957, Hadwiger and Debrunner showed that whenever q>(d-1)/(d)p+1 the piercing number is HDd(p,q)=p-q+1; no exact values of HDd(p,q) were found ever since. While for an arbitrary family of compact convex sets in ℝ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 rectangles in the plane. Wegner and (independently) Dol'nikov used a (p,2)-theorem for axis-parallel rectangles to show that HDrect(p,q)=p-q+1 holds for all q>√(2p). These are the only values of q for which HDrect(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 HDd-box(p,q)=p-q+1 holds for all q > c' logd-1 p, and in particular, HDrect(p,q)=p-q+1 holds for all q ≥ 7 log2 p (compared to q ≥ √(2p) 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.