Improved Bounds and Algorithms for Hypergraph Two-Coloring

We show that for all large n, every n-uniform hypergraph with at most 0. 7/spl radic/(n/lnn)/spl times/2/sup n/ 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 NC/sup 1/ versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n/sup 1/3-0(1)//spl times/2/sup n/ due to Beck (1978). We further generalize this to a "local" version, improving on one of the first applications of the Lovasz Local Lemma.

Authors

• Jaikumar Radhakrishnan
• Aravind Srinivasan

Keywords

• Erbium
• Approximation algorithms
• Computer science
• Lab-on-a-chip
• Application software
• Mathematics
• Contracts
• Parallel algorithms
• History
• Polynomials
• Parallelization
• L-arginine
• Redness
• Probability Of Events
• Types Of Events
• Probability Of Failure
• Independent Random Variables
• Probability 1
• Polynomial-time Algorithm
• Parallel Algorithm
• Event B
• Bad Events
• Vertex Values