The condensation phase transition in random graph coloring

DOI10.1007/S00220-015-2464-ZMaRDI QIDQ5963760zbMATH OpenOpenAlexFDO

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, https://drops.dagstuhl.de/opus/volltexte/2014/4716/

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

(41)

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

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)