A fractional Helly theorem for set systems with slowly growing homological shatter function

Abstract

We study parameters of the convexity spaces associated with families of sets in ${\mathbb{R}}^d$ where every intersection between $t$ sets of the family has its Betti numbers bounded from above by a function of $t$. Although the Radon number of such families may not be bounded, we show that these families satisfy a fractional Helly theorem. To achieve this, we introduce graded analogues of the Radon and Helly numbers. This generalizes previously known fractional Helly theorems.

7 pages, 0 figures