Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The hereditary discrepancy is nearly independent of the number of colors

Author: Benjamin Doerr
Translated by:
Journal: Proc. Amer. Math. Soc. 132 (2004), 1905-1912
MSC (2000): Primary 11K38; Secondary 05C65
Published electronically: January 29, 2004
MathSciNet review: 2053960
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We investigate the discrepancy (or balanced coloring) problem for hypergraphs and matrices in arbitrary numbers of colors. We show that the hereditary discrepancy in two different numbers $a, b \in{\mathbb N} _{\ge 2}$ of colors is the same apart from constant factors, i.e.,

\begin{displaymath}{herdisc}(\cdot,{b}) = \Theta( {herdisc}(\cdot,{a})).\end{displaymath}

This contrasts the ordinary discrepancy problem, where no correlation exists in many cases.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 11K38, 05C65

Retrieve articles in all journals with MSC (2000): 11K38, 05C65

Additional Information

Benjamin Doerr
Affiliation: Mathematisches Seminar, Christian–Albrechts–Universität zu Kiel, Christian–Albrechts–Platz 4, D–24098 Kiel, Germany

Keywords: Discrepancy, hypergraphs
Received by editor(s): November 1, 2002
Received by editor(s) in revised form: April 9, 2003
Published electronically: January 29, 2004
Additional Notes: Partially supported (associate member) by the graduate school “Effiziente Algorithmen und Multiskalenmethoden”, Deutsche Forschungsgemeinschaft
Communicated by: John R. Stembridge
Article copyright: © Copyright 2004 American Mathematical Society