Local limit of labeled trees and expected volume growth in a random quadrangulation. (English) Zbl 1102.60007

Well-labeled trees are studied by R. Cori and B. Vanquelin [Can. J. Math. 33, 1023–1042 (1981; Zbl 0415.05020)], who established a relationship between the number of well-labeled trees of size \(N\) and the number of quadrangulated planar maps with \(N\) faces. Given a probability measure on a space of planar maps (called also ensemble of planar maps), a relevant quantity of interest is the exponent \(\alpha\) that characterizes the expected volume of growth of the maps. Let \(B_r(\mathcal{M})\) be a ball of radius \(r\) around a marked point on the surface \(\mathcal{M}\) and let \(| B_r(\mathcal{M})|\) denote its volume, that is, the number of vertices in \(B_r(\mathcal{M})\). Then, \(\alpha\) is determined by the relation \(E(|B_r|)=\Theta(r^{\alpha})\) if this number \(\alpha\) exists. The expectation is taken with respect to the given probability measure and \(\Theta(r^{\alpha})\) denotes a function bounded from above and below by positive constant multiples of \(r^{\alpha}\) as \(r\) becomes large. In the present paper the authors exploit a bijective correspondence between planar quadrangulations and well-labeled trees to construct, using simple combinatorial arguments, a uniform probability measure \(\mu\) on the set of infinite well-labeled trees. They show how to identify well-labeled trees in the support of this measure with infinite quadrangulated planar surfaces. Then, viewing \(\mu\) as a measure on these surfaces, the authors prove that the exponent \(\alpha\) of the expected volume growth is equal to \(4\). To prove this result they show that the random surface, obtained in the limit, can be described in terms of a birth and death process and of a sequence of multitype Galton-Watson trees.


60C05 Combinatorial probability
05C30 Enumeration in graph theory
05C05 Trees
82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics


Zbl 0415.05020
Full Text: DOI arXiv


[1] Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 228–266. · Zbl 0733.60016 · doi:10.1214/aoap/1177005936
[2] Aldous, D. (1993). Tree-based models for random distribution of mass. J. Statist. Phys. 73 625–641. · Zbl 1102.60318 · doi:10.1007/BF01054343
[3] Ambjørn, J., Durhuus, B. and Fröhlich, J. (1985). Diseases of triangulated random surfaces. Nuclear Phys. B 257 433–449. · doi:10.1016/0550-3213(85)90356-6
[4] Ambjørn, J., Durhuus, B. and Jónsson, T. (1991). Three-dimensional simplicial quantum gravity and generalized matrix models. Mod. Phys. Lett. A 6 1133–1147. · Zbl 1020.83537 · doi:10.1142/S0217732391001184
[5] Ambjørn, J., Durhuus, B. and Jónsson, T. (1997). Quantum Geometry. A Statistical Field Theory Approach . Cambridge Univ. Press. · Zbl 0993.82500 · doi:10.1017/CBO9780511524417
[6] Ambjørn, J. and Watabiki, Y. (1995). Scaling in quantum gravity. Nuclear Phys. B 445 129–142. · Zbl 1006.83015 · doi:10.1016/0550-3213(95)00154-K
[7] Angel, O. (2003). Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 935–974. · Zbl 1039.60085 · doi:10.1007/s00039-003-0436-5
[8] Angel, O. and Schramm, O. (2003). Uniform infinite planar triangulations. Comm. Math. Phys. 241 191–214. · Zbl 1098.60010 · doi:10.1007/s00220-003-0932-3
[9] Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York. · Zbl 0172.21201
[10] Bouttier, J., Di Francesco, P. and Guitter, E. (2003). Geodesic distance in planar graphs. Nuclear Phys. B 663 535–567. · Zbl 1022.05022 · doi:10.1016/S0550-3213(03)00355-9
[11] Brezin, E., Itzykson, C., Parisi, G. and Zuber, J.-B. (1978). Planar diagrams. Comm. Math. Phys. 59 1035–1047. · Zbl 0997.81548 · doi:10.1007/BF01614153
[12] Chassaing, P. and Schaeffer, G. (2004). Random planar lattices and integrated superBrownian excursion. Probab. Theory Related Fields 128 161–212. · Zbl 1041.60008 · doi:10.1007/s00440-003-0297-8
[13] Cori, R. and Vauquelin, B. (1981). Planar maps are well labeled trees. Canad. J. Math. 33 1023–1042. · Zbl 0415.05020 · doi:10.4153/CJM-1981-078-2
[14] David, F. (1985). Planar diagrams, two-dimensinal lattice gravity and surface models. Nuclear Phys. B 257 45–58. · doi:10.1016/0550-3213(85)90335-9
[15] Durhuus, B. (2003). Probabilistic aspects of planar trees and surfaces. Acta Phys. Polonica B 34 4795–4811.
[16] Gillet, F. (2003). Études d’algorithmes stochastiques et arbres. Ph.D. thesis, Univ. Henri Poincaré, Nancy. Available at www.iecn.u-nancy.fr/ chassain.
[17] Flajolet, P. and Odlyzko, A. M. (1990). Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240. · Zbl 0712.05004 · doi:10.1137/0403019
[18] Flajolet, P. and Sedgewick, R. (2006). Analytic combinatorics. Available at algo.inria.fr/flajolet/Publications/books.html. · Zbl 1165.05001
[19] Janson, S. (2002). Ideals in a forest, one-way infinite binary trees and the contraction method. In Mathematics and Computer Science (B. Chauvin, P. Flajolet, D. Gardy and A. Mokkadem, eds.) 2 393–414. Birkhäuser, Basel. · Zbl 1023.60011
[20] Karlin, S. and Taylor, H. M. (1975). A First Course in Stochastic Processes , 2nd ed. Academic Press, New York. · Zbl 0315.60016
[21] Kazakov, V. A., Kostov, I. and Migdal, A. A. (1985). Critical properties of randomly triangulated planar random surfaces. Phys. Lett. B 157 295–300. · doi:10.1016/0370-2693(85)90669-0
[22] Kurtz, T., Lyons, R., Pemantle, R. and Peres, Y. (1997). A conceptual proof of the Kesten–Stigum theorem for multi-type branching processes. In Classical and Modern Branching Processes (K. B. Athreya and P. Jagers, eds.) 181–185. Springer, New York. · Zbl 0868.60068
[23] Le Gall, J.-F. (1986). An elementary approach to Williams’ decomposition theorems. Séminaire de Probabilités XX . Lecture Notes in Math. 1204 447–464. Springer, Berlin. · Zbl 0604.60081 · doi:10.1007/BFb0075735
[24] Lyons, R., Pemantle, R. and Peres, Y. (1995). Conceptual proofs of L log L criteria for mean behavior of branching processes. Ann. Probab. 23 1125–1138. · Zbl 0840.60077 · doi:10.1214/aop/1176988176
[25] Newman, M. H. A. (1992). Elements of the Topology of Plane Sets of Points. (Reprint of the second edition) Dover, New York. · Zbl 0845.54002
[26] Rudin, W. (1987). Real and Complex Analysis , 3rd ed. McGraw–Hill, New York. · Zbl 0925.00005
[27] Schaeffer, G. (1998). Conjugaison d’arbres et cartes combinatoires aléatoires. Ph.D. thesis, Université Bordeaux I, 1998, Bordeaux.
[28] Slade, G. (2002). Scaling limits and super-Brownian motion. Notices Amer. Math. Soc. 49 1056–1067. · Zbl 1126.60322
[29] Tutte, W. T. (1963). A census of planar maps. Canad. J. Math. 15 249–271. · Zbl 0115.17305 · doi:10.4153/CJM-1963-029-x
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.