The condensation phase transition in random graph coloring

DOI10.1007/S00220-015-2464-ZMaRDI QIDQ5963760zbMATHOpenAlexFDO

Authors Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Rassmann, Dan Vilenchik

Publication date 23 February 2016

Published in Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5513

zbMATH Keywords

phase transitionrandom graphgraph coloringcavity methoddiluted mean-field model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Phase transitions (general) in equilibrium statistical mechanics (82B26)

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$.

Recommendations

• The condensation phase transition in random graph coloring
• A positive temperature phase transition in random hypergraph 2-coloring
• The condensation transition in random hypergraph 2-coloring
• Coloring random graphs

Cites work

• 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?)
• 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
• 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 Parisi formula
• The condensation transition in random hypergraph 2-coloring
• The freezing threshold for \(k\)-colourings of a random graph
• The two possible values of the chromatic number of a random graph
• Upper-bounding the \(k\)-colorability threshold by counting covers

Cited in

(38)

• On the number of solutions in random hypergraph 2-colouring
• The cavity method for the rigidity transition
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• Circular coloring of random graphs: statistical physics investigation
• Lower bounds on the chromatic number of random graphs
• Frozen 1-RSB structure of the symmetric Ising perceptron
• On the method of typical bounded differences
• Searching for (sharp) thresholds in random structures: where are we now?
• Analytic description of the phase transition of inhomogeneous multigraphs
• On the connectivity of proper colorings of random graphs and hypergraphs
• Spin systems on Bethe lattices
• On the Potts antiferromagnet on random graphs
• Rigid colorings of hypergraphs and contiguity
• The replica symmetric phase of random constraint satisfaction problems
• Planting colourings silently
• Phase transitions in discrete structures
• The condensation transition in random hypergraph 2-coloring
• Phase transitions in the \(q\)-coloring of random hypergraphs
• Decoding from pooled data: sharp information-theoretic bounds
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Charting the replica symmetric phase
• Deterministic counting of graph colourings using sequences of subgraphs
• A positive temperature phase transition in random hypergraph 2-coloring
• The two-star model: exact solution in the sparse regime and condensation transition
• Local convergence of random graph colorings
• Charting the replica symmetric phase
• On the number of solutions in random graph \(k\)-colouring
• Phase transitions in discrete structures
• The number of solutions for random regular NAE-SAT
• Harnessing the Bethe free energy
• Counting colorings of triangle-free graphs
• Algorithmic obstructions in the random number partitioning problem
• Local convergence of random graph colorings
• Constraining the clustering transition for colorings of sparse random graphs
• One-step replica symmetry breaking of random regular NAE-SAT. II
• The condensation phase transition in random graph coloring
• Estimating the \(r\)-colorability threshold for a random hypergraph
• Phase transitions for the cavity approach to the clique problem 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)