A new lower bound on Hadwiger-Debrunner numbers in the plane

Abstract

A family of sets $\mathcal{F}$ is said to satisfy the $(p,q)$ property if among any $p$ sets in $\mathcal{F}$ some $q$ have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any $p \geq q \geq d+1$ there exists $c=c_d(p,q)$, such that any family of compact convex sets in $\mathcal{R}^d$ that satisfies the $(p,q)$ property can be pierced by at most $c$ points. In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on $c_d(p,q)$, known as the `the Hadwiger-Debrunner numbers,' is still a major open problem in combinatorial geometry. The best currently known lower bound on the Hadwiger-Debrunner numbers in the plane is $c_2(p,q) = \Omega( \frac{p}{q}\log(\frac{p}{q}))$, while the best known upper bound is $O(p^{(1.5+\delta)(1+\frac{1}{q-2})})$.
In this paper we improve the lower bound significantly by showing that $c_2(p,q) \geq p^{1+\Omega(1/q)}$. Furthermore, the bound is obtained by a family of lines and is tight for all families that have a bounded VC-dimension. Unlike previous bounds on the Hadwiger-Debrunner numbers, which mainly used the weak epsilon-net theorem, our bound stems from a surprising connection of the $(p,q)$ problem to an old problem of Erd\H{o}s on points in general position in the plane. We use a novel construction for the Erd\H{o}s' problem, obtained recently by Balogh and Solymosi using the \emph{hypergraph container method}, to get the lower bound on $c_2(p,3)$. We then generalize the bound to $c_2(p,q)$ for any $q \geq 3$.