Shakhar Smorodinsky

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 R^d that satisfies the (p,q) property. Hadwiger and Debrunner showed that HD_d(p,q)≥p−q+1 for all q, and equality is attained for q>[Formula presented]p+1. Almost tight upper bounds for HD_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 [9], 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 HD_d(p,q)_r≤p−q+1 holds for all r>(pq)−(p−d+1q−d+1); however, this is far from being tight. In this paper we present improved asymptotic upper bounds on HD_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, HD_d(p,q)_r≤p−q+1 holds with r=p^−q/2d⋅(pq). Our bound misses the known lower bound for the same piercing number by a factor of less than pq^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 HD_d(p,q) mentioned above.