Feb 13, 3:30pm, Wean 8220

Michael Krivelevich, Tel Aviv University

The phase transition in random graphs - a simple proof

Michael Krivelevich, Tel Aviv University

The phase transition in random graphs - a simple proof

Abstract:

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).