The Evolution of Random Graphs

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 < \frac{1}{2}$ then a.e. random graph of order $n$ and since $M$ is such that its largest component has $O(\log n)$ vertices, but for $c > \frac{1}{2} 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 others 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$.