Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-16T17:24:29.542Z Has data issue: false hasContentIssue false
  • English
  • Français

Volumes in the Uniform Infinite Planar Triangulation: From Skeletons to Generating Functions

Part of: Graph theory

Published online by Cambridge University Press:  21 May 2018

LAURENT MÉNARD
LAURENT MÉNARD*
Affiliation:
Modal'X, Université Paris Ouest and LiX, École Polytechnique, 200 avenue de la République, 92000 Nanterre, France (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We develop a method to compute the generating function of the number of vertices inside certain regions of the Uniform Infinite Planar Triangulation (UIPT). The computations are mostly combinatorial in flavour and the main tool is the decomposition of the UIPT into layers, called the skeleton decomposition, introduced by Krikun [20]. In particular, we get explicit formulas for the generating functions of the number of vertices inside hulls (or completed metric balls) centred around the root, and the number of vertices inside geodesic slices of these hulls. We also recover known results about the scaling limit of the volume of hulls previously obtained by Curien and Le Gall by studying the peeling process of the UIPT in [17].

MSC classification

Secondary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 6 , November 2018 , pp. 946 - 973
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Abraham, C. (2016) Rescaled bipartite planar maps converge to the Brownian map. Ann. Inst. Henri Poincaré Probab. Stat. 52 575–595.Google Scholar
[2] Addario-Berry, L. and Albenque, M. (2017) The scaling limit of random simple triangulations and random simple quadrangulations. Ann. Probab. 45 (5) 2767–2825.Google Scholar
[3] Ambjørn, J., Durhuus, B. and Jonsson, T. (1997) Quantum Geometry: A Statistical Field Theory Approach, Cambridge Monographs on Mathematical Physics, Cambridge University Press.Google Scholar
[4] Ambjørn, J. and Watabiki, Y. (1995) Scaling in quantum gravity. Nuclear Phys. B 445 129–142.Google Scholar
[5] Angel, O. (2003) Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 935–974.Google Scholar
[6] Angel, O. and Curien, N. (2015) Percolations on random maps I: Half-plane models. Ann. Inst. Henri Poincaré Probab. Stat. 51 405–431.Google Scholar
[7] Angel, O. and Schramm, O. (2003) Uniform infinite planar triangulations. Comm. Math. Phys. 241 191–213.Google Scholar
[8] Benjamini, I. and Curien, N. (2013) Simple random walk on the uniform infinite planar quadrangulation: Subdiffusivity via pioneer points. Geom. Funct. Anal. 23 501–531.Google Scholar
[9] Bertoin, J., Curien, N. and Kortchemski, I. (2018) Random planar maps and growth fragmentations. Ann. Probab. 46 (1) 207–260.Google Scholar
[10] Bettinelli, J., Jacob, E. and Miermont, G. (2014) The scaling limit of uniform random plane maps, via the Ambjørn–Budd bijection. Electron. J. Probab. 19 #74.Google Scholar
[11] Bouttier, J., Di Francesco, P. and Guitter, E. (2004) Planar maps as labeled mobiles. Electron. J. Combin. 11 #R69.Google Scholar
[12] Budd, T. (2016) The peeling process of infinite Boltzmann planar maps. Electron. J. Combin. 23 (1) Paper 1.28.Google Scholar
[13] Chassaing, P. and Schaeffer, G. (2004) Random planar lattices and integrated superBrownian excursion. Probab. Theory Rel. Fields 128 161–212.Google Scholar
[14] Cori, R. and Vauquelin, B. (1981) Planar maps are well labeled trees. Canad. J. Math. 33 1023–1042.Google Scholar
[15] Curien, N. (2015) A glimpse of the conformal structure of random planar maps. Comm. Math. Phys. 333 1417–1463.Google Scholar
[16] Curien, N. and Le Gall, J.-F. (2015) First-passage percolation and local modifications of distances in random triangulations. arXiv:1511.04264Google Scholar
[17] Curien, N. and Le Gall, J.-F. (2017) Scaling limits for the peeling process on random maps. Ann. Inst. Henri Poincaré Probab. Stat. 53 (1) 322–357.Google Scholar
[18] Curien, N. and Le Gall, J.-F. (2019) The hull process of the Brownian plane. Probab. Theory Rel. Fields 166 (1–2) 147–209.Google Scholar
[19] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[20] Krikun, M. (2005) Uniform infinite planar triangulation and related time-reversed critical branching process. J. Math. Sci. 131 5520–5537.Google Scholar
[21] Krikun, M. (2005) Local structure of random quadrangulations. arXiv:math/0512304v2Google Scholar
[22] Le Gall, J.-F. (2013) Uniqueness and universality of the Brownian map. Ann. Probab. 41 2880–2960.Google Scholar
[23] Le Gall, J.-F. (2014) The Brownian map: A universal limit for random planar maps. In XVIIth International Congress on Mathematical Physics, World Scientific, pp. 420–428.Google Scholar
[24] Ménard, L. and Nolin, P. (2014) Percolation on uniform infinite planar maps. Electron. J. Probab. 19 #79.Google Scholar
[25] Miermont, G. (2013) The Brownian map is the scaling limit of uniform random plane quadrangulations. Acta Math. 210 319–401.Google Scholar
[26] Miermont, G. (2014) Aspects of Random Planar Maps, Saint Flour Lecture Notes, in preparation.Google Scholar
[27] Miller, J. and Sheffield, S. (2015) An axiomatic characterization of the Brownian map. arXiv:1506.03806Google Scholar
[28] Richier, L. (2015) Universal aspects of critical percolation on random half-planar maps. Electron. J. Probab. 20 #129.Google Scholar
[29] Schaeffer, G. (1998) Conjugaison d'arbres et cartes combinatoires aléatoires. PhD thesis, Université Bordeaux I.Google Scholar
[30] Watabiki, Y. (1995) Construction of non-critical string field theory by transfer matrix formalism in dynamical triangulation. Nuclear Phys. B 441 119–163.Google Scholar