The condensation phase transition in random graph coloring
From MaRDI portal
(Redirected from The condensation phase transition in random graph coloring)
The condensation phase transition in random graph coloring (scientific article; zbMATH DE number 6544482)
The condensation phase transition in random graph coloring (scientific article; zbMATH DE number 6544482)
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 .
The cavity method is a non-rigorous approach which has been proposed to study diluted mean-field models, in which the geometry of interactions is described by a sparse random graph or hypergraph. The specific model therein considered is the Potts antiferromagnet on the Erdős-Renyi random graph at zero temperature known as the random graph coloring problem. The contribution of the present paper is to prove that, in the random graph coloring problem, condensation occurs at the exact value predicted by the cavity method. The key of the proof is to establish an explicit link between the combinatorics of the graph coloring problem and the cavity formalism.
Recommendations
Cites work
- Antiferromagnetic Potts model on the Erdős-Rényi random graph
- Are disordered spin glass models relevant for the structural glass problem?
- Gibbs measures and phase transitions on sparse random graphs
- Gibbs states and the set of solutions of random constraint satisfaction problems
- scientific article; zbMATH DE number 986986 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- scientific article; zbMATH DE number 1952026 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 1380613 (Why is no real title available?)
- Information, Physics, and Computation
- Large deviations of empirical neighborhood distribution in sparse random graphs
- On the method of typical bounded differences
- Polymers on disordered trees, spin glasses, and traveling waves.
- Random-energy model: an exactly solvable model of disordered systems
- The condensation transition in random hypergraph 2-coloring
- The freezing threshold for \(k\)-colourings of a random graph
- The Parisi formula
- The two possible values of the chromatic number of a random graph
- Upper-bounding the k-colorability threshold by counting covers
Cited in
(41)- Phase transitions in discrete structures
- Charting the replica symmetric phase
- Constraining the clustering transition for colorings of sparse random graphs
- Spin systems on Bethe lattices
- The number of solutions for random regular NAE-SAT
- Estimating the r-colorability threshold for a random hypergraph
- Analytic description of the phase transition of inhomogeneous multigraphs
- On the number of solutions in random hypergraph 2-colouring
- The cavity method for the rigidity transition
- Lower bounds on the chromatic number of random graphs
- Phase transitions in discrete structures
- Harnessing the Bethe free energy
- The condensation phase transition in random graph coloring
- A positive temperature phase transition in random hypergraph 2-coloring
- Circular coloring of random graphs: statistical physics investigation
- The two-star model: exact solution in the sparse regime and condensation transition
- Phase transitions in the \(q\)-coloring of random hypergraphs
- The replica symmetric phase of random constraint satisfaction problems
- Deterministic counting of graph colourings using sequences of subgraphs
- Charting the replica symmetric phase
- Decoding from pooled data: sharp information-theoretic bounds
- On the connectivity of proper colorings of random graphs and hypergraphs
- On the number of solutions in random graph \(k\)-colouring
- Rigid colorings of hypergraphs and contiguity
- Local convergence of random graph colorings
- On the method of typical bounded differences
- Planting colourings silently
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- The condensation transition in random hypergraph 2-coloring
- On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
- Counting colorings of triangle-free graphs
- One-step replica symmetry breaking of random regular NAE-SAT. II
- Algorithmic obstructions in the random number partitioning problem
- Frozen 1-RSB structure of the symmetric Ising perceptron
- Phase transitions for the cavity approach to the clique problem on random graphs
- Searching for (sharp) thresholds in random structures: where are we now?
- Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k 3
- The number of random 2-SAT solutions is asymptotically log-normal
- Local convergence of random graph colorings
- Inference and mutual information on random factor graphs
- On the Potts antiferromagnet on random graphs
This page was built for publication: The condensation phase transition in random graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963760)
