Bounded VC-dimension implies a fractional Helly theorem (Q1880214)

The classical theorem of Helly states that if \(C\) is a finite family of convex sets in \(R^d\), such that any \(d+1\) or fewer of the sets of \(C\) have a non-empty intersection then the intersection of all sets of \( C\) is non-empty. In this paper it is proved that every set system of bounded VC-dimension has fractional Helly property. To be more concrete, if the dual shatter function of a set system \(F\) is bounded by \(o(m^k)\), then \(F\) has fractional Helly number \(k\). This further implies a \((p,k)\)-theorem: for every \(F\) as above and every \(p \geq k\), there exists \(T\) such that if \(G \subseteq F\) is a finite subfamily where among every \(p\) sets, some \(k\) intersect, then \(G\) has a transversal of size \(T\). Examples, where the assumptions about bounded dual shatter functions applies, include families of sets in \(R^d\) definable by a bounded number of polynomial inequalities of bounded degree. In this case the fractional Helly number \(d+1\) is obtained.