The condensation phase transition in random graph coloring
type: Item
instance of: scholarly article
title: The condensation phase transition in random graph coloring
zbMATH Open document ID: 1341.82027
author: Victor Bapst
author: Amin Coja-Oghlan
author: Samuel Hetterich
author: Felicia Rassmann
author: Dan Vilenchik
published in: Communications in Mathematical Physics
publication date: 2016-02-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1404.5513
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4716/
review text: The cavity method is a non-rigorous approach which has been proposed to study diluted mean-field models, in which the geometry of interactions is described by a sparse random graph or hypergraph. The specific model therein considered is the Potts antiferromagnet on the Erdős-Renyi random graph at zero temperature known as the random graph coloring problem. The contribution of the present paper is to prove that, in the random graph coloring problem, condensation occurs at the exact value predicted by the cavity method. The key of the proof is to establish an explicit link between the combinatorics of the graph coloring problem and the cavity formalism.
reviewed by: Guy Jumarie
Mathematics Subject Classification ID: 82B26
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6544482
zbMATH Keywords: phase transition
zbMATH Keywords: random graph
zbMATH Keywords: graph coloring
zbMATH Keywords: cavity method
zbMATH Keywords: diluted mean-field model
MaRDI profile type: Publication
OpenAlex ID: W3106164415
arXiv ID: 1404.5513
cites work: Q4705349
cites work: The two possible values of the chromatic number of a random graph
cites work: Large deviations of empirical neighborhood distribution in sparse random graphs
cites work: Upper-bounding the \(k\)-colorability threshold by counting covers
cites work: The condensation transition in random hypergraph 2-coloring
cites work: Antiferromagnetic Potts model on the Erdős-Rényi random graph
cites work: Gibbs measures and phase transitions on sparse random graphs
cites work: Random-energy model: An exactly solvable model of disordered systems
cites work: Polymers on disordered trees, spin glasses, and traveling waves.
cites work: Q3286850
cites work: Q3122905
cites work: Q4519896
cites work: Are disordered spin glass models relevant for the structural glass problem?
cites work: Gibbs states and the set of solutions of random constraint satisfaction problems
cites work: Q4226453
cites work: Information, Physics, and Computation
cites work: The freezing threshold for k-colourings of a random graph
cites work: The Parisi formula
cites work: Q4413910
cites work: On the Method of Typical Bounded Differences
DOI: 10.1007/S00220-015-2464-Z
description: scientific article; zbMATH DE number 6544482