TY  - CONF
A1  - Bapst, Victor
A1  - Coja-Oghlan, Amin
A1  - Hetterich, Samuel
A1  - Raßmann, Felicia
A1  - Vilenchik, Dan
T1  - The condensation phase transition in random graph coloring
T2  - Leibniz-Zentrum fuer Informatik ; 2014, Leibniz International Proceedings in Informatics (LIPIcs) ; 28
N2  - 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.
KW  - random graphs
KW  - graph coloring
KW  - phase transitions
KW  - message-passing algorithm
Y1  - 2017
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/42602
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-426026
SN  - 978-3-939897-74-3
SN  - 1868-8969
N1  - © Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik; licensed under Creative Commons License CC-BY
SP  - 449
EP  - 464
PB  - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
CY  - Dagstuhl
ER  -