Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656786 | Journal of Combinatorial Theory, Series B | 2015 | 25 Pages |
Abstract
In 1998, Molloy and Reed showed that, under suitable conditions, if a sequence dndn of degree sequences converges to a probability distribution D , then the proportion of vertices in the largest component of the random graph associated to dndn is asymptotically ρ(D)ρ(D), where ρ(D)ρ(D) is a constant defined by the solution to certain equations that can be interpreted as the survival probability of a branching process associated to D. There have been a number of papers strengthening this result in various ways; here we prove a strong form of the result (with exponential bounds on the probability of large deviations) under minimal conditions.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Béla Bollobás, Oliver Riordan,