From a (p, 2)-Theorem to a Tight (p, q)-Theorem

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 ℝ^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 ℝ^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 ℝ^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 > √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₂ p (compared to q ≥ √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 ℝ^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.