Takács, Lajos On the limit distribution of the number of cycles in a random graph. (English) Zbl 0662.60017 A celebration of applied probability, J. Appl. Probab., Spec. Vol. 25A, 359-376 (1988). [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 Cited in 3 Documents MSC: 60C05 Combinatorial probability 05C80 Random graphs (graph-theoretic aspects) 60F05 Central limit and other weak theorems Keywords:random graph models; limit distribution Citations:Zbl 0654.00009 PDFBibTeX XML