Brownian excursions, critical random graphs and the multiplicative coalescent
Consider the critical random graph on \(n\) vertices with probability \(n^{-1}+ tn^{-4/3}\) for each edge, and denote by \(C_n^t(j)\) the size of its \(j\)-th largest component. Consider also the ``surplus'' of this same \(j\)-th component: \(\sigma_n^t(j): =1+\) number of edges -- number of vertices. Consider on the other hand the reflecting inhomogeneous Brownian motion \(B^t(s)\) with drift \((t-s)\) at time \(s\), marked with a point process of intensity \(B^t(s)\) at time \(s\). Denote by \(|\gamma_j |\) the length of the \(j\)-th largest excursion of \(B^t(s)\) (away from 0), and by \(y(\gamma_j)\) the number of marks that \(\gamma_j\) contains. Then the sharp main result asserts that the vector \((n^{-2/3} C^t_n(j))\) converges in \(\ell^2\) to some limit which has the law of \((|\gamma_j |,y (\gamma_j))\). The link between random graphs and Brownian motion arises from some deterministic graph-exploration procedure, the so-called ``breadth-first walk''. The dynamics of merging of components as \(t\) increases are abstracted to define a fine Markov process on \(\ell^2\), shown to be Feller, the so called ``multiplicative coalescent'', for which clusters of sizes \(x_i\) and \(x_j\) merge at rate \(x_ix_j\).
scientific article; zbMATH DE number 1018411
scientific article