×

On the limit distribution of the number of cycles in a random graph. (English) Zbl 0662.60017

[For the entire collection see Zbl 0654.00009.]
The random graph models \(\Gamma_ n(p)\) and \(\Gamma\) (n,m) with common vertex-set \(\{\) 1,2,...,n\(\}\) are considered. The number of edges in \(\Gamma_ n(p)\) is a Bernoulli distributed random variable with expectation n(n-1)p/2, while \(\Gamma\) (n,m) has m edges chosen at random among the possible n(n-1)/2 edges.
The author proves that the limit distribution of the number of cycles in \(\Gamma_ n(p)\) and \(\Gamma\) (n,m) is Poisson with expectation \(- (1/2)\log (1-\lambda)-(\lambda /2)-(\lambda^ 2/4)\) as \(n\to \infty\) for both \(\Gamma_ n(p)\) and \(\Gamma\) (n,m) in the cases where p and m depend on n, namely, \(p=p_ n\sim \lambda /n\) and \(m=m(n)\sim \lambda n/2\), \(0<\lambda <1\). Moreover, entirely different stochastic behaviour of these models is shown if \(\lambda =1\).
Reviewer: L.Mutafchiev

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
60F05 Central limit and other weak theorems

Citations:

Zbl 0654.00009