Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Abstract

We consider the problem of coloring Erdos-Renyi 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 q-COL/UNCOL phase transition. We also study the asymptotic thresholds for q >> 1 finding c_q = 2qlog(q)-log(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.

23 pages, 10 figures. Replaced with accepted version

References in corpus (13)

• Random graphs with arbitrary degree distributions and their applications
• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Glass models on Bethe lattices
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• The Phase Diagram of Random Heteropolymers
• Scaling and infrared divergences in the replica field theory of the Ising spin glass
• Glassy phases in Random Heteropolymers with correlated sequences

Cited by in corpus (39)

• Critical phenomena in complex networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• A Landscape Analysis of Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• On the freezing of variables in random constraint satisfaction problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Landscape of solutions in constraint satisfaction problems
• Perspective: Gardner Physics in Amorphous Solids and Beyond
• Reconstruction of Random Colourings
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Potts Glass on Random Graphs
• The condensation phase transition in random graph coloring
• Cusps and shocks in the renormalized potential of glassy random manifolds: How Functional Renormalization Group and Replica Symmetry Breaking fit together
• The hard-core model on random graphs revisited
• Constrained quantum annealing of graph coloring
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Approximating the XY model on a random graph with a $q$-state clock model
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Approximate Survey Propagation for Statistical Inference
• Phase transitions in the $q$-coloring of random hypergraphs
• The cavity method for large deviations
• A hard-sphere model on generalized Bethe lattices: Statics
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Planting colourings silently
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• The Chromatic Number of Random Regular Graphs
• Localization in the constrained quantum annealing of graph coloring
• Optimal Location of Sources in Transportation Networks
• On the chromatic number of random regular graphs
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Palette-colouring: a belief-propagation approach
• The effect of quantum fluctuations on the coloring of random graphs
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Critical properties of disordered XY model on sparse random graphs
• Breaking of 1RSB in random MAX-NAE-SAT
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• The replica symmetric solution for Orthogonally Constrained Heisenberg Model on Bethe lattice