ACO The ACO Seminar (2011-2012)

Feb 13, 3:30pm, Wean 8220
Michael Krivelevich, Tel Aviv University
The phase transition in random graphs - a simple proof


The classical result of Erdos and Renyi shows that the random graph G(n,p) experiences sharp phase transition around p=1/n - for any \epsilon>0 and p=(1-\epsilon)/n, all connected components of G(n,p) are typically of size O(log n), while for p=(1+\epsilon)/n, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime p=(1+\epsilon)/n, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games.

Joint work with Benny Sudakov (UCLA).

Back to the ACO home page