ECCC-Report TR19-048https://eccc.weizmann.ac.il/report/2019/048Comments and Revisions published for TR19-048en-usTue, 02 Apr 2019 12:46:20 +0300
Paper TR19-048
| Simplified inpproximability of hypergraph coloring via t-agreeing families |
Amey Bhangale,
Per Austrin,
Aditya Potukuchi
https://eccc.weizmann.ac.il/report/2019/048We 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:
$\bullet$ coloring a $3$ colorable $4$-uniform hypergraph with $(\log n)^\delta$ many colors
$\bullet$ coloring a $3$ colorable $3$-uniform hypergraph with $\tilde{O}(\sqrt{\log \log n})$ many colors
$\bullet$ coloring a $2$ colorable $6$-uniform hypergraph with $(\log n)^\delta$ many colors
$\bullet$ coloring a $2$ colorable $4$-uniform hypergraph with $\tilde{O}(\sqrt{\log \log n})$ many colors
where $n$ is the number of vertices of the hypergraph and $\delta>0$ is a universal constant. Tue, 02 Apr 2019 12:46:20 +0300https://eccc.weizmann.ac.il/report/2019/048