Simplified inpproximability of hypergraph coloring via t-agreeing families
share
We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal t-agreeing families of [q]^n. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs of quasi NP-hardness of the following problems: ∙ coloring a 3 colorable 4-uniform hypergraph with ( n)^δ many colors ∙ coloring a 3 colorable 3-uniform hypergraph with Õ(√( n)) many colors ∙ coloring a 2 colorable 6-uniform hypergraph with ( n)^δ many colors ∙ coloring a 2 colorable 4-uniform hypergraph with Õ(√( n)) many colors where n is the number of vertices of the hypergraph and δ>0 is a universal constant.
READ FULL TEXT