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 |
