Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor


The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing and Louchard as the block sizes in a parking scheme. In the coalescent forest representation, edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by, instead, adding edges between roots. This construction induces exactly the same process in terms of cluster sizes, meanwhile, it allows us to make numerous new connections with other combinatorial and probabilistic models: size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees. The variety of the combinatorial objects involved justifies our interest in this construction. © 2018 Wiley Periodicals, Inc.


Documento: Artículo
Título:A new combinatorial representation of the additive coalescent
Autor:Marckert, J.-F.; Wang, M.
Filiación:CNRS, LaBRI Université de Bordeaux, Talence cedex, 33405, France
Conicet-UBA, Universidad de Buenos Aires, Ciudad Universitaria, C1428EGA, Capital Federal, Argentina
Palabras clave:additive coalescent; Cayley trees; increasing trees; parking; random walks on trees
Página de inicio:340
Página de fin:370
Título revista:Random Structures and Algorithms
Título revista abreviado:Random Struct. Algorithms


  • Addario-Berry, L., Broutin, N., Holmgren, C., Cutting down trees with a Markov chainsaw (2014) Ann. Appl. Probab., 24 (6), pp. 2297-2339
  • Aldous, D., The continuum random tree. I (1991) Ann. Probab., 19, pp. 1-28
  • Aldous, D., Brownian excursions, critical random graphs and the multiplicative coalescent (1997) Ann. Probab., 25 (2), pp. 812-854
  • Aldous, D., Pitman, J., The standard additive coalescent (1998) Ann. Probab., 26, pp. 1703-1726
  • Aldous, D.J., Deterministic and stochastic models for coalescence (aggregation, coagulation): A review of the mean-field theory for probabilists (1997) Bernoulli, 5, pp. 3-48
  • Bertoin, J., A fragmentation process connected to Brownian motion (2000) Probab. Theory Relat. Fields, 117 (2), pp. 289-301
  • Bertoin, J., (2006) Random Fragmentation and Coagulation Processes, , Cambridge, University Press, Cambridge
  • Bertoin, J., Fires on trees (2012) Ann. Inst. Henri Poincaré Probab. Stat., 48 (4), pp. 909-921
  • Bertoin, J., Miermont, G., The cut-tree of large Galton–Watson trees and the Brownian CRT (2013) Ann. Appl. Probab., 23 (4), pp. 1469-1493
  • Broutin, N., Marckert, J., A new encoding of combinatorial coalescent processes. Applications to the additive and multiplicative cases (2016) Probab. Theory Relat. Fields, 166 (1), pp. 515-552
  • Broutin, N., Wang, M., Cutting down p-trees and inhomogeneous continuum random trees (2017) Bernoulli, 23 (4A), pp. 2380-2433
  • Chassaing, P., Louchard, G., Phase transition for parking blocks, brownian excursion and coalescence (2002) Random Struct. Algorithms, 21 (1), pp. 76-119
  • Dieuleveut, D., The vertex-cut-tree of Galton–Watson trees converging to a stable tree (2015) Ann. Appl. Probab., 25 (4), pp. 2215-2262
  • Dvoretzky, A., Motzkin, T., A problem of arrangements (1947) Duke Math. J., 14, pp. 305-313
  • Evans, S., Pitman, J., Construction of Markovian coalescents (1998) Ann. Inst. H. Poincaré Probab. Stat., 34, pp. 339-383
  • Evans, S.N., (2008) Probability and Real Trees, volume 1920 of Lecture Notes in Mathematics, , Springer, Berlin, Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005
  • Fournier, N., Laurençot, P., Well-posedness of Smoluchowski's coagulation equation for a class of homogeneous kernels (2006) J. Funct. Anal., 233 (2), pp. 351-379
  • Janson, S., Random cutting and records in deterministic and random trees, Random (2006) Struct. Algorithms, 29 (2), pp. 139-179
  • Kaigh, W.D., An invariance principle for random walk conditioned by a late return to zero (1976) Ann. Probab., 4 (1), pp. 115-121
  • Kingman, J.F.C., The coalescent (1982) Stoch. Process Appl., 13 (3), pp. 235-248
  • Le Gall, J.-F., The uniform random tree in a Brownian excursion (1993) Probab. Theory Relat. Fields, 96 (3), pp. 369-383
  • Lushnikov, A., Some new aspects of coagulation theory Izv. Atmos. Ocean Phys., 14 (1978), pp. 738-743
  • Marcus, A., Stochastic coalescence (1968) Technometrics, 10 (1), pp. 133-143
  • Meir, A., Moon, J., Cutting down random trees (1970) J. Aust. Math. Soc., 11, pp. 313-324
  • Moon, J.W., On the maximum degree in a random tree (1968) Mich. Math. J., 15 (4), pp. 429-432
  • Panholzer, A., Cutting down very simple trees (2006) Quaest. Math., 29, pp. 211-228
  • Pitman, J., Coalescent random forests (1999) J. Combin. Theory Ser. A, 85 (2), pp. 165-193
  • Pitman, J., (2006) Combinatorial Stochastic Processes, volume 1875 of Lecture Notes in Mathematics, , Springer, Berlin
  • Riordan, J., Forests of cayley trees (1968) J. Comb. Theory, 5, pp. 90-103
  • Smoluchowski, M., Drei Vortrage uber Diffusion, Brownsche Bewegung und Koagulation von Kolloidteilchen Physik. Zeit., 17 (1916), pp. 557-585


---------- APA ----------
Marckert, J.-F. & Wang, M. (2019) . A new combinatorial representation of the additive coalescent. Random Structures and Algorithms, 54(2), 340-370.
---------- CHICAGO ----------
Marckert, J.-F., Wang, M. "A new combinatorial representation of the additive coalescent" . Random Structures and Algorithms 54, no. 2 (2019) : 340-370.
---------- MLA ----------
Marckert, J.-F., Wang, M. "A new combinatorial representation of the additive coalescent" . Random Structures and Algorithms, vol. 54, no. 2, 2019, pp. 340-370.
---------- VANCOUVER ----------
Marckert, J.-F., Wang, M. A new combinatorial representation of the additive coalescent. Random Struct. Algorithms. 2019;54(2):340-370.