Improved bounds and algorithms for hypergraph 2-coloring

Abstract

We show that for all large n, every n-uniform hypergraph with at most edges can be 2-colored. This makes progress on a problem of Erdos [Nordisk Mat. Tidskrift 11, 5-10 (1963)], improving the previous-best bound of n^1/3-o(1)× 2ⁿ due to Beck [Discrete Math. 24, 127-137 (1978)]. We further generalize this to a "local" version, improving on one of the first applications of the Lovász local lemma. We also present fast randomized algorithms that output a proper 2-coloring with high probability for n-uniform hypergraphs with at most 0.7 √nIn n × 2ⁿ edges, for all large n. In addition, we derandomize and parallelize these algorithms, to derive NC¹ versions of these results.