Recursive Randomized Coloring Beats Fair Dice Random Colorings

摘要

We investigate a refined recursive coloring approach to construct balanced colorings for hypergraphs. A coloring is called balanced if each hyperedge has (roughly) the same number of vertices in each color. We provide a recursive randomized algorithm that colors an arbitrary hypergraph (n vertices, m edges) with c colors with discrepancy at most O(the square root of (n/c log m)). The algorithm has expected running time O(nm log c). This result improves the bound of O (the square root of (n log (cm)) achieved with probability at least 1/2 by a random coloring that independently chooses a random color for each vertex (fair dice coloring). Our approach also lowers the current best upper bound for the c-color discrepancy in the case n = m to O (the square root of (n/c log c)) and extends the algorithm of Matousek, Welzl and Wernisch for hypergraphs having bounded dual shatter function to arbitrary numbers of colors.