New Quantitative Bounds for the $(p,q)$-Theorem for Unions of Convex Sets

Abstract

A set in ${\mathbb{R}}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let ${\mathrm{HD}}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that ${\mathrm{HD}}_d^{(s)}(p,q)$ exists for any $p\ge q\ge d+1$ and any $s\ge 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., ${\mathrm{HD}}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge 2$, $s\ge 1$ and $\delta >0$, if $p>q$ and $q\ge C_d\log (esp)$, then ${\mathrm{HD}}_d^{(s)}(p,q)\le p-q+1+O_{d,\delta }((s\cdot \frac{p}{q}\cdot \log \frac{esp}{q}{)}^{{\rho }_d+\delta }),$ where ${\rho }_d<d$ is the exponent in the weak epsilon-net theorem of Rubin (2022). (ii) For $s\ge 1$, $p\ge q\ge 2$ and $q\ge C_{0}s\log (2s)\log (ep)$, $p-q+s\le {\mathrm{HD}}_1^{(s)}(p,q)\le p-q+2s+1$. This result provides the first near-tight estimate for ${\mathrm{HD}}_1^{(s)}(p,q)$ for $q>2$. (iii) For any fixed $s$, there are an integer ${\kappa }_s\in \{s,\dots ,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log (ep)$, ${\mathrm{HD}}_1^{(s)}(p,q)\in \{p-q+{\kappa }_s,p-q+{\kappa }_s+1\}.$ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s\ge 1$, ${\mathrm{HD}}_3^{(s)}(p,4)\ge s{p}^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on ${\mathrm{HD}}_d^{(1)}(p,d+1)$, for all $d\ge 3$.

21 pages