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

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)


60C05 Combinatorial probability
60J65 Brownian motion
60J50 Boundary theory for Markov processes
Full Text: DOI


[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 · doi:10.1214/aop/1176990534
[2] Aldous, D. J. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[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 · doi:10.1002/rsa.3240050402
[6] Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Univ. Press. · Zbl 0765.60015 · doi:10.1214/aop/1176989531
[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 · doi:10.1214/aop/1176989929
[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 · doi:10.1002/rsa.3240040105
[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 · doi:10.1002/rsa.3240040303
[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 · doi:10.1016/0304-4149(82)90011-4
[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 · doi:10.2307/2154580
[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: · doi:10.2307/1266230
[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 · doi:10.1214/aop/1024404422
[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 · doi:10.2307/1427622
[30] van Dongen, P. G. J. (1987). Fluctuations in coagulating systems. II. J. Statist. Phys. 49 927-975. · doi:10.1007/BF01017554
[31] van Dongen, P. G. J. and Ernst, M. H. (1987). Fluctuations in coagulating systems. J. Statist. Phys. 49 879-926. · doi:10.1007/BF01017554
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.