|
Session 27. Probabilistic and Extremal Combinatorics
|
The condensation phase transition in random graph coloring |
Amin Coja-Oghlan, Goethe University Frankfurt, Germany
|
The talk is based on the joint work with Victor Bapst, Samuel Hetterich, Felicia Rassmann, Dan Vilenchik
|
|
|
Based on a non-rigorous formalism called the ``cavity method'', physicists have put forward 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 {\em condensation} [Krzakala et al., PNAS 2007].
The existence of this phase transition appears 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.
Here we prove this conjecture for \(k\) exceeding a certain constant \(k_0\).
|
|
| Print version |
|
