Filtern
Erscheinungsjahr
- 2014 (1) (entfernen)
Dokumenttyp
Sprache
- Englisch (1) (entfernen)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1) (entfernen)
Schlagworte
- graph coloring (1)
- message-passing algorithm (1)
- phase transitions (1)
- random graphs (1)
Institut
- 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.