Bounded VC-dimension implies a fractional Helly theorem

We prove that every set system of bounded VC-dimension has a fractional Helly property. More precisely, if the dual shatter function of a set system F is bounded by o(m(k)), then F has fractional Helly number k. This means that for every alpha > 0 there exists a beta > 0 such that if F-1, F-2, . . . , F-n is an element of F are sets with boolean AND(iis an element ofI) F-i not equal 0 for at least alpha ((n)(k)) sets I subset of or equal to {1, 2, . . . , n) of size k, then there exists a point common to at least betan of the F-i. This further implies a (p, k)-theorem: for every F as above and every p greater than or equal to k there exists T such that if g C T is a finite subfamily where among every p sets, some k intersect, then 9 has a transversal of size T. The assumption about bounded dual shatter function applies, for example, to families of sets in R-d definable by abounded number of polynomial inequalities of bounded degree; in this case we obtain fractional Helly number d + 1.