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

cavity methoddiluted mean-field modelgraph coloringphase transitionrandom graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) 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

• 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)