Abstract | ||
---|---|---|
In 1998, Molloy and Reed showed that, under suitable conditions, if a sequence d n of degree sequences converges to a probability distribution D, then the proportion of vertices in the largest component of the random graph associated to d n is asymptotically ( D ) , where ( 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.jctb.2015.03.002 | Journal of Combinatorial Theory Series B |
Keywords | Field | DocType |
random graphs,giant component | Discrete mathematics,Combinatorics,Exponential function,Random graph,Vertex (geometry),Giant component,Probability distribution,Large deviations theory,Survival probability,Mathematics,Branching process | Journal |
Volume | Issue | ISSN |
113 | C | J. Combin. Theory Ser. B 113 (2015), 236--260 |
Citations | PageRank | References |
2 | 0.39 | 11 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Béla Bollobás | 1 | 2696 | 474.16 |
Oliver Riordan | 2 | 61 | 8.19 |