Remote Access Proceedings of the American Mathematical Society
Green Open Access

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

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?)

  • [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 $k$-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

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

American Mathematical Society