2004/03/31 by Florent Krzakala, Florent Krząkała, Andrea Pagnani +1 · 6 citations
Computer Science · Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.1103/physreve.70.046705
published as Phys. Rev. E 70, 046705 (2004) · 23 pages, 10 figures. Replaced with accepted version
arxiv created 2004/07/28 · openalex publication_date 2004/10/29 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We consider the problem of coloring Erdös-Rényi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-called one-step replica symmetry breaking (1RSB) ansatz. We derive a general criterion for the validity of this ansatz and, applying it to the ground state, we provide evidence that the 1RSB solution gives exact threshold values c(q) for the transition from the colorable to the uncolorable phase with q colors. We also study the asymptotic thresholds for q>>1 finding c(q) =2q ln q-ln q-1+o (1) in perfect agreement with rigorous mathematical bounds, as well as the nature of excited states, and give a global phase diagram of the problem.