The ACO Seminar (2011-2012)
, 3:30pm, Wean 8220
, 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