The condensation phase transition in random graph coloring
arXiv:1404.5513 · doi:10.1007/s00220-015-2464-z
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 -SAT or random graph -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 -colorability threshold as well as to the performance of message passing algorithms. In random graph -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 exceeding a certain constant .
References in corpus (10)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Phase Transitions in the Coloring of Random Graphs
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- Algorithmic barriers from phase transitions
- Polynomial iterative algorithms for coloring and analyzing random graphs
- On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
- 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
- The condensation transition in random hypergraph 2-coloring
- Antiferromagnetic Potts model on the Erdos-Renyi random graph
Cited by in corpus (13)
- Information-theoretic thresholds from the cavity method
- On the method of typical bounded differences
- Minimal contagious sets in random regular graphs
- Charting the replica symmetric phase
- Phase transitions in the -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
- Planting colourings silently
- The replica symmetric phase of random constraint satisfaction problems
- Circular Coloring of Random Graphs: Statistical Physics Investigation
- Deterministic counting of graph colourings using sequences of subgraphs