pipette
ESEspañol

Near-Optimal Bounds for Testing k-Colorability

Bangjie Xu

Preprint

In the authors' words

We study the sample complexity of testing -colorability in the dense graph model. A graph is -far from being -colorable if at least edge deletions are required to make it -colorable. We prove that, for every integer , a uniformly random induced subgraph on \[ O\!\left(\frac{k\log k}{\varepsilon}\right) \] vertices is non--colorable with probability at least whenever the original graph is -far from -colorable. The proof introduces a trial coloring process based on nested palette systems and iteratively selected pivots. This yields an upper bound of , which is no worse than the previous state of the art throughout the nonvacuous parameter range, and is an improvement whenever is superpolynomial in . Moreover, for every fixed , our bound matches the known lower bound, thereby establishing the optimal dependence on and, to the best of our knowledge, achieving this optimal dependence for the first time.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.