Colloquium: Chaya Keller (BGU) - 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.

Date: 

Thu, 29/11/2018 - 14:30 to 15:30

Location: 

Manchester Building (Hall 2), Hebrew University Jerusalem