The Scaling Window for a Random Graph with a Given Degree Sequence

Michael Molloy
University of Toronto
Computer Science

We consider random graphs with a given degree sequence $D=(d_1,...,d_n)$.
Molloy and Reed introduced a parameter Q and proved that
(1) for Q>0, the random graph almost surely (a.s.) has a giant component and
(2) for Q<0, a.s. the largest component has size o(n).
In this talk, we establish a scaling window around Q=0.

We consider a parameter R which is roughly equal to the sum of the cubes of the degrees.
We prove that if $|Q|=O(n^{-1/3} R^{2/3})$ then a.s. the size of the largest component will be of order $\Theta(n^{2/3} R^{-1/3})$.
If Q lies outside that range, then a.s. the size of the largest component is asymptotically smaller or larger.
(As usual, we require some reasonable conditions on the degree sequence.)
Joint work with Hamed Hatami.

Back to Workshop I: Probabilistic Techniques and Applications