A random graph with a subcritical number of edges

Abstract:

A random graph ${G_n}(\operatorname {prob} (\operatorname {edge} ) = p)\;(p = c/n, 0 < c < 1)$ on $n$ labelled vertices is studied. There are obtained limiting distributions of the following characteristics: the lengths of the longest cycle and the longest path, the total size of unicyclic components, the number of cyclic vertices, the number of distinct component sizes, and the middle terms of the component-size order sequence. For instance, it is proved that, with probability approaching ${(1 - c)^{1/2}}\exp (\sum \nolimits _{j = 1}^l {{c^j}/2j)}$ as $n \to \infty$, the random graph does not have a cycle of length $> l$. Another result is that, with probability approaching $1$, the size of the $\nu$th largest component either equals an integer closest to $a\;\log (bn/\nu {\log ^{5/2}}n)$, $a = a(c)$, $b = b(c)$, or is one less than this integer, provided that $\nu \to \infty$ and $\nu = o(n/{\log ^{5/2}}n)$.