The asymptotic variance of the giant component of configuration model random graphs

Citation
Ball, Frank et Neal, Peter, The asymptotic variance of the giant component of configuration model random graphs, Annals of applied probability , 27(2), 2017, pp. 1057-1092
ISSN journal
10505164
Volume
27
Issue
2
Year of publication
2017
Pages
1057 - 1092
Database
ACNP
SICI code
Abstract
For a supercritical configuration model random graph, it is well known that, subject to mild conditions, there exists a unique giant component, whose size Rn is O(n), where n is the total number of vertices in the random graph. Moreover, there exists 0 < . . 1 such that ${R_n}/n\xrightarrow{p}\rho $ as n . .. We show that for a sequence of well behaved configuration model random graphs with a deterministic degree sequence satisfying 0 < . < 1; there exists .² > 0, such that $\left( {\sqrt n \left( {{R_n}/n - \rho } \right)} \right) \to {\sigma ^2}$ as n . .. Moreover, an explicit, easy to compute, formula is given for .². This provides a key stepping stone for computing the asymptotic variance of the size of the giant component for more general random graphs.