Title: The Hardness of 3-Uniform Hypergraph Coloring

Speaker: Irit Dinur, NEC Research Institute

Date: Tuesday, October 8, 2002

Location: Hill Center, room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm [KNS] colors such a graph using O(n^{1/5}) colors. Our result immediately implies that for any constants k>2 and c_2>c_1>1, coloring a k-uniform c_1-colorable hypergraph with c_2 colors is NP-hard; leaving completely open only the k=2 graph case.

We are the first to obtain a hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k-uniform hypergraphs with k\ge 4 such a result has been shown by [GHS], who also discussed the inherent difference between the k=3 case and k > 3.

Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph and the Schrijver graph.

Joint work with Oded Regev and Clifford Smyth.