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 |
