Random Graph Coloring: The Replica Symmetric Phase

Monday, March 16, 2015 - 10:20am - 11:00am
Klaus 2443
Amin Coja-Oghlan (Johann Wolfgang Goethe-Universität Frankfurt)
In this talk I will give an overview of several recent results on the problem of coloring the sparse random graph G(n,d/n) with d>0 fixed as n grows. These results largely confirm and partially exceed the predictions on what physicists call the replica symmetric phase of the random graph coloring problem [Krzakala et al, PNAS 2007].