Brownian excursions, critical random graphs and the multiplicative coalescent
type: Item
instance of: scholarly article
title: Brownian excursions, critical random graphs and the multiplicative coalescent
zbMATH Open document ID: 0877.60010
published in: The Annals of Probability
publication date: 1997-12-07T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60J65
Mathematics Subject Classification ID: 60J50
zbMATH DE Number: 1018411
zbMATH Keywords: critical random graphs
zbMATH Keywords: largest components
zbMATH Keywords: Brownian excursions
zbMATH Keywords: breadth-first walk
zbMATH Keywords: multiplicative coalescent
author: David Aldous
reviewed by: Jacques Franchi
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1024404421
OpenAlex ID: W2056513564
cites work: The continuum random tree. I
cites work: The continuum random tree. III
cites work: The entrance boundary of the multiplicative coalescent
cites work: Brownian bridge asymptotics for random mappings
cites work: Compound Poisson approximation for nonnegative random variables via Stein's method
cites work: Q3682518
cites work: The birth of the infinite cluster: Finite-size scaling in percolation
cites work: Weak convergence of population genealogical processes to the coalescent with ages
cites work: Q3286850
cites work: Q3291948
cites work: Q3721531
cites work: Construction of Markovian coalescents
cites work: Multicyclic components in a random graph process
cites work: The birth of the giant component
cites work: Q3333815
cites work: The coalescent
cites work: The Structure of a Random Graph at the Point of the Phase Transition
cites work: Partition structures derived from Brownian motion and stable subordinators
cites work: The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
cites work: Q3997782
cites work: Q4508926
cites work: Q4328337
cites work: Enumerating graphs and Brownian motion
cites work: A bernoulli excursion and its various applications
DOI: 10.1214/AOP/1024404421
description: scientific article; zbMATH DE number 1018411