The Phase Transition in Random Graphs: A Simple Proof

3,540 views · Published 28 July 2016 · 1:00:10 · Indexed 6 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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

More from this channel