Name
Abstract | ||
|---|---|---|
In this paper we study the diameter of the random graph G(n, p), i.e., the largest finite distance between two vertices, for a wide range of functions p = p(n). For p = λ/n with λ 1 constant we give a simple proof of an essentially best possible result, with an Op(1) additive correction term. Using similar techniques, we establish two-point concentration in the case that np → ∞. For p =(1 + ε)/n with ε → 0, we obtain a corresponding result that applies all the way down to the scaling window of the phase transition, with an Op(1/ε) additive correction term whose (appropriately scaled) limiting distribution we describe. Combined with earlier results, our new results complete the determination of the diameter of the random graph G(n, p) to an accuracy of the order of its standard deviation (or better), for all functions p = p(n). Throughout we use branching process methods, rather than the more common approach of separate analysis of the 2-core and the trees attached to it. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1017/S0963548310000325 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
corresponding result,random graph,best possible result,additive correction term,functions p,largest finite distance,new result,sparse random graph,phase transition,common approach,earlier result,branching process,scaling limit,standard deviation | Discrete mathematics,Random regular graph,Combinatorics,Random graph,Vertex (geometry),Phase transition,Scaling,Standard deviation,Mathematics,Branching process,Asymptotic distribution | Journal |
Volume | Issue | ISSN |
19 | 5-6 | Combinatorics, Probability and Computing 19 (2010), 835--926 |
Citations | PageRank | References |
9 | 1.02 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Riordan | 1 | 285 | 38.31 |
| Nicholas C. Wormald | 2 | 1506 | 230.43 |