A seminal result of Dinur-Regev-Smyth from 2009 shows that for every \(q>0\), finding a \(q\)-coloring of a 2-colorable 3-uniform hypergraph is quasi NP-hard. The techniques in this proof have been very influential in this subject. I will describe some recent extensions which prove inapproximability of various hypergraph coloring problems.
A rainbow \(q\)-coloring of a \(k\)-uniform hypergraph is a \(q\)-coloring of the vertex set such that every hyperedge contains all \(q\) colors. Given a rainbow \((k−2\sqrt{k})\)-colorable \(k\)-uniform hypergraph, it is NP-hard to find a normal 2-coloring.
A \((q,p)\)-coloring is a coloring using \(q\) colors such that every hyperedge contains at least \(p\) colors. We prove that given a rainbow \((k-\sqrt{ck}, k-3\sqrt{ck})\)-colorable \(k\)-uniform hypergraph, it is NP-hard to find a normal \(c\)-coloring for any \(c=o(k)\). This relies on two combinatorial theorems: one of the theorems was proved by Sarkaria using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
This technique combined with some well-known combinatorial results also recovers several known results on hypergraph coloring in a simple and unified way. Moreover, this also leads to new approaches to improve these results.
Joint work with Per Austrin and Amey Bhangale.