The phase transition in random graphs: A simple proof

Source abstract

Abstract The classical result of Erdős and Rényi asserts that the random graph G ( n , p ) experiences sharp phase transition around \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$$\begin{align*}p=\frac{1}{n}\end{align*}$$ \end{document} – for any ε > 0 and \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$$\begin{align*}p=\frac{1-\epsilon}{n}\end{align*}$$ \end{document} , all connected components of G ( n , p ) are typically of size O ε (log n ), while for \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$$\begin{align*}p=\frac{1+\epsilon}{n}\end{align*}$$ \end{document} , 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 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$$\begin{align*}p=\frac{1+\epsilon}{n}\end{align*}$$ \end{document} , 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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013