2017/03/18 by Keller, Chaya, Smorodinsky, Shakhar
#52A37 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1703.06338
The Hadwiger-Debrunner number HDd(p,q) is the minimal size of a piercing set that can always be guaranteed for a family of compact convex sets in ℝd that satisfies the (p,q) property. Hadwiger and Debrunner showed that HDd(p,q) ≥ p-q+1 for all q, and equality is attained for q > (d-1)/(d)p +1. Almost tight upper bounds for HDd(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 HDd(p,q)r ≤ p-q+1 holds for all r>p\chooseq-p+1-d\chooseq+1-d; however, this is far from being tight. In this paper we present improved asymptotic upper bounds on HDd(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, HDd(p,q)r ≤ p-q+1 holds with r = \frac1p(q)/(2d)p\chooseq. Our bound misses the known lower bound for the same piercing number by a factor of less than pqd. Our results use Kalai's Upper Bound Theorem for convex sets, along with the Hadwiger-Debrunner theorem and the recent improved upper bound on HDd(p,q) mentioned above.