From a $(p, 2) $-Theorem to a Tight $(p, q) $-Theorem Academic Article uri icon

abstract

  • 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 $\mathbb {R}^ d $ that satisfies the $(p, q) $- property for some $ q\geq d+ 1$, can be pierced by a fixed number $ 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>\frac {d-1}{d} p+ 1$ the piercing …

publication date

  • December 12, 2017