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

DOI10.4230/LIPICS.SOCG.2018.51zbMATH Open1491.52010arXiv1712.04552MaRDI QIDQ5115819FDOQ5115819

Publication date: 18 August 2020

Abstract: 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

m a t h b b R^{d}

that satisfies the

(p, q)

-property for some

q g e q d + 1

, can be pierced by a fixed number

f_{d} (p, q)

of points. The minimum such piercing number is denoted by

H D_{d} (p, q)

. Already in 1957, Hadwiger and Debrunner showed that whenever

q > f r a c d - 1 d p + 1

the piercing number is

H D_{d} (p, q) = p - q + 1

; no exact values of

H D_{d} (p, q)

were found ever since. While for an arbitrary family of compact convex sets in

m a t h b b R^{d}

,

d g e q 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

H D_{m a t h r m r e c t} (p, q) = p - q + 1

holds for all

q > s q r t 2 p

. These are the only values of

q

for which

H D_{m a t h r m r e c t} (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