pipette
ENEnglish

Coloring 3-colorable graphs with colors via a Gaussian-cover recursion

Emile Anand

Preprint

En palabras de los autores

We give a randomized polynomial-time algorithm that colors any promised -colorable graph on vertices with colors, improving on the recent bounds of by Bansal, Huang, and Lee and Narang and Tang who obtained colors for every fixed . To prove our result, we start from a fixed-level semidefinite relaxation, where we use a finite-depth recursion on Gaussian covers. Fixing a root vertex, we group vertices by correlation with the root vector. Here, each step extends a cover of directions by one edge and transfers it to a successor group. Our key analytic ingredient is a variance bound for Gaussian maxima: for a maximum of centered linear forms with coefficient norms at most , mean , and variance , we prove using Chen's Gaussian convexity theorem. Together with a variance-scale lower-tail estimate, this controls the threshold loss at each extension, which shows that root-conditioned vector colorings can either extract a large independent set from a group or bound its size, forcing a contradiction after constantly many steps. The resulting sparse-case guarantee combines with the dense progress bound of Kawarabayashi, Thorup, and Yoneda, and the recursion's numerical inequalities are verified via rational interval arithmetic.

Resultado principalEl resumen no menciona limitaciones.

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

Comentario de los autores: 29 pages, 1 figure