00-35   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Benjamin Doerr, Anand Srivastav:

Multi-Color Discrepancies

In this article we introduce combinatorial multi-color discrepancies and generalize several classical results from $2$--color discrepancy theory to $c$ colors ($c \ge 2$). We give a recursive method that constructs $c$--colorings from approximations of $2$--color discrepancies. This method works for a large class of theorems like the `six standard deviations' theorem of Spencer, the Beck--Fiala theorem, the results of Matou\v{s}ek, Welzl and Wernisch and Matou\v sek for bounded VC--dimension and Matou\v sek's and Spencer's upper bound for the arithmetic progressions. In particular, the $c$--color discrepancy of an arbitrary hypergraph ($n$ vertices, $m$ hyperedges) is $\OO(\sqrt{\tfrac n c \log m})$. If $m = \OO(n)$, then this bound improves to $\OO(\sqrt{\tfrac n c \log c})$. On the other hand there are examples showing that discrepancy in $c$ colors can not be bounded in terms of two-color discrepancies in general, even if $c$ is a power of~2. For the linear discrepancy version of the Beck--Fiala theorem the recursive approach also fails. Here we extend the method of floating colors via tensor products of matrices to multi-colorings and prove multi-color versions of the Beck--Fiala theorem and the Barany--Grunberg theorem. Using properties of the tensor product we derive a lower bound for the $c$--color discrepancy of general hypergraphs. For the hypergraph of arithmetic progressions in $\{1, \ldots, n\}$ this yields a lower bound of $\frac{1}{25 \sqrt c} \sqrt[4]{n}$ for the discrepancy in $c$ colors. The recursive method shows an upper bound of $\OO(c^{-0.16} \sqrt[4]{n})$.

Mathematics Subject Classification (1991): Primary 11K38, 05C15. Secondary 05C65

Bibliographical note: Combinatorics, Probability & Computing, 12 (2003), 365-399.

Keywords: discrepancy theory, hypergraph coloring, arithmetic progressions


Mail an Jens Burmeister
[Thu Feb 19 18:56:35 2009]
Impressum