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-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.
Verfasserangaben: | Victor Bapst, Amin Coja-OghlanORCiDGND, Samuel Hetterich, Felicia Raßmann, Dan Vilenchik |
---|---|
URN: | urn:nbn:de:hebis:30:3-426026 |
DOI: | https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.449 |
ISBN: | 978-3-939897-74-3 |
ISSN: | 1868-8969 |
Titel des übergeordneten Werkes (Englisch): | Leibniz-Zentrum fuer Informatik ; 2014, Leibniz International Proceedings in Informatics (LIPIcs) ; 28 |
Verlag: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik |
Verlagsort: | Dagstuhl |
Dokumentart: | Konferenzveröffentlichung |
Sprache: | Englisch |
Datum der Veröffentlichung (online): | 14.01.2017 |
Jahr der Erstveröffentlichung: | 2014 |
Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Datum der Freischaltung: | 16.01.2017 |
Freies Schlagwort / Tag: | graph coloring; message-passing algorithm; phase transitions; random graphs |
Seitenzahl: | 16 |
Erste Seite: | 449 |
Letzte Seite: | 464 |
Bemerkung: | © Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik; licensed under Creative Commons License CC-BY |
HeBIS-PPN: | 399329366 |
Institute: | Informatik und Mathematik / Mathematik |
DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Sammlungen: | Universitätspublikationen |
Lizenz (Deutsch): | Creative Commons - Namensnennung 4.0 |