KAIST Discrete Math Seminar

The Helly number of a collection of sets is the size of its largest inclusionwise minimal subfamily with empty intersection. The precise conditions that lead to bounded Helly numbers have been studied since the 1920’s, when Helly showed that the Helly number of any collection of compact convex sets in R^d has Helly number at most d+1.

I will discuss a proof that any collection of subsets of R^d where the intersection of any subfamily consists of at most r connected components, each of which is contractible, has Helly number at most r(d+1). I will show how this implies, in a unified manner, quantitative bounds for several Helly-type theorems in geometric transversal theory.

Our main ingredients are a new variant of the nerve, a “homological nerve theorem” for this structure and an extension of a projection theorem of Kalai and Meshulam.

This is joint work with Eric Colin de Verdiere and Gregory Ginot.