The condensation phase transition in random graph coloring

Based on a non-rigorous formalism called the “cavity method”, physicists have made intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random k-
Based on a non-rigorous formalism called the “cavity method”, physicists have made 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 seems 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, provided that k exceeds a certain constant k0.
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, Dan Vilenchik
URN:urn:nbn:de:hebis:30:3-426026
DOI:http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.449
ISBN:978-3-939897-74-3
ISSN:1868-8969
Parent Title (English):Leibniz-Zentrum fuer Informatik ; 2014, Leibniz International Proceedings in Informatics (LIPIcs) ; 28
Publisher:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of publication:Dagstuhl
Document Type:Conference Proceeding
Language:English
Date of Publication (online):2017/01/14
Year of first Publication:2014
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2017/01/16
Tag:graph coloring; message-passing algorithm; phase transitions; random graphs
Pagenumber:16
First Page:449
Last Page:464
Note:
© Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik; licensed under Creative Commons License CC-BY
HeBIS PPN:399329366
Institutes:Mathematik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License LogoCreative Commons - Namensnennung 4.0

$Rev: 11761 $