On the probability of connectedness of a~graph~$\mathscr G_m(t)$

V. E. Stepanov

Teoriâ veroâtnostej i ee primeneniâ, Tome 15 (1970) no. 1, pp. 56-68

Résumé

In the previous paper of the author, it was shown that the probability of connectedness $P_m(t)$ of a random graph $\mathscr G_m(t)$ tends to exp $(-e^{-x})$ as $m\to\infty$ and $t=(\ln m+x+o(1))/m$. In the present paper, an asymptotic expression of probability $P_m(t)$ is found in a wider range. It is proved that $$ P_m(t)=\biggl(1-\frac{mt}{e^{mt}-1}\biggr)(1-e^{-mt})^m(1+o(1)) $$ uniformly in $t$ as $m\to\infty$ and $mt\ge y_0>0$. Based on this result, we prove that the distribution of the number of vertices in the greatest component of the graph $\mathscr G_m(t)$ is asymptotically normal as $m\to\infty$ and $mt>1$.