pipette
ENEnglish

Near-Optimal Bounds for Testing k-Colorability

Bangjie Xu

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.