ECCC-Report TR17-147https://eccc.weizmann.ac.il/report/2017/147Comments and Revisions published for TR17-147en-usTue, 03 Oct 2017 11:44:03 +0300
Paper TR17-147
| Hardness of Rainbow Coloring Hypergraphs |
Venkatesan Guruswami,
Rishi Saket
https://eccc.weizmann.ac.il/report/2017/147A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be nearly balanced rainbow colorable. Specifically, we show that for any $Q,k \geq 2$ and $\ell \leq k/2$, given a $Qk$-uniform hypergraph which admits a $k$-rainbow coloring satisfying the following condition:
--- in each hyperedge $e$, for some $\ell_e \leq \ell$ all but $2\ell_e$ colors occur exactly $Q$ times and the rest $(Q\pm 1)$ times,
it is NP-hard to compute an independent set of $(1 - (\ell+1)/k + \epsilon)$-fraction of vertices, for any constant $\epsilon > 0$. In particular, this implies the hardness of even $(k/\ell)$-rainbow coloring such hypergraphs.
The result is based on a novel long code PCP test that ensures the strong balancedness property desired of the $k$-rainbow coloring in the completeness case. The soundness analysis relies on a mixing bound based on uniform reverse hypercontractivity due to Mossel, Oleszkiewicz, and Sen, which was also used in earlier proofs of the hardness of $\omega(1)$-coloring $2$-colorable $4$-uniform hypergraphs due to Saket, and $k$-rainbow colorable $2k$-uniform hypergraphs due to Guruswami and Lee.Tue, 03 Oct 2017 11:44:03 +0300https://eccc.weizmann.ac.il/report/2017/147