The condensation phase transition in random graph coloring

DOI10.1007/s00220-015-2464-zzbMath1341.82027arXiv1404.5513OpenAlexW3106164415MaRDI QIDQ5963760

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)

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

zbMATH Keywords

phase transitiongraph coloringrandom graphcavity methoddiluted mean-field model

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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

This page was built for publication: The condensation phase transition in random graph coloring