"The phase transition in random graphs - a simple proof"
Benny Sudakov
UCLA
Wednesday, May 15, 2013, 11:00 am
EBU3B, Room 1202
Abstract:
In this talk we show how analyzing basic Depth First Search algorithm leads to a simple proof of the two most classical results about random graphs:
The result of Erdos-Renyi that the random graph G(n,p) experiences sharp phase transition around p=1/n. For 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.
The result of Ajtai-Komlos-Szemeredi that in the supercritical regime p=(1+\epsilon)/n, random graph typically contains a path of linear length.
Joint work with M. Krivelelvich