Premium
The phase transition in random graphs: A simple proof
Author(s) -
Krivelevich Michael,
Sudakov Benny
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20470
Subject(s) - combinatorics , random graph , graph , simple (philosophy) , physics , phase transition , mathematics , path (computing) , condensed matter physics , computer science , philosophy , epistemology , programming language
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