Premium
The scaling window for a random graph with a given degree sequence
Author(s) -
Hatami Hamed,
Molloy Michael
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20394
Subject(s) - random graph , combinatorics , giant component , scaling , mathematics , degree (music) , graph , sequence (biology) , random sequence , component (thermodynamics) , window (computing) , discrete mathematics , physics , geometry , computer science , mathematical analysis , quantum mechanics , biology , acoustics , genetics , operating system , distribution (mathematics)
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 ( \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal {D}\end{align*} \end{document} ) and prove that if | Q | = O ( n ‐1/3 R 2/3 ) then, with high probability, the size of the largest component of the random graph will be of order Θ( n 2/3 R ‐1/3 ). If | Q | is asymptotically larger than n ‐1/3 R 2/3 then the size of the largest component is asymptotically smaller or larger than n 2/3 R ‐1/3 . Thus, we establish that the scaling window is | Q | = O ( n ‐1/3 R 2/3 ). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012