Large unicellular maps in high genus

Ray, Gourab

Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4, pp. 1432-1456.

Nous étudions la géometrie d’une carte aléatoire unicellulaire qui est distribuée uniformement sur l’ensemble de toutes les cartes unicellulaires dont le genre est proportionnel au nombre des arrêtes. Nous prouvons que la distance entre deux sommets choisis uniformement d’une telle carte est de l’ordre $logn$ et le diamètre est aussi de l’ordre $logn$ avec une forte probabilité. Nous prouvons aussi une version quantitative du résultat que la carte est localement planaire avec une forte probabilité. L’ingrédient principal de la preuve est une procédure d’exploration qui utilise une bijection due au Chapuy, Féray et Fusy (J. Combin. Theory Ser. A 120 (2013) 2064–2092).

We study the geometry of a random unicellular map which is uniformly distributed on the set of all unicellular maps whose genus size is proportional to the number of edges. We prove that the distance between two uniformly selected vertices of such a map is of order $logn$ and the diameter is also of order $logn$ with high probability. We further prove a quantitative version of the result that the map is locally planar with high probability. The main ingredient of the proofs is an exploration procedure which uses a bijection due to Chapuy, Feray and Fusy (J. Combin. Theory Ser. A 120 (2013) 2064–2092).

Mots clés : unicellular maps, high genus maps, hyperbolic, diameter, typical distance, $C$-permutations

[1] L. Addario-Berry, L. Devroye and S. Janson. Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees. Ann. Probab. 41 (2) (2013) 1072–1087. | MR | Zbl

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

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

[4] O. Angel, G. Chapuy, N. Curien and G. Ray. The local limit of unicellular maps in high genus. Electron. Commun. Probab. 18 (2013) 1–8. | DOI | MR | Zbl

[5] O. Angel and G. Ray. Classification of half planar maps. Ann. Probab. 43 (2015) 1315–1349. | DOI | MR | Zbl

[6] O. Angel and O. Schramm. Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2-3) (2003) 191–213. | MR | Zbl

[7] K. Athreya and P. Ney. The local limit theorem and some related aspects of supercritical branching processes. Trans. Amer. Math. Soc. 152 (2) (1970) 233–251. | MR | Zbl

[8] I. Benjamini. Euclidean vs graph metric. Available at www.wisdom.weizmann.ac.il/~itai/erd100.pdf. | DOI | Zbl

[9] I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (23) (2001) 1–13. | MR | Zbl

[10] O. Bernardi. An analogue of the Harer–Zagier formula for unicellular maps on general surfaces. Adv. in Appl. Math. 48 (1) (2012) 164–180. | MR | Zbl

[11] J. Bettinelli. Scaling limits for random quadrangulations of positive genus. Electron. J. Probab. 15 (52) (2010) 1594–1644. | MR | Zbl

[12] J. D. Biggins and N. H. Bingham. Large deviations in the supercritical branching process. Adv. in Appl. Probab. 25 (4) (1993) 757–772. | MR | Zbl

[13] G. Chapuy. A new combinatorial identity for unicellular maps, via a direct bijective approach. Adv. in Appl. Math. 47 (4) (2011) 874–893. | MR | Zbl

[14] G. Chapuy, V. Féray and É. Fusy. A simple model of trees for unicellular maps. J. Combin. Theory Ser. A 120 (8) (2013) 2064–2092. | MR | Zbl

[15] G. Chapuy, M. Marcus and G. Schaeffer. A bijection for rooted maps on orientable surfaces. SIAM J. Discrete Math. 23 (3) (2009) 1587–1611. | MR | Zbl

[16] B. Davis and D. Mcdonald. An elementary proof of the local central limit theorem. J. Theoret. Probab. 8 (3) (1995) 693–701. | MR | Zbl

[17] L. Devroye and S. Janson. Distances between pairs of vertices and vertical profile in conditioned Galton–Watson trees. Random Structures Algorithms 38 (4) (2011) 381–395. | MR | Zbl

[18] R. Durrett. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics, 4th edition. Cambridge Univ. Press, Cambridge, 2010. | DOI | MR | Zbl

[19] K. Fleischmann and V. Wachtel. Lower deviation probabilities for supercritical Galton–Watson processes. Ann. Inst. Henri Poincaré Probab. Stat. 43 (2) (2007) 233–255. | Numdam | MR | Zbl

[20] M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Modern Birkhäuser Classics, english edition. Birkhäuser, Boston, MA, 2007. Based on the 1981 French original. With appendices by M. Katz, P. Pansu and S. Semmes. Translated from the French by Sean Michael Bates. | MR | Zbl

[21] T. E. Harris. The Theory of Branching Processes. Dover Phoenix Editions. Dover, Mineola, NY, 2002. Corrected reprint of the 1963 original [Springer, Berlin]. | MR | Zbl

[22] N. I. Kazimirov. The occurrence of a gigantic component in a random permutation with a known number of cycles. Diskret. Mat. 15 (3) (2003) 145–159. | MR | Zbl

[23] H. Kesten. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. Henri Poincaré Probab. Stat. 22 (4) (1986) 425–487. | Numdam | MR | Zbl

[24] M. Krikun. Local structure of random quadrangulations, 2005. Available at arXiv:math/0512304.

[25] S. K. Lando and A. K. Zvonkin. Graphs on Surfaces and Their Applications. Encyclopedia of Mathematical Sciences 141. Springer, Berlin, 2004. With an appendix by Don B. Zagier, Low-Dimensional Topology. II. | MR | Zbl

[26] J. F. Le Gall. Random trees and applications. Probab. Surv. 2 (2005) 245–311. | DOI | MR | Zbl

[27] S. V. Nagaev and N. V. Vahrusev. Estimation of probabilities of large deviations for a critical Galton–Watson process. Theory Probab. Appl. 20 (1) (1975) 179–180. | MR | Zbl