The Hardness of $3$-Uniform Hypergraph Coloring.
Cliff Smyth, Carnegie Mellon University
with Irit Dinur, IAS and NEC and Oded Regev, IAS

Abstract:
We prove that coloring a $3$-uniform $2$-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm (due to Krivelevich, Nathaniel, and Sudakov) 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 only the $k=2$ or graph case open.

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 \ge 4$ such a result has been shown by Guruswami, Haastad, and Sudan, who also discussed the inherent difference between the $k=3$ case and $k \ge 4$.

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. We prove a certain maximization variant of the Kneser Conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has `many' non-monochromatic edges.

Host: Alan Frieze