English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The Hadwiger-Debrunner number $HD_d(p,q)$ is the minimal size of a piercingset that can always be guaranteed for a family of compact convex sets in$\mathbb{R}^d$ that satisfies the $(p,q)$ property. Hadwiger and Debrunnershowed 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 a`sufficiently large' $q$ were obtained recently using an enhancement of thecelebrated 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 andunbalanced families, Disc. Comput. Geom., 45(2) (2011), pp. 358-364], Montejanoand 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 intersect. They showed that $HD_d(p,q)_r \leq p-q+1$ holds for all$r>{{p}\choose{q}}-{{p+1-d}\choose{q+1-d}}$; however, this is far from beingtight.  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 \leq p-q+1$ holds with$r = \frac{1}{p^{\frac{q}{2d}}}{{p}\choose{q}}$. Our bound misses the knownlower 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 theHadwiger-Debrunner theorem and the recent improved upper bound on $HD_d(p,q)$mentioned above.

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