Refine
Year of publication
- 2014 (1) (remove)
Document Type
Language
- English (1)
Has Fulltext
- yes (1) (remove)
Is part of the Bibliography
- no (1) (remove)
Keywords
- graph coloring (1)
- message-passing algorithm (1)
- phase transitions (1)
- random graphs (1)
Institute
- Mathematik (1)
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.