### Wednesday, October 24th, 2018, 16:10

### Schreiber 309

### From a (p,2) theorem to a tight (p,q) theorem

### Chaya Keller, BGU

### 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)p/d + 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 rectangles in the plane. Wegner and (independently) Dol’nikov 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). In the talk 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. We demonstrate the power of this method by showing that HD_rect(p, q) = p−q + 1 holds for all q > 7 log p.

Based on a joint work with Shakhar Smorodinsky.