×

Critical random graphs: limiting constructions and distributional properties. (English) Zbl 1227.05224

Summary: We consider the Erdős-Rényi random graph \(G(n, p)\) inside the critical window, where \(p= 1/n+\lambda n^{-4/3}\) for some \(\lambda\in\mathbb{R}\). 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\to\infty\) yields a non-trivial sequence of limit metric spaces \({\mathcal C}=({\mathcal C}_1,{\mathcal C}_2,\dots)\). 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 \(\mathbb{R}_+\). 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, B. Pittel, and J.C. Wierman [“The structure of a random graph at the point of the phase transition,” Trans. Am. Math. Soc. 341, No.2, 721–748 (1994; Zbl 0807.05065)] 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.

MSC:

05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
60F99 Limit theorems in probability theory

Citations:

Zbl 0807.05065