Multicolour discrepancies

In this article we introduce combinatorial multicolour discrepancies and generalize several classical results from 2-colour discrepancy theory to c colours (c ≥ 2). We give a recursive method that constructs c-colourings from approximations of 2-colour discrepancies. This method works for a large class of theorems, such as the 'six standard deviations' theorem of Spencer (1985), the Beck-Fiala (1981) theorem, the results of Matoušek, Wernisch and Welzl (1994) and Matoušek (1995) for bounded VC-dimension, and Matoušek and Spencer's (1996) upper bound for the arithmetic progressions. In particular, the c-colour discrepancy of an arbitrary hypergraph (n vertices, m hyperedges) is O(√n/c log m). If m = O(n), then this bound improves to O(√n/c-log c). On the other hand there are examples showing that discrepancy in c colours can not be bounded in terms of two-colour 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 colours via tensor products of matrices to multicolourings, and prove multicolour versions of the Beck-Fiala theorem and the Bárány-Grinberg theorem. Using properties of the tensor product we derive a lower bound for the c-colour discrepancy of general hypergraphs. For the hypergraph of arithmetic progressions in {1, . . ., n} this yields a lower bound of 1/25√c 4√n discrepancy in c colours. The recursive method shows an upper bound of O(c^-0.16 4√n).