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

Direct link
A new approach to the giant component problem
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2009 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 34, no 2, 197-216 p.Article in journal (Refereed) Published
Abstract [en]

We study the largest component 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 all the components are small, and other conditions that imply that with high probability there is a giant component 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 results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence.

We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np = 1 + ω(n)n−1/3, where ω(n) → arbitrarily slowly.

Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs

Place, publisher, year, edition, pages
2009. Vol. 34, no 2, 197-216 p.
Keyword [en]
random graph, giant component, death process, empirical distribution
National Category
URN: urn:nbn:se:uu:diva-106268DOI: 10.1002/rsa.20231ISI: 000263306800001OAI: oai:DiVA.org:uu-106268DiVA: diva2:224360
Available from: 2009-06-17 Created: 2009-06-17 Last updated: 2010-09-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
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: 170 hits
ReferencesLink to record
Permanent link

Direct link