Improved bounds on the Hadwiger-Debrunner numbers

Seminar
Speaker
Chaya Keller (Ben-Gurion University)
Date
22/05/2016 - 15:30 - 14:00Add to Calendar 2016-05-22 14:00:00 2016-05-22 15:30:00 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 Shakhar Smorodinsky and Gabor Tardos. Math building, 3rd floor seminar room (216/201) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Math building, 3rd floor seminar room (216/201)
Abstract

 

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.

Last Updated Date : 18/05/2016