On Piercing Numbers of Families Satisfying the $(p,q{)}_r$ Property

Abstract

The Hadwiger-Debrunner number $H{D}_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 $H{D}_d(p,q)\ge p-q+1$ for all $q$, and equality is attained for $q>\frac{d-1}{d}p+1$. Almost tight upper bounds for $H{D}_d(p,q)$ for a `sufficiently 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ón, Piercing numbers for balanced and unbalanced families, Disc. Comput. Geom., 45(2) (2011), pp. 358-364], Montejano and Soberó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 intersect. They showed that $H{D}_d(p,q{)}_r\le p-q+1$ holds for all $r>\left(\genfrac{}{}{0ex}{}{p}{q}\right)-\left(\genfrac{}{}{0ex}{}{p+1-d}{q+1-d}\right)$; however, this is far from being tight. In this paper we present improved asymptotic upper bounds on $H{D}_d(p,q{)}_r$ which hold when only a tiny portion of the $q$-tuples intersect. In particular, we show that for $p,q$ sufficiently large, $H{D}_d(p,q{)}_r\le p-q+1$ holds with $r=\frac{1}{p^{\frac{q}{2d}}}\left(\genfrac{}{}{0ex}{}{p}{q}\right)$. Our bound misses the known lower bound for the same piercing number by a factor of less than $p{q}^d$. Our results use Kalai's Upper Bound Theorem for convex sets, along with the Hadwiger-Debrunner theorem and the recent improved upper bound on $H{D}_d(p,q)$ mentioned above.

9 pages