The boundary of random planar maps via looptrees
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 29 (2020) no. 2, pp. 391-430.

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.

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.

Received:
Accepted:
Published online:
DOI: 10.5802/afst.1636
Classification: 60F17, 60C05, 05C80, 60G50, 60J80
Keywords: Planar maps, random trees, looptrees, random walks with negative drift, spinal decomposition, scaling limit, invariance principle

Igor Kortchemski 1; Loïc Richier 2

1 CNRS & CMAP, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex (France)
2 CMAP, École polytechnique, Route de Saclay, 91128 Palaiseau Cedex (France)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{AFST_2020_6_29_2_391_0,
     author = {Igor Kortchemski and Lo{\"\i}c Richier},
     title = {The boundary of random planar maps via looptrees},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {391--430},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 29},
     number = {2},
     year = {2020},
     doi = {10.5802/afst.1636},
     language = {en},
     url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1636/}
}
TY  - JOUR
AU  - Igor Kortchemski
AU  - Loïc Richier
TI  - The boundary of random planar maps via looptrees
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2020
SP  - 391
EP  - 430
VL  - 29
IS  - 2
PB  - Université Paul Sabatier, Toulouse
UR  - https://afst.centre-mersenne.org/articles/10.5802/afst.1636/
DO  - 10.5802/afst.1636
LA  - en
ID  - AFST_2020_6_29_2_391_0
ER  - 
%0 Journal Article
%A Igor Kortchemski
%A Loïc Richier
%T The boundary of random planar maps via looptrees
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2020
%P 391-430
%V 29
%N 2
%I Université Paul Sabatier, Toulouse
%U https://afst.centre-mersenne.org/articles/10.5802/afst.1636/
%R 10.5802/afst.1636
%G en
%F AFST_2020_6_29_2_391_0
Igor Kortchemski; Loïc Richier. The boundary of random planar maps via looptrees. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 29 (2020) no. 2, pp. 391-430. doi : 10.5802/afst.1636. https://afst.centre-mersenne.org/articles/10.5802/afst.1636/

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

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

[3] Inés Armendáriz; Michail Loulakis 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] Quentin Berger 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] Jérémie Bettinelli 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] Jérémie Bettinelli; Grégory Miermont Compact Brownian surfaces I: Brownian disks, Probab. Theory Relat. Fields, Volume 167 (2017) no. 3-4, pp. 555-614 | DOI | MR | Zbl

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

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

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

[10] Aleksandr A. Borovkov; Konstatin A. Borovkov 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] Jérémie Bouttier; Philippe Di Francesco; Emmanuel Guitter Planar maps as labeled mobiles, Electron. J. Comb., Volume 11 (2004) no. 1, 69, 27 pages | MR | Zbl

[12] Nicolas Broutin; Jean-François Marckert 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] Timothy Budd; Nicolas Curien Geometry of infinite planar maps with high degrees, Electron. J. Probab., Volume 22 (2017), 35, 37 pages | MR | Zbl

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

[15] Alessandra Caraceni 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] Xinxin Chen; Grégory Miermont Long Brownian bridges in hyperbolic spaces converge to Brownian trees, Electron. J. Probab., Volume 22 (2017), 58, 15 pages | MR | Zbl

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

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

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

[20] Denis Denisov; Vsevolod Shneer 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] Thomas Duquesne 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] Thomas Duquesne An elementary proof of Hawkes’s conjecture on Galton-Watson trees, Electron. Commun. Probab., Volume 14 (2009), pp. 151-164 | DOI | MR | Zbl

[23] Rick Durrett 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] Rick Durrett Probability: theory and examples, Cambridge Series in Statistical and Probabilistic Mathematics, 31, Cambridge University Press, 2010 | MR | Zbl

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

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

[27] Ilʼdar A. Ibragimov; Yuriĭ V. Linnik 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] Jean Jacod; Albert N. Shiryaev Limit theorems for stochastic processes, Grundlehren der Mathematischen Wissenschaften, 288, Springer, 2003, xx+661 pages | MR | Zbl

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

[30] Svante Janson; Sigurdur Örn Stefánsson 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] Thordur Jonsson; Sigurdur Örn Stefánsson Condensation in nongeneric trees, J. Stat. Phys., Volume 142 (2011) no. 2, pp. 277-313 | DOI | MR | Zbl

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

[33] Harry Kesten 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] Igor Kortchemski 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] Igor Kortchemski 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] Igor Kortchemski 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] Igor Kortchemski; Loïc Richier Condensation in critical Cauchy Bienaymé-Galton-Watson trees, Ann. Appl. Probab., Volume 29 (2019) no. 3, pp. 1837-1877 | DOI | Zbl

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

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

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

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

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

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

[44] Jean-François Marckert; Abdelkader Mokkadem 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] Cyril Marzouk 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] Grégory Miermont 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] Jacques Neveu Arbres et processus de Galton–Watson, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 22 (1986) no. 2, pp. 199-207 | Numdam | MR | Zbl

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

[49] Jim Pitman 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] Loïc Richier 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] Sigurdur Örn Stefánsson; Benedikt Stufler Geometry of large boltzmann outerplanar maps, Random Struct. Algorithms, Volume 55 (2019) no. 3, pp. 742-771 | DOI | MR | Zbl

[52] Benedikt Stufler 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] Benedikt Stufler Limits of random tree-like discrete structures, Probab. Surv., Volume 17 (2020), pp. 318-477 | DOI | MR | Zbl

Cited by Sources: