×

zbMATH — the first resource for mathematics

Local convergence of large critical multi-type Galton-Watson trees and applications to random maps. (English) Zbl 1393.05244
Summary: We show that large critical multi-type Galton-Watson trees, when conditioned to be large, converge locally in distribution to an infinite tree which is analogous to Kesten’s infinite monotype Galton-Watson tree. This is proven when we condition on the number of vertices of one fixed type, and with an extra technical assumption if we count at least two types. We then apply these results to study local limits of random planar maps, showing that large critical Boltzmann-distributed random maps converge in distribution to an infinite map.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
05C63 Infinite graphs
05C81 Random walks on graphs
60B10 Convergence of probability measures
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Abraham, C, Rescaled bipartite planar maps converge to the Brownian map, Ann. Inst. H. Poincaré Probab. Stat., 52, 575-595, (2016) · Zbl 1375.60034
[2] Abraham, R; Delmas, J-F, Local limits of conditioned Galton-Watson trees: the infinite spine case, Electron. J. Probab., 19, 1-19, (2014) · Zbl 1285.60085
[3] Abraham, R., Delmas, J.-F., Guo, H.: Critical multi-type Galton-Watson trees conditioned to be large. arXiv:1511.01721 · Zbl 1422.60146
[4] Ambjørn, J., Jónsson, T., Durhuus, B.: Quantum Geometry: A Statistical Field Theory Approach. Cambridge University Press, Cambridge (1997) · Zbl 0993.82500
[5] Angel, O; Schramm, O, Uniform infinite planar triangulations, Commun. Math. Phys., 241, 191-213, (2003) · Zbl 1098.60010
[6] Bettinelli, J; Jacob, E; Miermont, G, The scaling limit of uniform random plane maps, via the ambjørn-budd bijection, Electron. J. Probab., 19, 1-16, (2014) · Zbl 1320.60088
[7] Björnberg, J; Stefánsson, S, Recurrence of bipartite planar maps, Electron. J. Probab., 19, 1-40, (2014) · Zbl 1286.05153
[8] Bouttier, J; Francesco, P; Guitter, E, Planar maps as labeled mobiles, Electron. J. Comb., 11, 69, (2004) · Zbl 1060.05045
[9] Curien, N; Gall, J-F; Miermont, G, The Brownian cactus I. scaling limits of discrete cactuses, Ann. Inst. H. Poincaré Probab. Stat., 49, 340-373, (2013) · Zbl 1275.60035
[10] Curien, N; Ménard, L; Miermont, G, A view from infinity of the uniform planar quadrangulation, ALEA Lat. Am. J. Probab. Math. Stat., 10, 45-88, (2013) · Zbl 1277.05151
[11] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001
[12] Gurel-Gurevich, O; Nachmias, A, Recurrence of planar graph limits, Ann. Math., 177, 761-781, (2013) · Zbl 1262.05031
[13] Janson, S, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., 9, 103-252, (2012) · Zbl 1244.60013
[14] Kallenberg, O.: Foundations of Modern Probability, Applied Probability. Springer, Berlin (2002) · Zbl 0996.60001
[15] Kesten, H, Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincaré Probab. Stat., 22, 425-487, (1986) · Zbl 0632.60106
[16] Krikun, M.: Local structure of random quadrangulations. (2005). arXiv:math/0512304 · Zbl 1137.60314
[17] Kurtz, T., Lyons, R., Pemantle, R., Peres, Y.: A conceptual proof of the Kesten-Stigum theorem for multi-type branching processes. In: Athreya, K.B., et al. (eds.) Classical and Modern Branching Processes. Proceedings of the IMA Workshop, Minneapolis, MN, USA, June 13-17, 1994. Springer, New York. IMA Vol. Math. Appl. 84, 181-185 (1997) · Zbl 0868.60068
[18] Lando, S., Zvonkin, A., Zagier, D.: Graphs on Surfaces and Their Applications, Encyclopaedia of Mathematical Sciences. Springer, Berlin (2004)
[19] Gall, J-F, Uniqueness and universality of the Brownian map, Ann. Probab., 41, 2880-2960, (2013) · Zbl 1282.60014
[20] Lyons, R., Peres, Y.: Probability on Trees and Networks. Cambridge University Press, Cambridge (2014) · Zbl 1376.05002
[21] Marckert, J-F; Miermont, G, Invariance principles for random bipartite planar maps, Ann. Probab., 35, 1642-1705, (2007) · Zbl 1208.05135
[22] Meir, A; Moon, J, On an asymptotic method in enumeration, J. Comb. Theory Ser. A, 51, 77-89, (1989) · Zbl 0683.05001
[23] Ménard, L; Nolin, P, Percolation on uniform infinite planar maps, Electron. J. Probab., 19, 1-27, (2014) · Zbl 1300.60114
[24] Miermont, G.: An invariance principles for random maps. In: DMTCS Proceedings, pp. 39-58 (2006) · Zbl 1195.60049
[25] Miermont, G, Invariance principles for spatial multitype Galton-Watson trees, Ann. Inst. H. Poincaré Probab. Stat., 44, 1128-1161, (2008) · Zbl 1178.60058
[26] Miermont, G, The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math., 210, 319-401, (2013) · Zbl 1278.60124
[27] Neveu, J, Arbres et processus de Galton-Watson, Ann. Inst. H. Poincaré Probab. Stat., 22, 199-207, (1986) · Zbl 0601.60082
[28] Pénisson, S, Beyond the Q-process: various ways of conditioning the multitype Galton-Watson process, ALEA Lat. Am. J. Probab. Math. Stat., 13, 223-237, (2016) · Zbl 1337.60215
[29] Pitman, J.: Combinatorial Stochastic Processes, vol. 1875 of Lecture Notes in Mathematics. Springer, 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 (2006)
[30] Schaeffer, G.: Conjugaison d’arbres et de cartes combinatoires aléatoires. PhD Thesis, Université Bordeaux I (1998) · Zbl 1375.60034
[31] Spitzer, F.: Principles of Random Walk, Graduate Texts in Mathematics. Springer, Berlin (2001)
[32] Tutte, WT, A census of planar maps, Can. J. Math., 15, 249-271, (1963) · Zbl 0115.17305
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.