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

Direct link
A simple solution to the k-core problem
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2007 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 30, no 1-2, 50-62 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. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k-core is empty and other conditions that imply that with high probability the k-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer, and Wormald (J Combinator Theory 67 (1996), 111-151) on the existence and size of a k-core in G(n,p) and G(n,m), see also Molloy (Random Struct Algor 27 (2005), 124-135) and Cooper (Random Struct Algor 25 (2004), 353-375). Our method is based on the properties of empirical distributions of independent random variables and leads to simple proofs.

Place, publisher, year, edition, pages
2007. Vol. 30, no 1-2, 50-62 p.
Keyword [en]
cores, random graphs, balls and bins, death process, empirical distributions, law of large numbers
National Category
URN: urn:nbn:se:uu:diva-22671DOI: 10.1002/rsa.20147ISI: 000243477700004OAI: oai:DiVA.org:uu-22671DiVA: diva2:50444
Available from: 2007-01-19 Created: 2007-01-19 Last updated: 2011-04-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
Random structures & algorithms (Print)

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: 189 hits
ReferencesLink to record
Permanent link

Direct link