uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Asymptotic normality of the k-core in random graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2008 (English)In: The Annals of Applied Probability, ISSN 1050-5164, Vol. 18, no 3, 1085-1137 p.Article in journal (Refereed) Published
Abstract [en]

We study the k-core of a random (multi)graph on n vertices with a given degree sequence. In our previous paper [Random Structures Algorithms 30 (2007) 50-62] 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 -> infinity. 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).

Place, publisher, year, edition, pages
2008. Vol. 18, no 3, 1085-1137 p.
Keyword [en]
cores, random graphs, balls and bins, central limit theorem
National Category
URN: urn:nbn:se:uu:diva-110169DOI: 10.1214/07-AAP478ISI: 000256459300010OAI: oai:DiVA.org:uu-110169DiVA: diva2:275483
Available from: 2009-11-05 Created: 2009-11-05 Last updated: 2009-12-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of Mathematics
In the same journal
The Annals of Applied Probability

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 195 hits
ReferencesLink to record
Permanent link

Direct link