Improved bounds on the Hadwiger-Debrunner numbers

Abstract

Let $H{D}_d(p,q)$ denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in ${\mathbb{R}}^d$ which satisfy the $(p,q)$-property ($p\ge q\ge d+1$). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that $H{D}_d(p,q)$ exists for all $p\ge q\ge d+1$. Specifically, they prove that $H{D}_d(p,d+1)$ is $\tilde{O}(p^{d^2+d})$. We present several improved bounds: (i) For any $q\ge d+1$, $H{D}_d(p,q)=\tilde{O}(p^{d\left(\frac{q-1}{q-d}\right)})$. (ii) For $q\ge \log p$, $H{D}_d(p,q)=\tilde{O}(p+(p/q{)}^d)$. (iii) For every $\epsilon >0$ there exists a $p_0=p_0(\epsilon )$ such that for every $p\ge p_0$ and for every $q\ge p^{\frac{d-1}{d}+\epsilon }$ we have: $p-q+1\le H{D}_d(p,q)\le p-q+2$. The latter is the first near tight estimate of $H{D}_d(p,q)$ for an extended range of values of $(p,q)$ since the 1957 Hadwiger-Debrunner theorem. We also prove a $(p,2)$-theorem for families in ${\mathbb{R}}^2$ with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property.

14 pages