Improved bounds on the Hadwiger Debrunner numbers

The classical Helly‘s theorem states that if in a family of compact convex sets in R^d every $d+1$ members have a non-empty intersection then the whole family has a non-empty intersection.

In an attempt to generalize Helly‘s theorem, in 1957 Hadwiger and Debrunner posed a conjecture that was proved more than 30 years later in a celebrated result of Alon and Kleitman: For any p,q (p >= q > d) there exists a constant C=C(p,q,d) such that the following holds: If in a family of compact convex sets, out of every p members some q intersect, then the whole family can be pierced with C points. Hadwiger and Debrunner themselves showed that if q is very close to p, then $C=p-q+1$ suffices.

The proof of Alon and Kleitman yields a huge bound $C=O(p^{d^2+d})$, and providing sharp upper bounds on the minimal possible C remains a wide open problem.

In this talk we show an improvement of the best known bound on C for all pairs $(p,q)$. In particular, for a wide range of values of q, we reduce C all the way to the almost optimal bound p-q+1<=C<=p-q+2. This is the first near tight estimate of C since the 1957 Hadwiger-Debrunner theorem.

Joint work with Chaya Keller and Gabor Tardos.