On discrepancy bounds via dual shatter function

DOI10.1112/S0025579300011943MaRDI QIDQ4346282zbMATH OpenFDO

Authors Jiří Matoušek

Publication date 11 November 1997

Published in Mathematika (Search for Journal in Brave)

zbMATH Keywords

discrepancy boundsdual shatter functionasymptotically extremal bipartite graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Irregularities of distribution, discrepancy (11K38)

Recommendations

• Tight upper bounds for the discrepancy of half-spaces
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Tighter bounds for the discrepancy of boxes and polytopes

Cites work

• Discrepancy and approximations for bounded VC-dimension
• Geometric methods in the study of irregularities of distribution
• Norm-graphs and bipartite Turán numbers
• On Graphs that do not Contain a Thomsen Graph
• Tight upper bounds for the discrepancy of half-spaces

Cited in

(4)

• Norm-graphs: Variations and applications
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Some remarks on the Zarankiewicz problem
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension

This page was built for publication: On discrepancy bounds via dual shatter function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4346282)