The condensation phase transition in random graph coloring

DOI10.1007/S00220-015-2464-ZzbMATH Open1341.82027arXiv1404.5513OpenAlexW3106164415MaRDI QIDQ5963760FDOQ5963760

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

Publication date: 23 February 2016

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The two possible values of the chromatic number of a random graph
• The Parisi formula
• Polymers on disordered trees, spin glasses, and traveling waves.
• Are disordered spin glass models relevant for the structural glass problem?
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Information, Physics, and Computation
• Antiferromagnetic Potts model on the Erdős-Rényi random graph
• The freezing threshold for k-colourings of a random graph
• Gibbs measures and phase transitions on sparse random graphs
• Random-energy model: An exactly solvable model of disordered systems
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the Method of Typical Bounded Differences
• Large deviations of empirical neighborhood distribution in sparse random graphs
• The condensation transition in random hypergraph 2-coloring

Cited In (31)

• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• Spin systems on Bethe lattices
• Algorithmic obstructions in the random number partitioning problem
• Deterministic counting of graph colourings using sequences of subgraphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Information-theoretic thresholds from the cavity method
• Phase transitions in discrete structures
• On the Method of Typical Bounded Differences
• Estimating the \(r\)-colorability threshold for a random hypergraph
• Charting the replica symmetric phase
• Constraining the clustering transition for colorings of sparse random graphs
• Circular coloring of random graphs: statistical physics investigation
• Local convergence of random graph colorings
• The replica symmetric phase of random constraint satisfaction problems
• On the Number of Solutions in Random Graphk-Colouring
• 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
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Harnessing the Bethe free energy
• On the connectivity of proper colorings of random graphs and hypergraphs
• 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
• Rigid Colorings of Hypergraphs and Contiguity
• Phase transitions in theq-coloring of random hypergraphs
• On the Potts antiferromagnet on random graphs
• One-step replica symmetry breaking of random regular NAE-SAT. II
• Lower bounds on the chromatic number of random graphs
• Planting Colourings Silently

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)