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)

Full work available at URL https://doi.org/10.1112/S0025579300011943

zbMATH Keywords

asymptotically extremal bipartite graphdiscrepancy boundsdual shatter function

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

(5)

• Norm-graphs: Variations and applications
• Some remarks on the Zarankiewicz problem
• 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
• Applications of random algebraic constructions to hardness of approximation

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)