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

DOI:
https://doi.org/10.1090/S0002-9939-04-07309-5

Published electronically:
January 29, 2004

MathSciNet review:
2053960

Full-text PDF

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 of colors is the same apart from constant factors, i.e.,

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

**[Aig97]**M. Aigner.*Combinatorial Theory*. Classics in Mathematics. Springer-Verlag, Berlin, 1997. Reprint of the 1979 original. MR**80h:05002****[BCC02]**T. Biedl, E. Cenek, T. Chan, E. Demaine, M. Demaine, R. Fleischer, and M. Wang.*Balanced**-colorings*. Discrete Mathematics, 254:19-32, 2002. MR**2003e:68104****[BF81]**J. Beck and T. Fiala.*``Integer making'' theorems*. Discrete Applied Mathematics, 3:1-8, 1981. MR**82d:05088****[BHK01]**L. Babai, T. P. Hayes, and P. G. Kimmel.*The cost of the missing bit: communication complexity with help*. Combinatorica, 21:455-488, 2001. MR**2002i:68039****[BS84]**J. Beck and J. Spencer.*Integral approximation sequences*. Math. Programming, 30:88-98, 1984. MR**85j:11074****[BS95]**J. Beck and V. T. Sós.*Discrepancy theory*, in R. Graham, M. Grötschel, and L. Lovász, editors,*Handbook of Combinatorics*, Elsevier, Amsterdam, 1995, pp. 1405-1446. MR**96m:11060****[Cha00]**B. Chazelle.*The Discrepancy Method*. Cambridge University Press, Cambridge, 2000. MR**2002c:68002****[Doe02]**B. Doerr.*Discrepancy in different numbers of colors*. Discrete Mathematics, 250:63-70, 2002.MR**2003c:05154****[DS03]**B. Doerr and A. Srivastav.*Multicolour discrepancies*. Combinatorics, Probability and Computing, 12:365-399, 2003.**[LSV86]**L. Lovász, J. Spencer, and K. Vesztergombi.*Discrepancy of set-systems and matrices*. European J. Combin., 7:151-160, 1986.MR**88b:05036****[Mat99]**J. Matousek.*Geometric Discrepancy*. Algorithms and Combinatorics, Vol. 18, Springer-Verlag, Berlin, 1999. MR**2001a:11135****[MS96]**J. Matousek and J. Spencer.*Discrepancy in arithmetic progressions*. J. Amer. Math. Soc., 9:195-204, 1996. MR**96c:11089****[Rot64]**K. F. Roth.*Remark concerning integer sequences*. Acta Arithmetica, 9:257-260, 1964. MR**29:5806****[Spe85]**J. Spencer.*Six standard deviations suffice*. Trans. Amer. Math. Soc., 289:679-706, 1985. MR**86k:05004**

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:
https://doi.org/10.1090/S0002-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