The phase transition in random graphs: A simple proof. Issue 2 (24th September 2012)

• Record Type: Journal Article
• Authors: Krivelevich, Michael; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 43:Issue 2(2013)
• Page Start: 131
• Page End: 138
• Publication Date: 2012-09-24
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20470
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>The classical result of Erdős and Rényi asserts that the random graph <italic>G</italic>(<italic>n</italic>, <italic>p</italic>) experiences sharp phase transition around <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}p=\frac{1}{n}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg277vcgqk" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> – for any <italic>ε</italic> > 0 and <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}p=\frac{1-\epsilon}{n}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg277vcgp1" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, all connected components of <italic>G</italic>(<italic>n</italic>, <italic>p</italic>) are typically of size <italic>O</italic><sub><italic>ε</italic></sub>(log <italic>n</italic>), while for <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}p=\frac{1+\epsilon}{n}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg277vch35" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, with high probability there exists a connected component of size linear in <italic>n</italic>. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}p=\frac{1+\epsilon}{n}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg277vch0h" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, the random graph <italic>G</italic>(<italic>n</italic>, <italic>p</italic>) 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</p> </abstract>