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.
Author: | 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 |
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 |
Page Number: | 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: | Informatik und Mathematik / Mathematik |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Sammlungen: | Universitätspublikationen |
Licence (German): | Creative Commons - Namensnennung 4.0 |