ON DISCREPANCY BOUNDS VIA DUAL SHATTER FUNCTION

Recently, it has been shown that tight or almost tight upper bounds fo r the discrepancy of many geometrically defined set systems can be der ived from simple combinatorial parameters of these set systems. Namely , if the primal shatter function of a set system R on an n-point set X is bounded by const. m(d), then the discrepancy disc (R) = O(n((d-1)/ 2d)) (which is known to be tight), and if the dual shatter function is bounded by const. m(d) then disc (R) O(n((d-1)/2d)root log n). We pro ve that for d=2, 3, the latter bound also cannot be improved in genera l. We also show that bounds on the shatter functions alone do not impl y the average (L-1)-discrepancy to be much smaller than the maximum di screpancy: this contrasts results of Beck and Chen for certain geometr ic cases. In the proof we give a construction of a certain asymptotica lly extremal bipartite graph, which may be of independent interest.