×

The evolution of random graphs. (English) Zbl 0579.05046

Author’s abstract: ”According to a fundamental result of Erdős and Rényi, the structure of a random graph \(G_ M\) changes suddenly when \(M\sim n/2:\) if \(M=\lfloor cn\rfloor\) and \(c<\) then a.e. random graph of order n is such that its largest component has O(log n) vertices, but for \(c>\) a.e. \(G_ M\) has a giant component: a component of order \((1- \alpha_ c+o(1))n\) where \(\alpha_ c<1\). The aim of this paper is to examine in detail the structure of a random graph \(G_ M\) when M is close to n/2. Among other things it is proved that if \(M=n/2+s\), \(s=o(n)\) and \(s\geq (\log n)^{1/2}n^{2/3}\) then the giant component has \((4+o(1))s\) vertices. Furthermore, rather precise estimates are given for the order of the r-th largest component for every fixed r.”
Reviewer: G.Grimmett

MSC:

05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI