×

Limits of random tree-like discrete structures. (English) Zbl 1454.60019

This paper presents a probabilistic study of tree-like structures via the weighted \(\mathcal{R}\)-enriched tree models. They are characterized by an isomorphism. Let \(\mathcal{R}\) be a combinatorial species. For each finite set \(U\), let \(\mathcal{A_R}[U]\) be the set of all pairs \((A,\alpha)\) with \(A\in\mathcal{A}[U]\) a rooted tree with labels inside \(U\), and \(\alpha\) a mapping that assigns to each vertex \(v\) of \(A\) with offspring set \(M_v\) an \(\mathcal{R}\)-structure \(\alpha(v)\in\mathcal{R}[M_v]\). A bijection from \(U\) to the vertex set \(V\) then rebels the vertices of the tree and the \(\mathcal{R}\)-structures on the offspring sets accordingly. For a weighting \(\kappa\) on the species \(\mathcal{R}\), a weighting \(\omega\) on the species \(\mathcal{A_R}\) is given by \(\omega(A,\alpha)=\prod_{v\in A}\kappa(\alpha(v))\). This model is closely related to some other tree-type discrete structures including random block-weighted graphs, random dissections of polygons, random planar maps with block-weights, and random \(k\)-dimensional trees. The convergence and local convergence of random enriched trees are studied. The giant components in Gibbs partitions for \(\mathcal{A_R}\) are investigated in both the convergent case and the super-exponential case. Schröder \(\mathcal{N}\)-enriched parenthesizations are discussed together with applications and Gromov-Hausdorff scaling limits of metric spaces building on the \(\mathcal{R}\)-enriched trees.

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Romain Abraham and Jean-François Delmas. Local limits of conditioned Galton-Watson trees: the condensation case. Electron. J. Probab., 19:no. 56, 29, 2014. · Zbl 1304.60091
[2] Romain Abraham and Jean-François Delmas. Local limits of conditioned Galton-Watson trees: the infinite spine case. Electron. J. Probab., 19:no. 2, 19, 2014. · Zbl 1285.60085
[3] L. Addario-Berry and Y. Wen. Joint convergence of random quadrangulations and their cores. ArXiv e-prints, March 2015. · Zbl 1382.60017 · doi:10.1214/16-AIHP775
[4] Louigi Addario-Berry. Growing random 3-connected maps. Electron. Commun. Probab., 19:no. 54, 12, 2014. · Zbl 1300.60021 · doi:10.1214/ECP.v19-3314
[5] Louigi Addario-Berry. A probabilistic approach to block sizes in random maps. ArXiv e-prints, March 2015. · Zbl 1405.60014
[6] Louigi Addario-Berry, Luc Devroye, and Svante Janson. Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees. Ann. Probab., 41(2):1072-1087, 2013. · Zbl 1278.60128 · doi:10.1214/12-AOP758
[7] David Aldous. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1(2):228-266, 1991. · Zbl 0733.60016 · doi:10.1214/aoap/1177005936
[8] David Aldous. The continuum random tree. I. Ann. Probab., 19(1):1-28, 1991. · Zbl 0722.60013 · doi:10.1214/aop/1176990534
[9] David Aldous. The continuum random tree. II. An overview. In Stochastic analysis (Durham, 1990), volume 167 of London Math. Soc. Lecture Note Ser., pages 23-70. Cambridge Univ. Press, Cambridge, 1991. · Zbl 0791.60008
[10] David Aldous. The continuum random tree. III. Ann. Probab., 21(1):248-289, 1993. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[11] David Aldous and Jim Pitman. Tree-valued Markov chains derived from Galton-Watson processes. Ann. Inst. H. Poincaré Probab. Statist., 34(5):637-686, 1998. · Zbl 0917.60082 · doi:10.1016/S0246-0203(98)80003-4
[12] J. Ambjørn and T. G. Budd. Trees and spatial topology change in causal dynamical triangulations. J. Phys. A, 46(31):315201, 33, 2013. · Zbl 1273.81224 · doi:10.1088/1751-8113/46/31/315201
[13] Omer Angel and Oded Schramm. Uniform infinite planar triangulations. Comm. Math. Phys., 241(2-3):191-213, 2003. · Zbl 1098.60010 · doi:10.1007/s00220-003-0932-3
[14] Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees. Discrete Appl. Math., 23(1):11-24, 1989. · Zbl 0666.68067 · doi:10.1016/0166-218X(89)90031-0
[15] Richard Arratia, A. D. Barbour, and Simon Tavaré. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003. · Zbl 1040.60001
[16] Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michèle Soria. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures Algorithms, 19(3-4):194-246, 2001. Analysis of algorithms (Krynica Morska, 2000). · Zbl 1016.68179 · doi:10.1002/rsa.10021
[17] A. D. Barbour and Boris L. Granovsky. Random combinatorial structures: the convergent case. J. Combin. Theory Ser. A, 109(2):203-220, 2005. · Zbl 1065.60143 · doi:10.1016/j.jcta.2004.09.001
[18] E. Baur, G. Miermont, and G. Ray. Classification of scaling limits of uniform quadrangulations with a boundary. ArXiv e-prints, August 2016. · Zbl 1448.60027 · doi:10.1214/18-AOP1316
[19] L. W. Beineke and R. E. Pippert. The number of labeled \(k\)-dimensional trees. J. Combinatorial Theory, 6:200-205, 1969. · Zbl 0175.20904 · doi:10.1016/S0021-9800(69)80120-1
[20] Jason P. Bell. When structures are almost surely connected. Electron. J. Combin., 7:Research Paper 36, 7 pp. (electronic), 2000. · Zbl 0972.05001
[21] Itai Benjamini, Harry Kesten, Yuval Peres, and Oded Schramm. Geometry of the uniform spanning forest: transitions in dimensions \(4,8,12,\dots \). Ann. of Math. (2), 160(2):465-491, 2004. · Zbl 1071.60006
[22] Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm. Uniform spanning forests. Ann. Probab., 29(1):1-65, 2001. · Zbl 1016.60009
[23] Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13 pp. (electronic), 2001. · Zbl 1010.82021
[24] François Bergeron, Gilbert Labelle, and Pierre Leroux. Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.
[25] Olivier Bernardi, Marc Noy, and Dominic Welsh. Growth constants of minor-closed classes of graphs. J. Combin. Theory Ser. B, 100(5):468-484, 2010. · Zbl 1203.05145 · doi:10.1016/j.jctb.2010.03.001
[26] Nicla Bernasconi, Konstantinos Panagiotou, and Angelika Steger. On the degree sequences of random outerplanar and series-parallel graphs. In Approximation, randomization and combinatorial optimization, volume 5171 of Lecture Notes in Comput. Sci., pages 303-316. Springer, Berlin, 2008. · Zbl 1159.68635
[27] Nicla Bernasconi, Konstantinos Panagiotou, and Angelika Steger. The degree sequence of random graphs from subcritical classes. Combin. Probab. Comput., 18(5):647-681, 2009. · Zbl 1215.05156 · doi:10.1017/S0963548309990368
[28] Nicla Bernasconi, Konstantinos Panagiotou, and Angelika Steger. On properties of random dissections and triangulations. Combinatorica, 30(6):627-654, 2010. · Zbl 1231.05235 · doi:10.1007/s00493-010-2464-8
[29] Patrick Billingsley. Weak convergence of measures: Applications in probability. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1971. Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 5. · Zbl 0271.60009
[30] Jakob E. Björnberg and Sigurdur Ö. Stefánsson. Recurrence of bipartite planar maps. Electron. J. Probab., 19:no. 31, 40, 2014. · Zbl 1286.05153
[31] Jakob E. Björnberg and Sigurdur Örn Stefánsson. Random walk on random infinite looptrees. J. Stat. Phys., 158(6):1234-1261, 2015. · Zbl 1317.82018
[32] Manuel Bodirsky, Éric Fusy, Mihyun Kang, and Stefan Vigerske. Enumeration and asymptotic properties of unlabeled outerplanar graphs. Electron. J. Combin., 14(1):Research Paper 66, 24, 2007. · Zbl 1158.05320
[33] Manuel Bodirsky, Éric Fusy, Mihyun Kang, and Stefan Vigerske. Boltzmann samplers, Pólya theory, and cycle pointing. SIAM J. Comput., 40(3):721-769, 2011. · Zbl 1232.05008 · doi:10.1137/100790082
[34] Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. J. Graph Algorithms Appl., 9(2):185-204 (electronic), 2005. · Zbl 1084.05019 · doi:10.7155/jgaa.00105
[35] N. Bourbaki. Éléments de mathématique. Fasc. XXXV. Livre VI: Intégration. Chapitre IX: Intégration sur les espaces topologiques séparés. Actualités Scientifiques et Industrielles, No. 1343. Hermann, Paris, 1969. · Zbl 0189.14201
[36] J. Bouttier, P. Di Francesco, and E. Guitter. Planar maps as labeled mobiles. Electron. J. Combin., 11(1):Research Paper 69, 27, 2004. · Zbl 1060.05045
[37] Dmitri Burago, Yuri Burago, and Sergei Ivanov. A course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001. · Zbl 1232.53037 · doi:10.2140/gt.2011.15.2275
[38] Alessandra Caraceni. The scaling limit of random outerplanar maps. Ann. Inst. H. Poincaré Probab. Statist., 52(4):1667-1686, 11 2016. · Zbl 1384.60032 · doi:10.1214/15-AIHP694
[39] Philippe Chassaing and Bergfinnur Durhuus. Local limit of labeled trees and expected volume growth in a random quadrangulation. Ann. Probab., 34(3):879-917, 2006. · Zbl 1102.60007 · doi:10.1214/009117905000000774
[40] J. Chover, P. Ney, and S. Wainger. Functions of probability measures. J. Analyse Math., 26:255-302, 1973. · Zbl 0276.60018 · doi:10.1007/BF02790433
[41] Robert Cori and Bernard Vauquelin. Planar maps are well labeled trees. Canad. J. Math., 33(5):1023-1042, 1981. · Zbl 0415.05020 · doi:10.4153/CJM-1981-078-2
[42] N. Curien, L. Ménard, and G. Miermont. A view from infinity of the uniform infinite planar quadrangulation. ALEA Lat. Am. J. Probab. Math. Stat., 10(1):45-88, 2013. · Zbl 1277.05151
[43] Nicolas Curien. Notes provisoires du cours de m2 graphes aléatoires. 2016.
[44] Nicolas Curien, Bénédicte Haas, and Igor Kortchemski. The CRT is the scaling limit of random dissections. Random Structures Algorithms, 47(2):304-327, 2015. · Zbl 1322.05123 · doi:10.1002/rsa.20554
[45] Nicolas Curien and Igor Kortchemski. Random non-crossing plane configurations: a conditioned Galton-Watson tree approach. Random Structures Algorithms, 45(2):236-260, 2014. · Zbl 1301.05310 · doi:10.1002/rsa.20481
[46] Nicolas Curien and Igor Kortchemski. Random non-crossing plane configurations: a conditioned Galton-Watson tree approach. Random Struct. Algorithms, 45(2):236-260, 2014. · Zbl 1301.05310 · doi:10.1002/rsa.20481
[47] Alexis Darrasse and Michèle Soria. Limiting distribution for distances in \(k\)-trees. In Combinatorial algorithms, volume 5874 of Lecture Notes in Comput. Sci., pages 170-182. Springer, Berlin, 2009. · Zbl 1267.05106
[48] D. Denisov, A. B. Dieker, and V. Shneer. Large deviations for random walks under subexponentiality: the big-jump domain. Ann. Probab., 36(5):1946-1991, 2008. · Zbl 1155.60019 · doi:10.1214/07-AOP382
[49] Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition, 2010. · Zbl 1204.05001
[50] M. Drmota, E. Y. Jin, and B. Stufler. Graph limits of random graphs from a subset of connected \(k\)-trees. ArXiv e-prints, May 2016. · Zbl 1423.05152 · doi:10.1002/rsa.20802
[51] Michael Drmota, Éric Fusy, Mihyun Kang, Veronika Kraus, and Juanjo Rué. Asymptotic study of subcritical graph classes. SIAM J. Discrete Math., 25(4):1615-1651, 2011. · Zbl 1237.05103 · doi:10.1137/100790161
[52] Michael Drmota, Omer Giménez, and Marc Noy. Degree distribution in random planar graphs. J. Combin. Theory Ser. A, 118(7):2102-2130, 2011. · Zbl 1230.05103 · doi:10.1016/j.jcta.2011.04.010
[53] Michael Drmota, Emma Yu Jin, and Benedikt Stufler. Graph limits of random graphs from a subset of connected k-trees. Random Structures & Algorithms, 55(1):125-152. · Zbl 1423.05152 · doi:10.1002/rsa.20802
[54] Michael Drmota and Marc Noy. Extremal parameters in sub-critical graph classes. In ANALCO13—Meeting on Analytic Algorithmics and Combinatorics, pages 1-7. SIAM, Philadelphia, PA, 2013. · Zbl 1430.05059
[55] Michael Drmota, Lander Ramos, and Juanjo Rué. Subgraph statistics in subcritical graph classes. Random Structures & Algorithms, 51(4):631-673, 2017. · Zbl 1379.05100 · doi:10.1002/rsa.20721
[56] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput., 13(4-5):577-625, 2004. · Zbl 1081.65007 · doi:10.1017/S0963548304006315
[57] Thomas Duquesne. A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab., 31(2):996-1027, 2003. · Zbl 1025.60017 · doi:10.1214/aop/1048516543
[58] Thomas Duquesne and Jean-François Le Gall. Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields, 131(4):553-603, 2005. · Zbl 1070.60076 · doi:10.1007/s00440-004-0385-4
[59] Rick Durrett. Probability: theory and examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, fourth edition, 2010. · Zbl 1202.60001
[60] Richard Ehrenborg and Miguel Méndez. Schröder parenthesizations and chordates. J. Combin. Theory Ser. A, 67(2):127-139, 1994. · Zbl 0804.05021
[61] Julia Ehrenm. Spanning trees in random series-parallel graphs. Advances in Applied Mathematics, 75:18-55, 2016. · Zbl 1331.05061 · doi:10.1016/j.aam.2015.12.001
[62] P. Embrechts and E. Omey. Functions of power series. Yokohama Math. J., 32(1-2):77-88, 1984. · Zbl 0561.60093
[63] Michael M. Erlihson and Boris L. Granovsky. Limit shapes of Gibbs distributions on the set of integer partitions: the expansive case. Ann. Inst. Henri Poincaré Probab. Stat., 44(5):915-945, 2008. · Zbl 1181.60146 · doi:10.1214/07-AIHP129
[64] William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons, Inc., New York-London-Sydney, 1971. · Zbl 0077.12201
[65] Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009. · Zbl 1165.05001
[66] Dominique Foata. Enumerating \(k\)-trees. Discrete Math., 1(2):181-186, 1971/72. · Zbl 0219.05066
[67] Tom Fowler, Ira Gessel, Gilbert Labelle, and Pierre Leroux. The specification of 2-trees. Adv. in Appl. Math., 28(2):145-168, 2002. · Zbl 1003.05054 · doi:10.1006/aama.2001.0771
[68] Andrew Gainer-Dewar. \( \Gamma \)-species and the enumeration of \(k\)-trees. Electron. J. Combin., 19(4):Paper 45, 33, 2012. · Zbl 1266.05065
[69] A. Georgakopoulos and S. Wagner. Limits of subcritical random graphs and random graphs with excluded minors. ArXiv e-prints, December 2015.
[70] Omer Giménez and Marc Noy. Asymptotic enumeration and limit laws of planar graphs. J. Amer. Math. Soc., 22(2):309-329, 2009. · Zbl 1206.05019 · doi:10.1090/S0894-0347-08-00624-3
[71] Omer Giménez, Marc Noy, and Juanjo Rué. Graph classes with given 3-connected components: asymptotic enumeration and random graphs. Random Structures Algorithms, 42(4):438-479, 2013. · Zbl 1269.05060 · doi:10.1002/rsa.20421
[72] Martin Grötschel and Gyula Katona. Preface. In Building bridges, volume 19 of Bolyai Soc. Math. Stud., pages 7-8. Springer, Berlin, 2008.
[73] Ori Gurel-Gurevich and Asaf Nachmias. Recurrence of planar graph limits. Ann. of Math. (2), 177(2):761-781, 2013. · Zbl 1262.05031 · doi:10.4007/annals.2013.177.2.10
[74] Bénédicte Haas and Grégory Miermont. Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. Ann. Probab., 40(6):2589-2666, 2012. · Zbl 1259.60033
[75] Bénédicte Haas and Robin Stephenson. Scaling limits of \(k\)-ary growing trees. Ann. Inst. Henri Poincaré Probab. Stat., 51(4):1314-1341, 2015. · Zbl 1329.60076
[76] Frank Harary and Edgar M. Palmer. Graphical enumeration. Academic Press, New York-London, 1973. · Zbl 0266.05108
[77] Tom Hutchcroft and Asaf Nachmias. Uniform spanning forests of planar graphs. Forum Math. Sigma, 7:e29, 55, 2019. · Zbl 1422.60022 · doi:10.1017/fms.2019.14
[78] Svante Janson. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv., 9:103-252, 2012. · Zbl 1244.60013 · doi:10.1214/11-PS188
[79] Svante Janson. Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees. Random Structures Algorithms, 48(1):57-101, 2016. · Zbl 1330.05039 · doi:10.1002/rsa.20568
[80] Svante Janson, Thordur Jonsson, and Sigurdur Örn Stefánsson. Random trees with superexponential branching weights. J. Phys. A, 44(48):485002, 16, 2011. · Zbl 1236.05180 · doi:10.1088/1751-8113/44/48/485002
[81] Svante Janson and Sigurdur Örn Stefánsson. Scaling limits of random planar maps with a unique large face. Ann. Probab., 43(3):1045-1081, 2015. · Zbl 1320.05112
[82] Thordur Jonsson and Sigurdur Örn Stefánsson. Condensation in nongeneric trees. J. Stat. Phys., 142(2):277-313, 2011. · Zbl 1225.60140
[83] André Joyal. Une théorie combinatoire des séries formelles. Adv. in Math., 42(1):1-82, 1981. · Zbl 0491.05007
[84] Olav Kallenberg. Foundations of modern probability. Probability and its Applications (New York). Springer-Verlag, New York, second edition, 2002. · Zbl 0996.60001
[85] Douglas P. Kennedy. The Galton-Watson process conditioned on the total progeny. J. Appl. Probability, 12(4):800-806, 1975. · Zbl 0322.60072 · doi:10.2307/3212730
[86] Götz Kersting. On the height profile of a conditioned galton-watson tree, 2011.
[87] Igor Kortchemski. Invariance principles for Galton-Watson trees conditioned on the number of leaves. Stochastic Process. Appl., 122(9):3126-3172, 2012. · Zbl 1259.60103 · doi:10.1016/j.spa.2012.05.013
[88] Igor Kortchemski. A simple proof of Duquesne’s theorem on contour processes of conditioned Galton-Watson trees. In Séminaire de Probabilités XLV, volume 2078 of Lecture Notes in Math., pages 537-558. Springer, Cham, 2013. · Zbl 1286.60087
[89] Igor Kortchemski. Random stable laminations of the disk. Ann. Probab., 42(2):725-759, 2014. · Zbl 1304.60094 · doi:10.1214/12-AOP799
[90] Igor Kortchemski. Limit theorems for conditioned ot non-generic Galton-Watson trees. Ann. Inst. Henri Poincaré Probab. Stat., 51(2):489-511, 2015. · Zbl 1315.60091 · doi:10.1214/13-AIHP580
[91] Igor Kortchemski. Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees. Probab. Theory Related Fields, 168(1-2):1-40, 2017. · Zbl 1374.60167 · doi:10.1007/s00440-016-0704-6
[92] V. Kurauskas. On local weak limit and subgraph counts for sparse random graphs. ArXiv e-prints, April 2015.
[93] Gilbert Labelle. Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange. Adv. in Math., 42(3):217-247, 1981. · Zbl 0477.05007 · doi:10.1016/0001-8708(81)90041-4
[94] Jacques Labelle. Applications diverses de la théorie combinatoire des espèces de structures. Ann. Sci. Math. Québec, 7(1):59-94, 1983. · Zbl 0524.18003
[95] Jean-François Le Gall. The topological structure of scaling limits of large planar maps. Invent. Math., 169(3):621-670, 2007. · Zbl 1132.60013 · doi:10.1007/s00222-007-0059-9
[96] Jean-François Le Gall. Uniqueness and universality of the Brownian map. Ann. Probab., 41(4):2880-2960, 2013. · Zbl 1282.60014 · doi:10.1214/12-AOP792
[97] Jean-François Le Gall and Grégory Miermont. Scaling limits of random planar maps with large faces. Ann. Probab., 39(1):1-69, 2011. · Zbl 1204.05088
[98] Jean-François Le Gall and Grégory Miermont. Scaling limits of random trees and planar maps. In Probability and statistical physics in two and more dimensions, volume 15 of Clay Math. Proc., pages 155-211. Amer. Math. Soc., Providence, RI, 2012. · Zbl 1321.05240
[99] Malwina Luczak and Peter Winkler. Building uniformly random subtrees. Random Structures Algorithms, 24(4):420-443, 2004. · Zbl 1050.60007 · doi:10.1002/rsa.20011
[100] Russell Lyons. A bird’s-eye view of uniform spanning trees and forests. In Microsurveys in discrete probability (Princeton, NJ, 1997), volume 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 135-162. Amer. Math. Soc., Providence, RI, 1998. · Zbl 0909.60016
[101] Russell Lyons. Asymptotic enumeration of spanning trees. Combin. Probab. Comput., 14(4):491-522, 2005. · Zbl 1076.05007 · doi:10.1017/S096354830500684X
[102] Russell Lyons, Benjamin J. Morris, and Oded Schramm. Ends in uniform spanning forests. Electron. J. Probab., 13:no. 58, 1702-1725, 2008. · Zbl 1191.60016 · doi:10.1214/EJP.v13-566
[103] Colin McDiarmid. Random graphs from a minor-closed class. Combin. Probab. Comput., 18(4):583-599, 2009. · Zbl 1215.05167 · doi:10.1017/S0963548309009717
[104] Colin McDiarmid and Alex Scott. Random graphs from a block-stable class. European J. Combin., 58:96-106, 2016. · Zbl 1343.05137 · doi:10.1016/j.ejc.2016.05.005
[105] Laurent Ménard and Pierre Nolin. Percolation on uniform infinite planar maps. Electron. J. Probab., 19:no. 79, 27, 2014. · Zbl 1300.60114 · doi:10.1214/EJP.v19-2675
[106] Grégory Miermont. The Brownian map is the scaling limit of uniform random plane quadrangulations. Acta Math., 210(2):319-401, 2013. · Zbl 1278.60124 · doi:10.1007/s11511-013-0096-8
[107] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. · Zbl 0979.05002
[108] J. W. Moon. The number of labeled \(k\)-trees. J. Combinatorial Theory, 6:196-199, 1969. · Zbl 0175.50203 · doi:10.1016/S0021-9800(69)80119-5
[109] Marc Noy. Random planar graphs and beyond. Proc. ICM, 2014. · Zbl 1373.05015
[110] Konstantinos Panagiotou and Angelika Steger. Maximal biconnected subgraphs of random planar graphs. ACM Trans. Algorithms, 6(2):Art. 31, 21, 2010. · Zbl 1300.05287 · doi:10.1145/1721837.1721847
[111] Konstantinos Panagiotou and Angelika Steger. On the degree distribution of random planar graphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1198-1210. SIAM, Philadelphia, PA, 2011. · Zbl 1376.05034
[112] Konstantinos Panagiotou, Benedikt Stufler, and Kerstin Weller. Scaling limits of random graphs from subcritical classes. Ann. Probab., 44(5):3291-3334, 2016. · Zbl 1360.60073 · doi:10.1214/15-AOP1048
[113] Robin Pemantle. Choosing a spanning tree for the integer lattice uniformly. Ann. Probab., 19(4):1559-1574, 1991. · Zbl 0758.60010 · doi:10.1214/aop/1176990223
[114] Yuval Peres and David Revelle. Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs, 2004. · Zbl 1064.60095 · doi:10.1214/EJP.v9-198
[115] Jim Pitman. Combinatorial stochastic processes, volume 1875 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7-24, 2002, With a foreword by Jean Picard.
[116] Douglas Rizzolo. Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set. Ann. Inst. Henri Poincaré Probab. Stat., 51(2):512-532, 2015. · Zbl 1319.60170 · doi:10.1214/13-AIHP594
[117] Robert W. Robinson. Enumeration of non-separable graphs. J. Combinatorial Theory, 9:327-356, 1970. · Zbl 0217.02501 · doi:10.1016/S0021-9800(70)80089-8
[118] Gilles Schaeffer. Conjugaison d’arbres et cartes combinatoires aléatoires. PhD thesis Université de Boredaux 1, 1998.
[119] Robin Stephenson. Local convergence of large critical multi-type galton-watson trees and applications to random maps. Journal of Theoretical Probability, pages 1-47, 2016.
[120] Benedikt Stufler. Scaling limits of random outerplanar maps with independent link-weights. Ann. Inst. Henri Poincaré Probab. Stat., 53(2):900-915, 2017. · Zbl 1367.60031 · doi:10.1214/16-AIHP741
[121] Benedikt Stufler. Gibbs partitions: The convergent case. Random Structures & Algorithms, 53(3):537-558, 2018. · Zbl 1398.05184 · doi:10.1002/rsa.20771
[122] Benedikt Stufler. Random enriched trees with applications to random graphs. Electronic Journal of Combinatorics, 25(3), 2018. · Zbl 1393.60013
[123] Benedikt Stufler. Local convergence of random planar graphs. arXiv e-prints, arXiv:1908.04850, Aug 2019. · Zbl 1467.60066
[124] Benedikt Stufler. Local limits of large Galton-Watson trees rerooted at a random vertex. Ann. Inst. Henri Poincaré, Probab. Stat., 55(1):155-183, 2019. · Zbl 1467.60066 · doi:10.1214/17-AIHP879
[125] Lajos Takács. A generalization of the ballot problem and its application in the theory of queues. J. Amer. Statist. Assoc., 57:327-337, 1962. · Zbl 0109.36702
[126] E. · Zbl 0159.25501 · doi:10.1112/jlms/s1-43.1.720
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.