arXiv:2610.37869 · v1

Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{Ω(1)} n$ Colors

首次提交 2026-10-28 03:14

版本更新 2026-10-28 03:14

雷达观测 2026-10-30 10:23

摘要

We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.

作者备注：20 pages