An Improved Bound for Testing $k$-Colorability
Bangjie Xu
We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\varepsilon$-far from being $k$-colorable if at least $\varepsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that a uniformly random induced subgraph on $O(k\log k/\varepsilon)$ vertices is non-$k$-colorable with probability at least $2/3$ whenever the original graph is $\varepsilon$-far from $k$-colorable. The proof combines a palette-based coloring process with a container-style encoding-and-reconstruction argument. This yields $O(k\log k/\varepsilon)$, which is no worse than the previous state of the art $O(k\log (1/\varepsilon)/\varepsilon)$ throughout the nonvacuous parameter range, and is an improvement when $\log k=o(\log(1/\varepsilon))$. For each fixed $k$, combining this upper bound with the known $Ω(\log k/\varepsilon)$ lower bound gives $Θ(1/\varepsilon)$ dependence on $\varepsilon$.
尚无 AI 解读，展示原文摘要