Brownian excursions, critical random graphs and the multiplicative coalescent. (English) Zbl 0877.60010

Aldous, David

Ann. Probab. 25, No. 2, 812-854 (1997).

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\).

Reviewer: J.Franchi (Paris)

MSC:

60C05	Combinatorial probability
60J65	Brownian motion
60J50	Boundary theory for Markov processes

Keywords:

critical random graphs; largest components; Brownian excursions; breadth-first walk; multiplicative coalescent

References:

[1]	Aldous, D. J. (1991). The continuum random tree. II: an overview. In Stochastic Analysis (M. T. Barlow and N. H. Bingham, eds.) 23-70. Cambridge Univ. Press. · Zbl 0722.60013
[2]	Aldous, D. J. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009
[3]	Aldous, D. J. (1996). Deterministic and stochastic models for coalescence: a review of the mean-field theory for probabilists. Unpublished manuscript.
[4]	Aldous, D. J. and Limic, V. (1996). The entrance boundary of the multiplicative coalescent. Unpublished manuscript. · Zbl 0889.60080
[5]	Aldous, D. J. and Pitman, J. (1994). Brownian bridge asymptotics for random mappings. Random Structures and Algorithms 5 487-512. · Zbl 0811.60057
[6]	Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Univ. Press. · Zbl 0765.60015
[7]	Bollobás, B. (1985). Random Graphs. Academic Press, London. · Zbl 0567.05042
[8]	Borgs, C., Chayes, J., Kesten, H. and Spencer, J. (1996). The birth of the infinite cluster: finite-size scaling in percolation. Unpublished manuscript. · Zbl 1038.82035
[9]	Donnelly, P. and Joyce, P. (1992). Weak convergence of population genealogical processes to the coalescent with ages. Ann. Probab. 20 322-341. · Zbl 0747.60034
[10]	Drake, R. L. (1972). A general mathematical survey of the coagulation equation. International Reviews in Aerosol Physics and Chemistry 3 201-376. Pergamon, Elmsford, NY.
[11]	Erd os, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17-61. · Zbl 0103.16301
[12]	Erd os, P. and Rényi, A. (1961). On the evolution of random graphs. Bull. Inst. Internat. Statist. 38 343-347. · Zbl 0106.12006
[13]	Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. · Zbl 0592.60049
[14]	Evans, S. N. and Pitman, J. (1996). Construction of Markovian coalescents. Technical Report 465, Dept. Statistics, Univ. California, Berkeley. · Zbl 0906.60058
[15]	Janson, S. (1993). Multicyclic components in a random graph process. Random Structures and Algorithms 4 71-84. · Zbl 0766.60014
[16]	Janson, S., Knuth, D. E., Luczak, T. and Pittel, B. (1993). The birth of the giant component. Random Structures and Algorithms 4 233-358. · Zbl 0795.05127
[17]	Kallenberg, O. (1983). Random Measures. Akademie-Verlag, Berlin. · Zbl 0544.60053
[18]	Kingman, J. F. C. (1982). The coalescent. Stochastic Process. Appl. 13 235-248. · Zbl 0491.60076
[19]	Luczak, T., Pittel, B. and Wierman, J. C. (1994). The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 721-748. JSTOR: · Zbl 0807.05065
[20]	Lushnikov, A. A. (1978). Coagulation in finite systems. J. Colloid and Interface Science 65 276-285.
[21]	Marcus, A. H. (1968). Stochastic coalescence. Technometrics 10 133-143. JSTOR:
[22]	Martin-L öf, A. (1996). The final size of a nearly critical epidemic, and the first passage time of a Wiener process to a parabolic barrier. J. Appl. Probab.
[23]	Pitman, J. (1992). Partition structures derived from Brownian motion and stable subordinators. Technical Report 346, Dept. Statistics, Univ. California, Berkeley. · Zbl 0882.60081
[24]	Pitman, J. W. and Yor, M. (1997). The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator. Ann. Probab. 25 855-900. · Zbl 0880.60076
[25]	Revuz, D. and Yor, M. (1991). Continuous Martingales and Brownian Motion. Springer, Berlin. · Zbl 0731.60002
[26]	Rogers, L. C. G. and Williams, D. (1987). Diffusions, Markov Processes and Martingales: It o Calculus 2. Wiley, New York. · Zbl 0977.60005
[27]	Rogers, L. C. G. and Williams, D. (1994). Diffusions, Markov Processes and Martingales: Foundations 1, 2nd ed. Wiley, New York. · Zbl 0826.60002
[28]	Spencer, J. (1996). Enumerating graphs and Brownian motion. Technical report, Courant Institute, New York. · Zbl 0871.05032
[29]	Tak acs, L. (1991). A Bernouilli excursion and its various applications. Adv. in Appl. Probab. 23 557-585. JSTOR: · Zbl 0738.60069
[30]	van Dongen, P. G. J. (1987). Fluctuations in coagulating systems. II. J. Statist. Phys. 49 927-975.
[31]	van Dongen, P. G. J. and Ernst, M. H. (1987). Fluctuations in coagulating systems. J. Statist. Phys. 49 879-926.