Random trees constructed by aggregation
Annales de l'Institut Fourier, Volume 67 (2017) no. 5, p. 1963-2001

We study a general procedure that builds random -trees by gluing recursively a new branch on a uniform point of the pre-existing tree. The aim of this paper is to see how the asymptotic behavior of the sequence of lengths of branches influences some geometric properties of the limiting tree, such as compactness and Hausdorff dimension. In particular, when the sequence of lengths of branches behaves roughly like n -α for some α(0,1], we show that the limiting tree is a compact random tree of Hausdorff dimension α -1 . This encompasses the famous construction of the Brownian tree of Aldous. When α>1, the limiting tree is thinner and its Hausdorff dimension is always 1. In that case, we show that α -1 corresponds to the dimension of the set of leaves of the tree.

Nous nous intéressons à une procédure générale de construction d’arbres réels aléatoires par collages successifs de nouvelles branches. À chaque étape, la nouvelle branche est collée en un point uniformément sur l’arbre pré-existant. Notre objectif principal est de comprendre comment le comportement asymptotique de la suite des longueurs de branches influence certaines propriétés géométriques de l’arbre, telles que la compacité ou la dimension de Hausdorff. Nous montrons en particulier que lorsque la suite de longueurs de branches se comporte en n -α , avec α(0,1] fixé, l’arbre limite est compact, de dimension de Hausdorff α -1 . A titre d’exemple, ceci englobe une construction bien connue de l’arbre brownien d’Aldous. Lorsque α>1, l’arbre limite est plus fin et de dimension de Hausdorff 1. Dans ce cas, nous montrons que α -1 correspond à la dimension de l’ensemble des feuilles de l’arbre.

Received : 2015-12-08
Revised : 2016-06-29
Accepted : 2016-12-16
Published online : 2017-11-17
DOI : https://doi.org/10.5802/aif.3126
Classification:  60D05,  28A80
Keywords: random trees, stick-breaking, Gromov–Hausdorff convergence, fractal dimension
     author = {Curien, Nicolas and Haas, B\'en\'edicte},
     title = {Random trees constructed by aggregation},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {67},
     number = {5},
     year = {2017},
     pages = {1963-2001},
     doi = {10.5802/aif.3126},
     language = {en},
     url = {http://www.numdam.org/item/AIF_2017__67_5_1963_0}
Curien, Nicolas; Haas, Bénédicte. Random trees constructed by aggregation. Annales de l'Institut Fourier, Volume 67 (2017) no. 5, pp. 1963-2001. doi : 10.5802/aif.3126. http://www.numdam.org/item/AIF_2017__67_5_1963_0/

[1] Aldous, David The continuum random tree. I, Ann. Probab., Tome 19 (1991) no. 1, pp. 1-28 | Article | MR MR1085326 | Zbl 0722.60013

[2] Amini, Omid; Devroye, Luc; Griffiths, Simon; Olver, Neil Explosion and linear transit times in infinite trees, Probab. Theory Relat. Fields, Tome 167 (2017) no. 1-2, pp. 325-347 | Article | Zbl 06685604

[3] Barlow, Martin T.; Pemantle, Robin; Perkins, Edwin A. Diffusion-limited aggregation on a tree, Probab. Theory Relat. Fields, Tome 107 (1997) no. 1, pp. 1-60 | Article | MR 1427716 | Zbl 0866.60093

[4] Evans, Steven N. Probability and real trees, Springer, Lecture Notes in Mathematics, Tome 1920 (2008), xii+193 pages (Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23, 2005) | Article | MR 2351587 | Zbl 1139.60006

[5] Falconer, Kenneth Fractal geometry. Mathematical foundations and applications, John Wiley & Sons, Inc. (2003), xxviii+337 pages | Article | MR 2118797 | Zbl 1060.28006

[6] Goldschmidt, Christina; Haas, Bénédicte A line-breaking construction of the stable trees, Elect. J. Probab., Tome 20 (2015) no. 16, pp. 1-24 | Zbl 06471494

[7] Haas, Bénédicte Asymptotics of heights in random trees constructed by aggregation, Electron. J. Probab., Tome 22 (2017) (Paper No. 21, 25 p.) | Article | Zbl 1358.05054

[8] Imrich, Wilfried On metric properties of tree-like spaces, Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977) (German), Tech. Hochschule Ilmenau, Ilmenau (1977), pp. 129-156 | MR 599771 | Zbl 0417.05058

[9] Le Gall, Jean-François Random real trees, Ann. Fac. Sci. Toulouse, Tome 15 (2006) no. 1, pp. 35-62 | Article | MR MR2225746 | Zbl 1129.60047

[10] Pemantle, Robin A time-dependent version of Pólya’s urn, J. Theor. Probab., Tome 3 (1990) no. 4, pp. 627-637 | Article | MR 1067672 | Zbl 0708.60015

[11] Schramm, O. Conformally invariant scaling limits: an overview and a collection of problems, Proceedings of the international congress of mathematicians (ICM), Madrid (2006), European Mathematical Society (2007), pp. 513-543 | Zbl 1131.6008

[12] Sénizergues, Delphin Random gluing of d–dimensional metric spaces (2017) (https://arxiv.org/abs/1707.09833 )