The hereditary discrepancy is nearly independent of the number of colors
HTML articles powered by AMS MathViewer
- by Benjamin Doerr PDF
- Proc. Amer. Math. Soc. 132 (2004), 1905-1912 Request permission
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., \[ \operatorname {herdisc}(\cdot ,{b}) = \Theta ( \operatorname {herdisc}(\cdot ,{a})).\] This contrasts the ordinary discrepancy problem, where no correlation exists in many cases.References
- Martin Aigner, Combinatorial theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 234, Springer-Verlag, Berlin-New York, 1979. MR 542445, DOI 10.1007/978-1-4615-6666-3
- Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang, Balanced $k$-colorings, Discrete Math. 254 (2002), no. 1-3, 19–32. MR 1909857, DOI 10.1016/S0012-365X(01)00431-9
- József Beck and Tibor Fiala, “Integer-making” theorems, Discrete Appl. Math. 3 (1981), no. 1, 1–8. MR 604260, DOI 10.1016/0166-218X(81)90022-6
- László Babai, Thomas P. Hayes, and Peter G. Kimmel, The cost of the missing bit: communication complexity with help, Combinatorica 21 (2001), no. 4, 455–488. MR 1863574, DOI 10.1007/s004930100009
- József Beck and Joel Spencer, Integral approximation sequences, Math. Programming 30 (1984), no. 1, 88–98. MR 755116, DOI 10.1007/BF02591800
- József Beck and Vera T. Sós, Discrepancy theory, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1405–1446. MR 1373682
- Bernard Chazelle, The discrepancy method, Cambridge University Press, Cambridge, 2000. Randomness and complexity. MR 1779341, DOI 10.1017/CBO9780511626371
- Benjamin Doerr, Discrepancy in different numbers of colors, Discrete Math. 250 (2002), no. 1-3, 63–70. MR 1905964, DOI 10.1016/S0012-365X(01)00271-0
- B. Doerr and A. Srivastav. Multicolour discrepancies. Combinatorics, Probability and Computing, 12:365–399, 2003.
- L. Lovász, J. Spencer, and K. Vesztergombi, Discrepancy of set-systems and matrices, European J. Combin. 7 (1986), no. 2, 151–160. MR 856328, DOI 10.1016/S0195-6698(86)80041-5
- Jiří Matoušek, Geometric discrepancy, Algorithms and Combinatorics, vol. 18, Springer-Verlag, Berlin, 1999. An illustrated guide. MR 1697825, DOI 10.1007/978-3-642-03942-3
- Jiří Matoušek and Joel Spencer, Discrepancy in arithmetic progressions, J. Amer. Math. Soc. 9 (1996), no. 1, 195–204. MR 1311824, DOI 10.1090/S0894-0347-96-00175-0
- K. F. Roth, Remark concerning integer sequences, Acta Arith. 9 (1964), 257–260. MR 168545, DOI 10.4064/aa-9-3-257-260
- Joel Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289 (1985), no. 2, 679–706. MR 784009, DOI 10.1090/S0002-9947-1985-0784009-0
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
- 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
- © Copyright 2004 American Mathematical Society
- 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
- MathSciNet review: 2053960