The Phase Transition in Random Graphs: A Simple Proof

Опубликовано 28 июля 2016, 1:21

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 \epsilon0 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 M. Krivelelvich