The Erdős-Rényi theory of random graphs.

*(English)*Zbl 1027.05083
Halász, Gábor (ed.) et al., Paul Erdős and his mathematics II. Based on the conference, Budapest, Hungary, July 4-11, 1999. Berlin: Springer. Bolyai Soc. Math. Stud. 11, 79-134 (2002).

The paper under review is a broad-ranging survey of the Erdős-Rényi theory of random graphs. This is an area to which the author has made enormous contributions over the years, especially through his canonical text [B. Bollobás, Random graphs (Academic Press, London) (1985; Zbl 0567.05042)] (for second modified edition in 2001, see Zbl 0979.05003). The article under review is of survey type so does not include new results (though some remarks on the historical development of Erdős and Rényi’s work in this area are not well known, and the Postscript on recent developments may contain occasional surprises even for those experienced in the field).

The emphasis is on the pioneering work of Erdős and Rényi on the model of random graphs which is now often named after them. Roughly, one considers the set of all graphs on \(n\) labelled vertices with \(M(n)\) edges, with each such graph begin equally likely. (Sometimes it is desirable, or more technically convenient, to consider the evolution of such a graph as the edges are added one-by-one, or the very closely related model \(G(n,p(n))\) where each edge arises with probability \(p(n)\) independently of all other edges, with \(p(n)=2M(n)/n(n-1)\).) The key idea in the pioneering paper [P. Erdős and A. Rényi, Publ. Math., Debrecen 6, 290-297 (1959; Zbl 0092.15705)] is not to try to enumerate the number of these graphs which have some property of interest, but instead to treat graph invariants as random variables and use ideas of probability theory – especially asymptotic probability theory – to obtain results.

An archetypal example, dealt with (in more generality) in the 1959 Erdős-Rényi paper, is about the probability that \(G(n,M_{\omega})\), where \(M_{\omega}=n(\log(n)+\omega(n))/2\), is connected. It transpires that this depends critically on \(\omega(n)\). If \(\omega(n)\rightarrow -\infty\), then this probability tends to 0: if \(\omega(n)\rightarrow \infty\) it tends to 1 (and if \(\omega(n)\rightarrow c\) for constant \(c\), the probability is \(\exp(-\exp(-c))\)). The fact that the probability changes rather rapidly from being very close to 0 to being very close to 1 as \(M(n)\) increases is very typical of this subject: it leads, as in the second seminal paper of P. Erdős and A. Rényi [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5, 17-61 (1960; Zbl 0103.16301)] to the notion of thresholds, discussed in Section 2 of the paper under review.

A particularly important topic is the so-called phase transition: in \(G(n,cn/2)\) for \(c\) constant, if \(c<1\) most graphs have all components being ‘small’ trees or unicyclic. If \(c=1\) most graphs have a largest component with about \(n^{2/3}\) vertices and if \(c>1\) most graphs have a component of size \(\alpha(c)n\) for a suitable function \(\alpha(c)\) which is \(>0\) for \(c>0\). This is discussed in some detail in Section 3: for more of the (astonishingly precise) results proved on this seemingly inexhaustible topic, see the text of the author mentioned above, and the other standard text [S. Janson, T. Łuczak and A. Ruciński, Random graphs (Wiley, New York) (2000; Zbl 0968.05003)] which concentrates on topics where there has been progress since the 1985 edition of Bollobás.

Section 4 discusses cliques, colourings (including the author’s famous determination of the chromatic number of \(G(n,p)\) for fixed \(p\) using martingales) and Hamilton cycles. Section 5 deals with later papers of Erdős and Rényi on the topic, and Section 6 is a very wide-ranging overview of results in the last twenty or so years.

For the entire collection see [Zbl 0999.00016].

The emphasis is on the pioneering work of Erdős and Rényi on the model of random graphs which is now often named after them. Roughly, one considers the set of all graphs on \(n\) labelled vertices with \(M(n)\) edges, with each such graph begin equally likely. (Sometimes it is desirable, or more technically convenient, to consider the evolution of such a graph as the edges are added one-by-one, or the very closely related model \(G(n,p(n))\) where each edge arises with probability \(p(n)\) independently of all other edges, with \(p(n)=2M(n)/n(n-1)\).) The key idea in the pioneering paper [P. Erdős and A. Rényi, Publ. Math., Debrecen 6, 290-297 (1959; Zbl 0092.15705)] is not to try to enumerate the number of these graphs which have some property of interest, but instead to treat graph invariants as random variables and use ideas of probability theory – especially asymptotic probability theory – to obtain results.

An archetypal example, dealt with (in more generality) in the 1959 Erdős-Rényi paper, is about the probability that \(G(n,M_{\omega})\), where \(M_{\omega}=n(\log(n)+\omega(n))/2\), is connected. It transpires that this depends critically on \(\omega(n)\). If \(\omega(n)\rightarrow -\infty\), then this probability tends to 0: if \(\omega(n)\rightarrow \infty\) it tends to 1 (and if \(\omega(n)\rightarrow c\) for constant \(c\), the probability is \(\exp(-\exp(-c))\)). The fact that the probability changes rather rapidly from being very close to 0 to being very close to 1 as \(M(n)\) increases is very typical of this subject: it leads, as in the second seminal paper of P. Erdős and A. Rényi [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5, 17-61 (1960; Zbl 0103.16301)] to the notion of thresholds, discussed in Section 2 of the paper under review.

A particularly important topic is the so-called phase transition: in \(G(n,cn/2)\) for \(c\) constant, if \(c<1\) most graphs have all components being ‘small’ trees or unicyclic. If \(c=1\) most graphs have a largest component with about \(n^{2/3}\) vertices and if \(c>1\) most graphs have a component of size \(\alpha(c)n\) for a suitable function \(\alpha(c)\) which is \(>0\) for \(c>0\). This is discussed in some detail in Section 3: for more of the (astonishingly precise) results proved on this seemingly inexhaustible topic, see the text of the author mentioned above, and the other standard text [S. Janson, T. Łuczak and A. Ruciński, Random graphs (Wiley, New York) (2000; Zbl 0968.05003)] which concentrates on topics where there has been progress since the 1985 edition of Bollobás.

Section 4 discusses cliques, colourings (including the author’s famous determination of the chromatic number of \(G(n,p)\) for fixed \(p\) using martingales) and Hamilton cycles. Section 5 deals with later papers of Erdős and Rényi on the topic, and Section 6 is a very wide-ranging overview of results in the last twenty or so years.

For the entire collection see [Zbl 0999.00016].

Reviewer: David B.Penman (Colchester)