Loading...
Please wait, while we are loading the content...
Similar Documents
On Piercing Numbers of Families Satisfying the $(p,q)_r$ Property
| Content Provider | arXiv |
|---|---|
| Author | Keller, Chaya Smorodinsky, Shakhar |
| Date of Submission | 2017-03-18 |
| 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 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\'{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 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 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 \leq p-q+1$ holds with $r = \frac{1}{p^{\frac{q}{2d}}}{{p}\choose{q}}$. 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. |
| Related Links | https://arxiv.org/pdf/1703.06338.pdf |
| Page Count | 9 |
| arXiv | 1703.06338 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Combinatorics Other problems of combinatorial convexity Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
