Tessellations of random maps of arbitrary genus

Miermont, Grégory

Annales scientifiques de l'École Normale Supérieure, Série 4, Tome 42 (2009) no. 5, pp. 725-781.

Nous examinons les propriétés de mosaïques de type Voronoï sur des quadrangulations bipartites de genre arbitraire. Ceci est rendu possible par une généralisation naturelle d'une bijection de Marcus et Schaeffer, permettant de décrire ces mosaïques par des cartes étiquetées avec un nombre fixé de faces, dont nous déterminons les limites d'échelle. Parmi les applications de ces résultats, figurent le comptage asymptotique des quadrangulations, ainsi que des propriétés métriques typiques de quadrangulations choisies au hasard. En particulier, nous montrons que les limites d'échelles de ces quadrangulations aléatoires sont telles que presque toute paire de points est liée par un unique chemin géodésique.

We investigate Voronoi-like tessellations of bipartite quadrangulations on surfaces of arbitrary genus, by using a natural generalization of a bijection of Marcus and Schaeffer allowing one to encode such structures by labeled maps with a fixed number of faces. We investigate the scaling limits of the latter. Applications include asymptotic enumeration results for quadrangulations, and typical metric properties of randomly sampled quadrangulations. In particular, we show that scaling limits of these random quadrangulations are such that almost every pair of points is linked by a unique geodesic.

Classification : 60C05, 05C30, 60F05
Keywords: random maps, scaling limits, random snakes, asymptotic enumeration, geodesics
Mot clés : cartes aléatoires, limites d'échelle, serpents aléatoires, comptage asymptotique, géodésiques

[1] D. Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), 1-28. | MR | Zbl

[2] J. Ambjørn, B. Durhuus & T. Jonsson, Quantum geometry. A statistical field theory approach, Cambridge Monographs on Mathematical Physics, Cambridge Univ. Press, 1997. | Zbl

[3] O. Angel, Growth and percolation on the uniform infinite planar triangulation, Geom. Funct. Anal. 13 (2003), 935-974. | Zbl

[4] E. A. Bender & E. R. Canfield, The asymptotic number of rooted maps on a surface, J. Combin. Theory 43 (1986), 244-257. | Zbl

[5] P. Billingsley, Convergence of probability measures, second éd., Probability and Statistics, John Wiley & Sons Inc., 1999. | Zbl

[6] N. Bourbaki, Éléments de mathématique, Topologie générale, chap. 1 à 4, Hermann, 1971. | Zbl

[7] J. Bouttier, P. Di Francesco & E. Guitter, Planar maps as labeled mobiles, Electron. J. Combin. 11 (2004), Research Paper 69 (electronic). | Zbl

[8] J. Bouttier & E. Guitter, Statistics in geodesics in large quadrangulations, J. Phys. 41 (2008), 145001, 30. | Zbl

[9] D. Burago, Y. Burago & S. Ivanov, A course in metric geometry, Graduate Studies in Math. 33, Amer. Math. Soc., 2001. | Zbl

[10] G. Chapuy, M. Marcus & G. Schaeffer, A bijection for rooted maps on orientable surfaces, preprint arXiv:0712.3649, 2007. | Zbl

[11] P. Chassaing & G. Schaeffer, Random planar lattices and integrated superBrownian excursion, Probab. Theory Related Fields 128 (2004), 161-212. | Zbl

[12] R. M. Dudley, Real analysis and probability, Cambridge Studies in Advanced Math. 74, Cambridge Univ. Press, 2002. | Zbl

[13] T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab. 31 (2003), 996-1027. | Zbl

[14] T. Duquesne & J.-F. Le Gall, Random trees, Lévy processes and spatial branching processes, Astérisque 281 (2002). | Numdam | Zbl

[15] T. Duquesne & J.-F. Le Gall, Probabilistic and fractal aspects of Lévy trees, Probab. Theory Related Fields 131 (2005), 553-603. | Zbl

[16] S. N. Evans, J. Pitman & A. Winter, Rayleigh processes, real trees, and root growth with re-grafting, Probab. Theory Related Fields 134 (2006), 81-126. | Zbl

[17] S. N. Evans & A. Winter, Subtree prune and regraft: a reversible real tree-valued Markov process, Ann. Probab. 34 (2006), 918-961. | Zbl

[18] P. Flajolet & R. Sedgewick, Analytic combinatorics, Cambridge Univ. Press, 2009. | MR | Zbl

[19] K. Fukaya, Collapsing of Riemannian manifolds and eigenvalues of Laplace operator, Invent. Math. 87 (1987), 517-547. | MR | Zbl

[20] Z. Gao, A pattern for the asymptotic number of rooted maps on surfaces, J. Combin. Theory 64 (1993), 246-264. | MR | Zbl

[21] A. Greven, P. Pfaffelhuber & A. Winter, Convergence in distribution of random metric measure spaces 2006. | MR | Zbl

[22] M. Gromov, Metric structures for Riemannian and non-Riemannian spaces, Progress in Math. 152, Birkhäuser, 1999. | MR | Zbl

[23] S. Janson & J.-F. Marckert, Convergence of discrete snakes, J. Theoret. Probab. 18 (2005), 615-647. | MR | Zbl

[24] S. K. Lando & A. K. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Math. Sciences 141, Springer, 2004. | MR | Zbl

[25] J.-F. Le Gall, The uniform random tree in a Brownian excursion, Probab. Theory Related Fields 96 (1993), 369-383. | MR | Zbl

[26] J.-F. Le Gall, The topological structure of scaling limits of large planar maps, Invent. Math. 169 (2007), 621-670. | MR | Zbl

[27] J.-F. Le Gall, Geodesics in large planar maps and in the Brownian map, preprint arXiv:0804.3012, 2008. | MR | Zbl

[28] J.-F. Le Gall & F. Paulin, Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere, Geom. Funct. Anal. 18 (2008), 893-918. | MR | Zbl

[29] T. Lévy, Yang-Mills measure on compact surfaces, Mem. Amer. Math. Soc. 166 (2003). | MR | Zbl

[30] J.-F. Marckert & G. Miermont, Invariance principles for random bipartite planar maps, Ann. Probab. 35 (2007), 1642-1705. | MR | Zbl

[31] J.-F. Marckert & A. Mokkadem, States spaces of the snake and its tour - convergence of the discrete snake, J. Theoret. Probab. 16 (2003), 1015-1046. | MR | Zbl

[32] J.-F. Marckert & A. Mokkadem, Limit of normalized quadrangulations: the Brownian map, Ann. Probab. 34 (2006), 2144-2202. | MR | Zbl

[33] M. Marcus & G. Schaeffer, Une bijection simple pour les cartes orientables, preprint http://www.lix.polytechnique.fr/~schaeffe/Biblio/MaSc01.ps, 2001.

[34] G. Miermont, An invariance principle for random planar maps, in Fourth Colloquium on Mathematics and Computer Sciences CMCS'06, Discrete Math. Theor. Comput. Sci. Proc., 2006, 39-58 (electronic). | MR | Zbl

[35] G. Miermont, Invariance principles for spatial multitype Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008), 1128-1161. | Numdam | MR | Zbl

[36] G. Miermont & M. Weill, Radius and profile of random planar maps with faces of arbitrary degrees, Electron. J. Probab. 13 (2008), 79-106. | MR | Zbl

[37] A. Okounkov, Random matrices and random permutations, Int. Math. Res. Not. 2000 (2000), 1043-1095. | MR | Zbl

[38] A. Okounkov & R. Pandharipande, Gromov-Witten theory, Hurwitz numbers, and matrix models, in Algebraic geometry - Seattle 2005. Part 1, Proc. Sympos. Pure Math. 80, Amer. Math. Soc., 2009, 325-414. | MR | Zbl

[39] V. V. Petrov, Sums of independent random variables, Springer, 1975. | MR | Zbl

[40] J. Pitman, Combinatorial stochastic processes, Lecture Notes in Math. 1875, Springer, 2006. | MR | Zbl

[41] D. Revuz & M. Yor, Continuous martingales and Brownian motion, third éd., Grund. Math. Wiss. 293, Springer, 1999. | MR | Zbl

[42] G. Schaeffer, Conjugaison d'arbres et cartes combinatoires aléatoires, Thèse de doctorat, Université Bordeaux I, 1998.

[43] S. Sheffield, Gaussian free fields for mathematicians, Probab. Theory Related Fields 139 (2007), 521-541. | MR | Zbl

[44] C. Villani, Optimal transport, Grund. Math. Wiss. 338, Springer, 2009. | MR | Zbl

[45] M. Weill, Asymptotics for rooted bipartite planar maps and scaling limits of two-type spatial trees, Electron. J. Probab. 12 (2007), 887-925. | MR | Zbl