The boundary of random planar maps via looptrees

Kortchemski, Igor; Richier, Loïc

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 29 (2020) no. 2, pp. 391-430.

Dans ce travail, nous étudions les limites d’échelle d’arbres à boucles associés à des arbres de Bienaymé–Galton–Watson (BGW). Dans un premier temps, nous considérons des arbres BGW dont la loi de reproduction est critique et dans le bassin d’attraction d’une loi gaussienne. Nous montrons que l’arbre continu brownien est la limite d’échelle des arbres à boucles associés, ce qui confirme une prédiction de [18]. Dans un second temps, nous considérons des arbres BGW dont la loi de reproduction est sous-critique et à queue lourde. Nous prouvons que la limite d’échelle des arbres à boucles associés est un multiple du cercle unité. Ceci correspond à un phénomène dit de condensation dans l’arbre sous-jacent, qui présente un sommet de degré macroscopique. Notre approche est fondée sur l’étude de marches aléatoires ayant une dérive négative. Enfin, nous appliquons ces résultats à l’étude de la géométrie de grandes faces de cartes de Boltzmann. Nous complétons les résultats de [50] en établissant l’existence d’une transition de phase pour la topologie de ces cartes dans le régime non générique critique.

We study the scaling limits of looptrees associated with Bienaymé–Galton–Watson (BGW) trees, that are obtained by replacing every vertex of the tree by a “cycle” whose size is its degree. First, we consider BGW trees whose offspring distribution is critical and in the domain of attraction of a Gaussian distribution. We prove that the Brownian CRT is the scaling limit of the associated looptrees, thereby confirming a prediction of [18]. Then, we deal with BGW trees whose offspring distribution is critical and heavy-tailed. We show that the scaling limit of the associated looptrees is a multiple of the unit circle. This corresponds to a so-called condensation phenomenon, meaning that the underlying tree exhibits a vertex with macroscopic degree. Here, we rely on an invariance principle for random walks with negative drift, which is of independent interest. Finally, we apply these results to the study of the scaling limits of large faces of Boltzmann planar maps. We complete the results of [50] and establish a phase transition for the topology of these maps in the non-generic critical regime.

Classification : 60F17, 60C05, 05C80, 60G50, 60J80
Mots clés : Planar maps, random trees, looptrees, random walks with negative drift, spinal decomposition, scaling limit, invariance principle

[1] Albenque, Marie; Marckert, Jean-François Some families of increasing planar maps, Electron. J. Probab., Volume 13 (2008) no. 56, pp. 1624-1671 | DOI | MR | Zbl

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

[3] Armendáriz, Inés; Loulakis, Michail Conditional distribution of heavy tailed random variables on large deviations of their sum, Stochastic Processes Appl., Volume 121 (2011) no. 5, pp. 1138-1147 | DOI | MR | Zbl

[4] 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

[5] 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

[6] 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

[7] Billingsley, Patrick Convergence of probability measures, Wiley Series in Probability and Statistics, John Wiley & Sons, 1999, x+277 pages | DOI | Zbl

[8] Bingham, Nicholas H.; Goldie, Charles M.; Teugels, Jozef L. Regular variation, Encyclopedia of Mathematics and Its Applications, 27, Cambridge University Press, 1989, xx+494 pages | MR

[9] Borot, Gaëtan; Bouttier, Jérémie; Guitter, Emmanuel A recursive approach to the $O\left(n\right)$ model on random maps via nested loops, J. Phys. A, Math. Gen., Volume 45 (2012) no. 4, 045002, 38 pages | MR | Zbl

[10] Borovkov, Aleksandr A.; Borovkov, Konstatin A. Asymptotic analysis of random walks. Heavy-tailed distributions, Encyclopedia of Mathematics and Its Applications, 118, Cambridge University Press, 2008, xxx+625 pages (translated from the Russian by O. B. Borovkova) | Zbl

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

[12] 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

[13] Budd, Timothy; Curien, Nicolas Geometry of infinite planar maps with high degrees, Electron. J. Probab., Volume 22 (2017), 35, 37 pages | MR | Zbl

[14] Burago, Dmitri; Burago, Yuri; Ivanov, Sergei A course in metric geometry, Graduate Studies in Mathematics, 33, American Mathematical Society, 2001, xiv+415 pages | MR

[15] Caraceni, Alessandra The scaling limit of random outerplanar maps, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 52 (2016) no. 4, pp. 1667-1686 | DOI | MR | Zbl

[16] Chen, Xinxin; Miermont, Grégory Long Brownian bridges in hyperbolic spaces converge to Brownian trees, Electron. J. Probab., Volume 22 (2017), 58, 15 pages | MR | Zbl

[17] Curien, Nicolas; Haas, Bénédicte; Kortchemski, Igor The CRT is the scaling limit of random dissections, Random Struct. Algorithms, Volume 47 (2015) no. 2, pp. 304-327 | DOI | MR | Zbl

[18] Curien, Nicolas; Kortchemski, Igor Random stable looptrees, Electron. J. Probab., Volume 19 (2014), 108, 35 pages | MR | Zbl

[19] Curien, Nicolas; Kortchemski, Igor Percolation on random triangulations and stable looptrees, Probab. Theory Relat. Fields, Volume 163 (2015) no. 1-2, pp. 303-337 | DOI | MR | Zbl

[20] Denisov, Denis; Shneer, Vsevolod Asymptotics for the first passage times of Lévy processes and random walks, J. Appl. Probab., Volume 50 (2013) no. 1, pp. 64-84 | DOI | Zbl

[21] Duquesne, Thomas A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab., Volume 31 (2003) no. 2, pp. 996-1027 | MR | Zbl

[22] Duquesne, Thomas An elementary proof of Hawkes’s conjecture on Galton-Watson trees, Electron. Commun. Probab., Volume 14 (2009), pp. 151-164 | DOI | MR | Zbl

[23] Durrett, Rick Conditioned limit theorems for random walks with negative drift, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 52 (1980) no. 3, pp. 277-287 | DOI | MR | Zbl

[24] Durrett, Rick Probability: theory and examples, Cambridge Series in Statistical and Probabilistic Mathematics, 31, Cambridge University Press, 2010 | MR | Zbl

[25] Feller, William An introduction to probability theory and its applications. Vol. II, John Wiley & Sons, 1971, xxiv+669 pages | Zbl

[26] den Hollander, Frank Probability Theory: The Coupling Method (lecture notes available online http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf)

[27] Ibragimov, Ilʼdar A.; Linnik, Yuriĭ V. Independent and stationary sequences of random variables, Wolters-Noordhoff Publishing, 1971, 443 pages (with a supplementary chapter by I. A. Ibragimov and V. V. Petrov, translation from the Russian edited by J. F. C. Kingman)

[28] Jacod, Jean; Shiryaev, Albert N. Limit theorems for stochastic processes, Grundlehren der Mathematischen Wissenschaften, 288, Springer, 2003, xx+661 pages | MR | Zbl

[29] Janson, Svante Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | DOI | MR

[30] Janson, Svante; Stefánsson, Sigurdur Ö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

[31] Jonsson, Thordur; Stefánsson, Sigurdur Örn Condensation in nongeneric trees, J. Stat. Phys., Volume 142 (2011) no. 2, pp. 277-313 | DOI | MR | Zbl

[32] Kallenberg, Olav Foundations of modern probability, Probability and Its Applications, Springer, 2002, xx+638 pages | DOI | Zbl

[33] Kesten, Harry Subdiffusive behavior of random walk on a random cluster, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 22 (1986) no. 4, pp. 425-487 | Numdam | MR | Zbl

[34] Kortchemski, Igor A simple proof of Duquesne’s theorem on contour processes of conditioned Galton-Watson trees, Séminaire de Probabilités XLV (Lecture Notes in Mathematics), Volume 2078, Springer, 2013, pp. 537-558 | DOI | MR | Zbl

[35] 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

[36] 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

[37] 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

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

[39] 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

[40] 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

[41] Lindvall, Torgny Lectures on the coupling method, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1992, xiv+257 pages | Zbl

[42] Lyons, Russell; Pemantle, Robin; Peres, Yuval Conceptual proofs of $LlogL$ criteria for mean behavior of branching processes, Ann. Probab., Volume 23 (1995) no. 3, pp. 1125-1138 | DOI | Zbl

[43] 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

[44] 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 | MR | Zbl

[45] 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

[46] 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

[47] Neveu, Jacques Arbres et processus de Galton–Watson, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 22 (1986) no. 2, pp. 199-207 | Numdam | MR | Zbl

[48] Panagiotou, Konstantinos; Stufler, Benedikt; Weller, Kerstin Scaling limits of random graphs from subcritical classes, Ann. Probab., Volume 44 (2016) no. 5, pp. 3291-3334 | DOI | MR | Zbl

[49] Pitman, Jim Combinatorial stochastic processes, Lecture Notes in Mathematics, 1875, Springer, 2006, x+256 pages (lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002, With a foreword by Jean Picard) | MR | Zbl

[50] Richier, Loïc Limits of the boundary of random planar maps, Probab. Theory Relat. Fields, Volume 172 (2018) no. 3-4, pp. 789-827 | DOI | MR | Zbl

[51] Stefánsson, Sigurdur Örn; Stufler, Benedikt Geometry of large boltzmann outerplanar maps, Random Struct. Algorithms, Volume 55 (2019) no. 3, pp. 742-771 | DOI | MR | Zbl

[52] Stufler, Benedikt Scaling limits of random outerplanar maps with independent link-weights, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 53 (2017) no. 2, pp. 900-915 | DOI | MR | Zbl

[53] Stufler, Benedikt Limits of random tree-like discrete structures, Probab. Surv., Volume 17 (2020), pp. 318-477 | DOI | MR | Zbl