On discrepancy bounds via dual shatter function

DOI10.1112/S0025579300011943zbMATH Open0874.11054MaRDI QIDQ4346282FDOQ4346282

Authors: Jiří Matoušek 

Publication date: 11 November 1997

Published in: Mathematika (Search for Journal in Brave)

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

zbMATH Keywords

discrepancy boundsdual shatter functionasymptotically extremal bipartite graph

Mathematics Subject Classification ID

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

Cites Work

• Norm-graphs and bipartite Turán numbers
• On Graphs that do not Contain a Thomsen Graph
• Discrepancy and approximations for bounded VC-dimension
• Geometric methods in the study of irregularities of distribution
• 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
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Some remarks on the Zarankiewicz problem

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)