On Piercing Numbers of Families Satisfying the $(p, q) _r $ Property Academic Article uri icon

abstract

  • The Hadwiger-Debrunner number $ HD_d (p, q) $ is the minimal size of a piercing set that can always be guaranteed for a family of compact convex sets in $\mathbb {R}^ d $ that satisfies the $(p, q) $ property. Hadwiger and Debrunner showed that $ HD_d (p, q)\geq p- q+ 1$ for all $ q $, and equality is attained for $ q>\frac {d-1}{d} p+ 1$. Almost tight upper bounds for $ HD_d (p, q) $ for asufficiently large'$ q $ were obtained recently using an enhancement of the celebrated Alon-Kleitman theorem, but no sharp upper bounds for a general $ q $ are known. In [L. Montejano and P. Sober\'{o} n, Piercing numbers for balanced and unbalanced families, Disc. Comput. Geom., 45 (2)(2011), pp. 358-364], Montejano and Sober\'{o} n defined a refinement of the $(p, q) $ property: $ F $ satisfies the $(p, q) _r $ property if among any $ p $ elements of $ F $, at least $ r $ of the $ q $-tuples …

publication date

  • March 18, 2017