On scaling limits of random trees and maps with a prescribed degree sequence

Marzouk, Cyril

Annales Henri Lebesgue, Tome 5 (2022), pp. 317-386.

Nous étudions un modèle de configuration sur les cartes planaires biparties dans lequel on se donne $n$ entiers pairs et l’on tire une carte planaire avec $n$ faces uniformément au hasard parmi celles avec ces degrés. Nous démontrons que ces cartes, convenablement remises à l’échelle, admettent toujours des limites non triviales le long de sous-suites pour la topologie de Gromov–Hausdorff–Prokhorov. De plus nous montrons qu’elles convergent vers la célèbre sphère brownienne, et plus généralement un disque brownien pour des cartes à bord, si et seulement si elles ne contiennent pas de face de degré macroscopique, ou bien, si le périmètre est trop grand, les cartes dégénèrent et convergent vers l’arbre brownien. En choisissant les degrés eux-mêmes de façon aléatoire, ce modèle recouvre celui déjà étudié des cartes de Boltzmann conditionnées par la taille associées à une suite de poids critique et dans le bassin d’attraction d’une loi stable d’indice $\alpha \in [1,2]$. L’arbre et les disques browniens apparaissent alors respectivement dans les cas $\alpha =1$ et $\alpha =2$, tandis que dans le cas $\alpha \in ]1,2[$ nous retrouvons partiellement des résultats connus. Les preuves reposent sur des bijections connues avec des arbres plans étiquetés qui sont de la même manière tirés uniformément au hasard avec $n$ degrés donnés. Nous obtenons ainsi plusieurs résultats sur la géométrie de ces arbres intéressants par ailleurs, notamment leur convergence en loi vers l’arbre brownien, mais uniquement dans un sens faible de sous-arbres engendrés par un nombre fini de sommets.

We study a configuration model on bipartite planar maps in which, given $n$ even integers, one samples a planar map with $n$ faces uniformly at random with these face degrees. We prove that when suitably rescaled, such maps always admit nontrivial subsequential limits as $n\to \infty$ in the Gromov–Hausdorff–Prokhorov topology. Further, we show that they converge in distribution towards the celebrated Brownian sphere, and more generally a Brownian disk for maps with a boundary, if and only if there is no inner face with a macroscopic degree, or, if the perimeter is too big, the maps degenerate and converge to the Brownian tree. By first sampling the degrees at random with an appropriate distribution, this model recovers that of size-conditioned Boltzmann maps associated with critical weights in the domain of attraction of a stable law with index $\alpha \in [1,2]$. The Brownian tree and disks then appear respectively in the case $\alpha =1$ and $\alpha =2$, whereas in the case $\alpha \in (1,2)$ our results partially recover previous known ones. Our proofs rely on known bijections with labelled plane trees, which are similarly sampled uniformly at random given $n$ outdegrees. Along the way, we obtain some results on the geometry of such trees, such as a convergence to the Brownian tree but only in the weaker sense of subtrees spanned by random vertices, which are of independent interest.

Classification : 05C80, 60B05, 60D05, 60F17
Mots clés : Random maps, random trees, scaling limits

[AB12] Addario-Berry, Louigi Tail bounds for the height and width of a random tree with a given degree sequence, Random Struct. Algorithms, Volume 41 (2012) no. 2, pp. 253-261 | DOI | MR | Zbl

[ABA17] Addario-Berry, Louigi; Albenque, Marie The scaling limit of random simple triangulations and random simple quadrangulations, Ann. Probab., Volume 45 (2017) no. 5, pp. 2767-2825 | DOI | Zbl

[ABA21] Addario-Berry, Louigi; Albenque, Marie Convergence of non-bipartite maps via symmetrization of labeled trees, Ann. Henri Lebesgue, Volume 4 (2021), pp. 653-683 | DOI | MR | Zbl

[Abr16] Abraham, Céline Rescaled bipartite planar maps converge to the Brownian map, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 52 (2016) no. 2, pp. 575-595 | DOI | MR | Zbl

[Ald85] Aldous, David Exchangeability and related topics, École d’été de probabilités de Saint-Flour, XIII—1983 (Lecture Notes in Mathematics), Volume 1117, Springer, 1985, pp. 1-198 | DOI | MR | Zbl

[Ald93] Aldous, David The continuum random tree. III, Ann. Probab., Volume 21 (1993) no. 1, pp. 248-289 | DOI | MR | Zbl

[AMP04] Aldous, David; Miermont, Grégory; Pitman, Jim The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity, Probab. Theory Relat. Fields, Volume 129 (2004) no. 2, pp. 182-218 | DOI | MR | Zbl

[BCM19] Bernardi, Olivier; Curien, Nicolas; Miermont, Grégory A Boltzmann approach to percolation on random triangulations, Can. J. Math., Volume 71 (2019) no. 1, pp. 1-43 | DOI | MR | Zbl

[BCP03] Bertoin, Jean; Chaumont, Loïc; Pitman, Jim Path transformations of first passage bridges, Electron. Commun. Probab., Volume 8 (2003), pp. 155-166 | DOI | MR | Zbl

[BDFG04] Bouttier, Jérémie; Di Francesco, Philippe; Guitter, Emmanuel Planar maps as labeled mobiles, Electron. J. Comb., Volume 11 (2004) no. 1, 69 | MR | Zbl

[Ber19] Berger, Quentin Notes on random walks in the Cauchy domain of attraction, Probab. Theory Relat. Fields, Volume 175 (2019) no. 1-2, pp. 1-44 | DOI | MR | Zbl

[Bet10] Bettinelli, Jérémie Scaling limits for random quadrangulations of positive genus, Electron. J. Probab., Volume 15 (2010), 52, pp. 1594-1644 | DOI | MR | Zbl

[Bet15] Bettinelli, Jérémie Scaling limit of random planar quadrangulations with a boundary, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 51 (2015) no. 2, pp. 432-477 | DOI | Numdam | MR | Zbl

[BJM14] Bettinelli, Jérémie; Jacob, Emmanuel; Miermont, Grégory The scaling limit of uniform random plane maps, via the Ambjørn–Budd bijection, Electron. J. Probab., Volume 19 (2014), 74 | DOI | MR | Zbl

[BM14] Broutin, Nicolas; Marckert, Jean-François Asymptotics of trees with a prescribed degree sequence and applications, Random Struct. Algorithms, Volume 44 (2014) no. 3, pp. 290-316 | DOI | MR | Zbl

[BM17] Bettinelli, Jérémie; Miermont, Grégory Compact Brownian surfaces I: Brownian disks, Probab. Theory Relat. Fields, Volume 167 (2017) no. 3-4, pp. 555-614 | DOI | MR | Zbl

[CLGM13] Curien, Nicolas; Le Gall, Jean-François; Miermont, Grégory The Brownian cactus I. Scaling limits of discrete cactuses, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 49 (2013) no. 2, pp. 340-373 | DOI | Numdam | MR | Zbl

[Fel71] Feller, William An introduction to probability theory and its applications. Vol. II., Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1971 | MR | Zbl

[Hoe63] Hoeffding, Wassily Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., Volume 58 (1963), pp. 13-30 | DOI | MR | Zbl

[JS15] Janson, Svante; Stefánsson, Sigurður Örn Scaling limits of random planar maps with a unique large face, Ann. Probab., Volume 43 (2015) no. 3, pp. 1045-1081 | DOI | MR | Zbl

[Kor12] Kortchemski, Igor Invariance principles for Galton–Watson trees conditioned on the number of leaves, Stochastic Processes Appl., Volume 122 (2012) no. 9, pp. 3126-3172 | DOI | MR | Zbl

[Kor15] Kortchemski, Igor Limit theorems for conditioned non-generic Galton–Watson trees, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 51 (2015) no. 2, pp. 489-511 | DOI | Numdam | MR | Zbl

[Kor17] Kortchemski, Igor Sub-exponential tail bounds for conditioned stable Bienaymé–Galton–Watson trees, Probab. Theory Relat. Fields, Volume 168 (2017) no. 1-2, pp. 1-40 | DOI | MR | Zbl

[KR19] Kortchemski, Igor; Richier, Loïc Condensation in critical Cauchy Bienaymé–Galton–Watson trees, Ann. Appl. Probab., Volume 29 (2019) no. 3, pp. 1837-1877 | DOI | Zbl

[KR20] Kortchemski, Igor; Richier, Loïc The boundary of random planar maps via looptrees, Ann. Fac. Sci. Toulouse, Math., Volume 29 (2020) no. 2, pp. 391-430 | DOI | MR | Zbl

[Lei19] Lei, Tao Scaling limit of random forests with prescribed degree sequences, Bernoulli, Volume 25 (2019) no. 4A, pp. 2409-2438 | DOI | MR | Zbl

[LG05] Le Gall, Jean-François Random trees and applications, Probab. Surv., Volume 2 (2005), pp. 245-311 | DOI | MR | Zbl

[LG07] Le Gall, Jean-François The topological structure of scaling limits of large planar maps, Invent. Math., Volume 169 (2007) no. 3, pp. 621-670 | DOI | MR | Zbl

[LG13] Le Gall, Jean-François Uniqueness and universality of the Brownian map, Ann. Probab., Volume 41 (2013) no. 4, pp. 2880-2960 | DOI | MR | Zbl

[LGM11] Le Gall, Jean-François; Miermont, Grégory Scaling limits of random planar maps with large faces, Ann. Probab., Volume 39 (2011) no. 1, pp. 1-69 | DOI | MR | Zbl

[LGP08] Le Gall, Jean-François; Paulin, Frédéric Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere, Geom. Funct. Anal., Volume 18 (2008) no. 3, pp. 893-918 | DOI | MR | Zbl

[Mar18a] Marzouk, Cyril On scaling limits of planar maps with stable face-degrees, ALEA, Lat. Am. J. Probab. Math. Stat., Volume 15 (2018) no. 2, pp. 1089-1123 | DOI | MR | Zbl

[Mar18b] Marzouk, Cyril Scaling limits of random bipartite planar maps with a prescribed degree sequence, Random Struct. Algorithms, Volume 53 (2018) no. 3, pp. 448-503 | DOI | MR | Zbl

[McD98] McDiarmid, Colin Concentration, Probabilistic methods for algorithmic discrete mathematics (Algorithms and Combinatorics), Volume 16, Springer, 1998, pp. 195-248 | DOI | MR | Zbl

[Mie08] Miermont, Grégory On the sphericity of scaling limits of random planar quadrangulations, Electron. Commun. Probab., Volume 13 (2008), pp. 248-257 | DOI | MR | Zbl

[Mie09] Miermont, Grégory Tessellations of random maps of arbitrary genus, Ann. Sci. Éc. Norm. Supér., Volume 42 (2009) no. 5, pp. 725-781 | DOI | Numdam | MR | Zbl

[Mie13] Miermont, Grégory The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math., Volume 210 (2013) no. 2, pp. 319-401 | DOI | MR | Zbl

[MM03] Marckert, Jean-François; Mokkadem, Abdelkader The depth first processes of Galton–Watson trees converge to the same Brownian excursion, Ann. Probab., Volume 31 (2003) no. 3, pp. 1655-1678 | DOI | MR | Zbl

[MM07] Marckert, Jean-François; Miermont, Grégory Invariance principles for random bipartite planar maps, Ann. Probab., Volume 35 (2007) no. 5, pp. 1642-1705 | DOI | MR | Zbl

[Pit06] Pitman, Jim Combinatorial stochastic processes. École d’Été de Probabilités de Saint-Flour XXXII – 2002., Lecture Notes in Mathematics, 1875, Springer, 2006 | DOI | Zbl

[Thé20] Thévenin, Paul Vertices with fixed outdegrees in large Galton–Watson trees, Electron. J. Probab., Volume 25 (2020), 64 | DOI | MR | Zbl