Random trees constructed by aggregation
[Arbres aléatoires construits par agrégation]
Annales de l'Institut Fourier, Tome 67 (2017) no. 5, pp. 1963-2001.

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.

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/aif.3126
Classification : 60D05, 28A80
Keywords: random trees, stick-breaking, Gromov–Hausdorff convergence, fractal dimension
Mot clés : arbres aléatoires, convergence au sens Gromov–Hausdorff, dimension fractale
Curien, Nicolas 1 ; Haas, Bénédicte 2

1 Université Paris-Sud Bâtiment 425, 91400, Orsay (France)
2 Université Paris 13 LAGA - Institut Galilée 99 avenue Jean Baptiste Clément 93430 Villetaneuse (France)
@article{AIF_2017__67_5_1963_0,
     author = {Curien, Nicolas and Haas, B\'en\'edicte},
     title = {Random trees constructed by aggregation},
     journal = {Annales de l'Institut Fourier},
     pages = {1963--2001},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {67},
     number = {5},
     year = {2017},
     doi = {10.5802/aif.3126},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/aif.3126/}
}
TY  - JOUR
AU  - Curien, Nicolas
AU  - Haas, Bénédicte
TI  - Random trees constructed by aggregation
JO  - Annales de l'Institut Fourier
PY  - 2017
SP  - 1963
EP  - 2001
VL  - 67
IS  - 5
PB  - Association des Annales de l’institut Fourier
UR  - http://archive.numdam.org/articles/10.5802/aif.3126/
DO  - 10.5802/aif.3126
LA  - en
ID  - AIF_2017__67_5_1963_0
ER  - 
%0 Journal Article
%A Curien, Nicolas
%A Haas, Bénédicte
%T Random trees constructed by aggregation
%J Annales de l'Institut Fourier
%D 2017
%P 1963-2001
%V 67
%N 5
%I Association des Annales de l’institut Fourier
%U http://archive.numdam.org/articles/10.5802/aif.3126/
%R 10.5802/aif.3126
%G en
%F AIF_2017__67_5_1963_0
Curien, Nicolas; Haas, Bénédicte. Random trees constructed by aggregation. Annales de l'Institut Fourier, Tome 67 (2017) no. 5, pp. 1963-2001. doi : 10.5802/aif.3126. http://archive.numdam.org/articles/10.5802/aif.3126/

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

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

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

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

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

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

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

[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 | Zbl

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

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

[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

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

Cité par Sources :