Multi-Color Discrepancies – Extended Abstract –

We investigate the discrepancy problem in arbitrary numbers of colors, that is, we try to color the vertices of a hypergraph in such a way that each hyperedge contains the same number of vertices in each color. In this paper we present new results extending [DS99]. In particular, we exhibit near-tight multi-color discrepancy bounds for several classical problems. They extend Spencerʹs ‘six standard deviations’ result and the upper bound for the discrepancy of the arithmetic progressions due to Matousek and Spencer to arbitrary numbers of colors. We also give lower bounds for these discrepancies.