The hereditary discrepancy is nearly independent of the number of colors

Doerr, Benjamin

doi:10.1090/S0002-9939-04-07309-5

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