Improved bounds on the Hadwiger-Debrunner numbers

יום א', 22/05/2016 - 14:00


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 Shakhar Smorodinsky and Gabor Tardos.