Discrepancy and approximations for bounded VC-dimension (Q1316651)

Given a family \(R\) of subsets of an \(n\)-point set \(X\) with a 2-coloring on \(X\), the discrepancy of \(R\) is defined as the maximum number by which the occurrences of the two colors differ in any set in \(R\). It is shown that if for any \(m\)-point set \(Y \subseteq X\) the number of distinct subsets induced by \(R\) on \(Y\) is bounded by \(O(m^ d)\) then there is a coloring with discrepancy \(O(n^{{1 \over2} - {1 \over 2d}} (\log n)^{1+{1 \over 2d}})\). Some implications of this result for \(\varepsilon\)-approximations are discussed.