The condensation phase transition in random graph coloring

Abstract

Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random $k$-SAT or random graph $k$-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called "condensation" [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the $k$-colorability threshold as well as to the performance of message passing algorithms. In random graph $k$-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for $k$ exceeding a certain constant $k_0$.

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Large deviations of empirical neighborhood distribution in sparse random graphs

Cited by in corpus (11)

• Information-theoretic thresholds from the cavity method
• Minimal contagious sets in random regular graphs
• Charting the replica symmetric phase
• Phase transitions in the $q$-coloring of random hypergraphs
• Limits of discrete distributions and Gibbs measures on random graphs
• A positive temperature phase transition in random hypergraph 2-coloring
• Spin systems on Bethe lattices
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• The replica symmetric phase of random constraint satisfaction problems
• Planting colourings silently
• Circular Coloring of Random Graphs: Statistical Physics Investigation