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
