Colloquium: Chaya Keller (Technion) - Improved lower and upper bounds on the Hadwiger-Debrunner numbers

A family of sets F is said to satisfy the (p,q)-property if among any p sets in F, some q have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any p > q > d there exists a constant c = c_d(p,q), such that any family of compact convex sets in R^d that satisfies the (p,q)-property, can be pierced by at most c points. Helly's Theorem is equivalent to the fact that c_d(p,p)=1 (p > d). In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on the minimal such c_d(p,q), called `the Hadwiger-Debrunner numbers', is still a major open problem in combinatorial geometry. In this talk we present improved upper and lower bounds on the Hadwiger-Debrunner numbers, the latter using the hypergraph container method. Based on joint works with Shakhar Smorodinsky and Gabor Tardos.


2018-11-29 14:30 to 15:30


Manchester Building (Hall 2), Hebrew University Jerusalem