Improved bounds and algorithms for hypergraph two-coloring
| Title | Improved bounds and algorithms for hypergraph two-coloring |
| Publication Type | Conference Papers |
| Year of Publication | 1998 |
| Authors | Radhakrishnan J, Srinivasan A |
| Conference Name | 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings |
| Date Published | 1998/11/08/11 |
| Publisher | IEEE |
| ISBN Number | 0-8186-9172-7 |
| Keywords | algorithms, 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 |
| Abstract | 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 |
| DOI | 10.1109/SFCS.1998.743519 |