Critical random graphs: Limiting constructions and distributional properties

We consider the Erdős–Rényi random graph G(n, p) inside the critical window, where p = 1/n + λn-4/3 for some λ ∈ ℝ. We proved in [1] that considering the connected components of G(n, p) as a sequence of metric spaces with the graph distance rescaled by n-1/3 and letting n →∞ yields a non-trivial sequence of limit metric spaces C = (C1,C2, …). These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous’ Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on ℝ+. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Σuczak et al. [29] by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component. © 2010 Applied Probability Trust.