Name
Abstract | ||
|---|---|---|
In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erdos-Renyi random graph G(n,p) as it emerges from the critical window, i.e. for p=(1+@e)/n where @e^3n-~ and @e=o(1), in terms of a tractable contiguous model. Here we provide the analogous description for the supercritical giant component, i.e. the largest component of G(n,p) for p=@l/n where @l1 is fixed. The contiguous model is roughly as follows. Take a random degree sequence and sample a random multigraph with these degrees to arrive at the kernel; replace the edges by paths whose lengths are i.i.d. geometric variables to arrive at the 2-core; attach i.i.d. Poisson-Galton-Watson trees to the vertices for the final giant component. As in the case of the emerging giant, we obtain this result via a sequence of contiguity arguments at the heart of which are Kim's Poisson-cloning method and the Pittel-Wormald local limit theorems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ejc.2013.06.004 | Eur. J. Comb. |
Keywords | Field | DocType |
random multigraph,largest component,contiguous model,tractable contiguous model,analogous description,random degree sequence,supercritical regime,erdos-renyi random graph,final giant component,supercritical giant component,complete description | Kernel (linear algebra),Discrete mathematics,Combinatorics,Contiguity,Multigraph,Random graph,Vertex (geometry),Contiguity (probability theory),Giant component,Degree (graph theory),Mathematics | Journal |
Volume | ISSN | Citations |
35, | 0195-6698 | 5 |
PageRank | References | Authors |
0.54 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jian Ding | 1 | 103 | 9.96 |
| Eyal Lubetzky | 2 | 355 | 28.87 |
| Yuval Peres | 3 | 523 | 53.68 |