Combinatorial Optimization Reading Group - Joshua Nevin

Title: Approximate Coloring of 2-Colorable 4-Uniform Hypergraphs

Abstract:

In this talk, we discuss several inapproximability results of Bhangale for 2-colorable 4-uniform hypergraphs. These results provide the best known lower bounds, under certain assumptions, on the number of colors which must be used in the worst case by a polynomial-time algorithm providing an explicit coloring of a 4-uniform hypergraph which is known to be 2-colorable. In particular, we show that no such algorithm can use at most polylogarithmically many colors (polylogarithmic in the number of vertices), assuming that P is not equal to NP. This result extends to an analogous result for c-colorable k-uniform hypergraphs, for any c>1 and k>2.