The scaling window for a random graph with a given degree sequence |
| |
Authors: | Hamed Hatami Michael Molloy |
| |
Affiliation: | Department of Computer Science, University of Toronto, Toronto, Ontario, Canada |
| |
Abstract: | We consider a random graph on a given degree sequence D, satisfying certain conditions. Molloy and Reed defined a parameter Q = Q(D) and proved that Q = 0 is the threshold for the random graph to have a giant component. We introduce a new parameter R = R( begin{align*}mathcal {D}end{align*}) and prove that if |Q| = O(n‐1/3R2/3) then, with high probability, the size of the largest component of the random graph will be of order Θ(n2/3R‐1/3). If |Q| is asymptotically larger than n‐1/3R2/3 then the size of the largest component is asymptotically smaller or larger than n2/3R‐1/3. Thus, we establish that the scaling window is |Q| = O(n‐1/3R2/3). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 |
| |
Keywords: | |
|
|