Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
Email: bed@numerik.uni-kiel.de

DOI: http://dx.doi.org/10.1090/S0002-9939-04-07309-5
PII: S 0002-9939(04)07309-5
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