On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase

Abstract

A uniformly random graph on $n$ vertices with a fixed degree sequence, obeying a $\gamma$ subpower law, is studied. It is shown that, for $\gamma >3$, in a subcritical phase with high probability the largest component size does not exceed $n^{1/\gamma +{\epsilon }_n}$, ${\epsilon }_n=O(\ln \ln n/\ln n)$, $1/\gamma$ being the best power for this random graph. This is similar to the best possible $n^{1/(\gamma -1)}$ bound for a different model of the random graph, one with independent vertex degrees, conjectured by Durrett, and proved recently by Janson.

Published in at http://dx.doi.org/10.1214/07-AAP493 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• The largest component in a subcritical random graph with a power law degree distribution
• Edge percolation on a random regular graph of low degree

Cited by in corpus (1)

• The largest component in a subcritical random graph with a power law degree distribution