Quantitative Helly-type theorems

The classical Helly's theorem, dated 1923, asserts that if F is a family of compact convex sets in R^d such that any d+1 sets of F have a non-empty intersection, then all sets of F can be pierced by a single point. Helly's theorem is a cornerstone in convexity theory, and the need to generalize and extend it has led mathematicians to deep and fascinating new research directions. One of the best-known extensions is the Alon-Kleitman (p,q) theorem (1992) which asserts that for F as above, if among any p sets of F some q intersect (for q>d), then all sets of F can be pierced by a bounded number c(p,q,d) of points.

In this talk we survey the quest for quantitative Helly-type theorems which aim at finding effective bounds on the piercing numbers in various scenarios. We present new bounds on c(p,q,d) for the Alon-Kleitman theorem, which are almost tight for a wide range of parameters. We also show that for several large classes of families, quantitative (p,2) theorems in the plane can be obtained, providing a strong connection between the piercing number of a family to its well-studied packing number, and giving rise to new Ramsey-type theorems.

Based on joint works with Shakhar Smorodinsky and Gabor Tardos.