The phase transition in random graphs: A simple proof. Issue 2 (24th September 2012) - Krivelevich, Michael; Sudakov, Benny
Abstract The classical result of Erdős and Rényi asserts that the random graph G(n, p) experiences sharp phase transition around <![CDATA[articlemathrsfsamsmathemptydocumentalign*p=1nalign* document]]> <inline-graphic xlink:href="ark:/27927/pgg277vcgqk" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> – for any ε > 0 and <![CDATA[articlemathrsfsamsmathemptydocumentalign*p=1-εnalign* document]]> <inline-graphic xlink:href="ark:/27927/pgg277vcgp1" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, all connected components of G(n, p) are typically of size Oε(log n), while for <![CDATA[articlemathrsfsamsmathemptydocumentalign*p=1+εnalign* document]]> <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 n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime <![CDATA[articlemathrsfsamsmathemptydocumentalign*p=1+εnalign* document]]> <inline-graphic xlink:href="ark:/27927/pgg277vch0h" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, 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