文章基本信息
- 标题：Simplified inpproximability of hypergraph coloring via t-agreeing families
- 本地全文：下载
- 作者：Per Austrin ; Amey Bhangale ; Aditya Potukuchi 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2019
- 卷号：2019
- 页码：1-17
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
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 colors
where n is the number of vertices of the hypergraph and 0"> 0 is a universal constant.
- 关键词：hypergraph coloring ; intersecting families
