TY - JOUR

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

AU - Keller, Chaya

AU - Smorodinsky, Shakhar

N1 - Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - 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 Rd that satisfies the (p, q)-property for some q≥ d+ 1 , can be pierced by a fixed number (independent of the size of the family) 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-1dp+1 the piercing number is HDd(p, q) = p- q+ 1 ; no tight bounds on HDd(p, q) were found ever since. While for an arbitrary family of compact convex sets in Rd, d≥ 2 , a (p, 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific classes. The best-studied among them is the class of axis-parallel boxes in Rd, and specifically, axis-parallel rectangles in the plane. Wegner (Israel J Math 3:187–198, 1965) and (independently) Dol’nikov (Sibirsk Mat Ž 13(6):1272–1283, 1972) 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 classes with Helly number 2, even without assuming that the sets in the class are convex or compact. To demonstrate the strength of this method, we show that HDd-box(p, q) = p- q+ 1 holds for all q> c′log d-1p, and in particular, HDrect(p, q) = p- q+ 1 holds for all q≥ 7 log 2p (compared to q≥2p, obtained by Wegner and Dol’nikov more than 40 years ago). In addition, for several classes, 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 class G of compact convex sets in Rd with Helly number 2 admits a (p, 2)-theorem with piercing number O(p2d-1) , and thus, satisfies HD G(p, q) = p- q+ 1 , for a universal constant c.

AB - 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 Rd that satisfies the (p, q)-property for some q≥ d+ 1 , can be pierced by a fixed number (independent of the size of the family) 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-1dp+1 the piercing number is HDd(p, q) = p- q+ 1 ; no tight bounds on HDd(p, q) were found ever since. While for an arbitrary family of compact convex sets in Rd, d≥ 2 , a (p, 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific classes. The best-studied among them is the class of axis-parallel boxes in Rd, and specifically, axis-parallel rectangles in the plane. Wegner (Israel J Math 3:187–198, 1965) and (independently) Dol’nikov (Sibirsk Mat Ž 13(6):1272–1283, 1972) 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 classes with Helly number 2, even without assuming that the sets in the class are convex or compact. To demonstrate the strength of this method, we show that HDd-box(p, q) = p- q+ 1 holds for all q> c′log d-1p, and in particular, HDrect(p, q) = p- q+ 1 holds for all q≥ 7 log 2p (compared to q≥2p, obtained by Wegner and Dol’nikov more than 40 years ago). In addition, for several classes, 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 class G of compact convex sets in Rd with Helly number 2 admits a (p, 2)-theorem with piercing number O(p2d-1) , and thus, satisfies HD G(p, q) = p- q+ 1 , for a universal constant c.

KW - (p,q)-Theorem

KW - Axis-parallel rectangles

KW - Convexity

KW - Hadwiger–Debrunner numbers

KW - Helly-type theorems

UR - http://www.scopus.com/inward/record.url?scp=85057560065&partnerID=8YFLogxK

U2 - 10.1007/s00454-018-0048-3

DO - 10.1007/s00454-018-0048-3

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85057560065

SN - 0179-5376

VL - 63

SP - 821

EP - 847

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -