CDAM: Computational, Discrete and Applicable Mathematics@LSE

 CDAM Research Report, LSE-CDAM-2007-40

February 2008

Asymptotic Normality of the k-Core in Random Graphs

Svante Janson and Malwina J. Luczak

We study the k-core of a random (multi)graph on n vertices with a given degree sequence. In our previous paper [18] we used properties of empirical distributions of independent random variables to give a simple proof of the fact that the size of the giant k-core obeys a law of large numbers as n→∞. Here we develop the method further and show that the fluctuations around the deterministic limit converge to a Gaussian law above and near the threshold, and to a non-normal law at the threshold. Further, we determine precisely the location of the phase transition window for the emergence of a giant k-core. Hence we deduce corresponding results for the k-core in G(n,p) and G(n,m).

A PDF file (399 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-40, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2007