Miermont, Grégory
Tessellations of random maps of arbitrary genus  [ Mosaïques sur des cartes aléatoires en genre arbitraire ]
Annales scientifiques de l'École Normale Supérieure, Série 4 : Tome 42 (2009) no. 5 , p. 725-781
Zbl 1228.05118 | 2 citations dans Numdam
doi : 10.24033/asens.2108
URL stable : http://www.numdam.org/item?id=ASENS_2009_4_42_5_725_0

Classification:  60C05,  05C30,  60F05
Mots clés: cartes aléatoires, limites d'échelle, serpents aléatoires, comptage asymptotique, géodésiques
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 usilg a natural generalization of a bijection of Marcus and Schaeffer allowilg one to encode such structures by labeled maps with a fixed number of faces. We investigate the scalilg limits of the latter. Applications include asymptotic enumeration results for quadrangulations, and typical metric properties of randomly sampled quadrangulations. In particular, we show that scalilg limits of these random quadrangulations are such that almost every pair of points is linked by a unique geodesic.

Bibliographie

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

[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 1096.82500

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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 2033196 | Zbl 1044.60083

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

[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 2509622 | Zbl 1195.60049

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

[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 2375600 | Zbl 1190.60024

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

[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 2483941 | Zbl 1205.14072

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

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

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

[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 2322706 | Zbl 1132.60072

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

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