Charles Explorer logo
🇬🇧

A Stepping-Up Lemma for Topological Set Systems

Publication at Faculty of Mathematics and Physics |
2021

Abstract

Intersection patterns of convex sets in Rd have the remarkable property that for d+1<=k<=ℓ, in any sufficiently large family of convex sets in Rd, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the ℓ-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system F in Rd.

Quantitatively, our bounds depend on how complicated the intersection of ℓ elements of F can be, as measured by the sum of the LEFT CEILINGd2RIGHT CEILING first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1.

We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivash to recast a simplicial complex as a homological minor of a cubical complex.