Asymptotic normality in random graphs with given vertex degrees
Author:
- 12 January 2020
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 56 (4) , 1070-1116
Abstract
We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph.Keywords
All Related Versions
Funding Information
- Knut and Alice Wallenberg Foundation
This publication has 28 references indexed in Scilit:
- Asymptotic normality of the size of the giant component via a random walkJournal of Combinatorial Theory, Series B, 2012
- A new approach to the giant component problemRandom Structures & Algorithms, 2008
- Asymptotic normality of the k-core in random graphsThe Annals of Applied Probability, 2008
- Monotonicity, asymptotic normality and vertex degrees in random graphsBernoulli, 2007
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- On tree census and the giant component in sparse random graphsRandom Structures & Algorithms, 1990
- Poisson convergence and random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1982
- The asymptotic distribution of short cycles in random regular graphsJournal of Combinatorial Theory, Series B, 1981
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978