Improved bounds and algorithms for hypergraph two-coloring

TitleImproved bounds and algorithms for hypergraph two-coloring
Publication TypeConference Papers
Year of Publication1998
AuthorsRadhakrishnan J, Srinivasan A
Conference Name39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings
Date Published1998/11/08/11
ISBN Number0-8186-9172-7
Keywordsalgorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability

We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn)×2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1)×2n due to Beck (1978). We further generalize this to a “local” version, improving on one of the first applications of the Lovasz Local Lemma