Available in electronic format
Available in print format		 Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

The hereditary discrepancy is nearly independent of the number of colors

Author(s): Benjamin Doerr
Journal: Proc. Amer. Math. Soc. 132 (2004), 1905-1912.
MSC (2000): Primary 11K38; Secondary 05C65
Posted: January 29, 2004
Retrieve article in: PDF DVI PostScript

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:

[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
Email: bed@numerik.uni-kiel.de

DOI: 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
Posted: January 29, 2004
Additional Notes: Partially supported (associate member) by the graduate school ``Effiziente Algorithmen und Multiskalenmethoden'', Deutsche Forschungsgemeinschaft
Communicated by: John R. Stembridge
Copyright of article: Copyright 2004, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google