Leonardo Ignacio Martínez Sandoval
Ben-Gurion University of the Negev

Tuesday, May 8 at 3:00 PM


The Colorful Helly Theorem is one of the most surprising and counter-intuitive generalizations of Helly’s theorem. To state it, we start with a family F of convex sets in R^d split into the (non-neccesarily disjoint) union F=F_1 U … U F_{d+1}. We think of each F_i as a color class. We say that this family satisfies the colorful hypothesis if every colorful (d+1)-subfamily (consisting of exactly one from each color) is intersecting. The result states that if the family satisfies the colorful hypothesis, then at least one of the color classes is intersecting. A natural question is immediate: Why this happens for only one color class? What happens with the remaining color classes?

An easy example shows that there might not be a second intersecting color class. One of our results is that either there is a second color class that can be pierced by few points, or else all the remaining color classes can be pierced by few lines. Here “”few”” is a number that depends only on d and not on |F|. This result is remarkable in view of the few transversal line results for convex sets for d>2. In more generality, we classify the families satisfying the colorful hypothesis in terms of their transversal structure by flats. We also give an example that matches our results qualitatively.

The proof is based on the Alon-Kleitman’s approach for proving the (p,q)-theorem. This approach combines the existance of epsilon-nets, linear programming duality and the fractional Helly’s theorem. In the literature there are no results for epsilon-nets with lines to general convex sets, or general fractional Helly-results for transversal lines. Nevertheless, a delicate approach by induction allows us to repeatedly use epsilon-nets with hyperplanes in order to bound some fractional transversal numbers that naturally arise in the problem. From here we proceed by a similar combination of tricks as in the Alon-Kleitman’s approach.

This is a joint work with Edgardo Roldán-Pensado and Natan Rubin.

Download presentation
Also: diagram of geometric transversal theory.

Categories: Seminar