Simplified inpproximability of hypergraph coloring via t-agreeing families

摘要

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 ( log n ) many colors coloring a 3 colorable 3 -uniform hypergraph with O ( log log n ) many colors coloring a 2 colorable 6 -uniform hypergraph with ( log n ) many colors coloring a 2 colorable 4 -uniform hypergraph with O ( log log n ) many colorswhere n is the number of vertices of the hypergraph and 0" 0 is a universal constant.