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 and the diameter is also of order 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).
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 et le diamètre est aussi de l’ordre 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).
@article{AIHPB_2015__51_4_1432_0, author = {Ray, Gourab}, title = {Large unicellular maps in high genus}, journal = {Annales de l'I.H.P. Probabilit\'es et statistiques}, pages = {1432--1456}, publisher = {Gauthier-Villars}, volume = {51}, number = {4}, year = {2015}, doi = {10.1214/14-AIHP618}, mrnumber = {3414452}, zbl = {1376.60011}, language = {en}, url = {http://www.numdam.org/articles/10.1214/14-AIHP618/} }
TY - JOUR AU - Ray, Gourab TI - Large unicellular maps in high genus JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2015 SP - 1432 EP - 1456 VL - 51 IS - 4 PB - Gauthier-Villars UR - http://www.numdam.org/articles/10.1214/14-AIHP618/ DO - 10.1214/14-AIHP618 LA - en ID - AIHPB_2015__51_4_1432_0 ER -
Ray, Gourab. Large unicellular maps in high genus. Annales de l'I.H.P. Probabilités et statistiques, Volume 51 (2015) no. 4, pp. 1432-1456. doi : 10.1214/14-AIHP618. http://www.numdam.org/articles/10.1214/14-AIHP618/
[1] Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees. Ann. Probab. 41 (2) (2013) 1072–1087. | MR | Zbl
, and .[2] The continuum random tree. I. Ann. Probab. 19 (1) (1991) 1–28. | MR | Zbl
.[3] Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 (5) (2003) 935–974. | MR | Zbl
.[4] The local limit of unicellular maps in high genus. Electron. Commun. Probab. 18 (2013) 1–8. | DOI | MR | Zbl
, , and .[5] Classification of half planar maps. Ann. Probab. 43 (2015) 1315–1349. | DOI | MR | Zbl
and .[6] Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2-3) (2003) 191–213. | MR | Zbl
and .[7] The local limit theorem and some related aspects of supercritical branching processes. Trans. Amer. Math. Soc. 152 (2) (1970) 233–251. | MR | Zbl
and .[8] Euclidean vs graph metric. Available at www.wisdom.weizmann.ac.il/~itai/erd100.pdf. | DOI | Zbl
.[9] Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (23) (2001) 1–13. | MR | Zbl
and .[10] 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] Scaling limits for random quadrangulations of positive genus. Electron. J. Probab. 15 (52) (2010) 1594–1644. | MR | Zbl
.[12] Large deviations in the supercritical branching process. Adv. in Appl. Probab. 25 (4) (1993) 757–772. | MR | Zbl
and .[13] A new combinatorial identity for unicellular maps, via a direct bijective approach. Adv. in Appl. Math. 47 (4) (2011) 874–893. | MR | Zbl
.[14] A simple model of trees for unicellular maps. J. Combin. Theory Ser. A 120 (8) (2013) 2064–2092. | MR | Zbl
, and .[15] A bijection for rooted maps on orientable surfaces. SIAM J. Discrete Math. 23 (3) (2009) 1587–1611. | MR | Zbl
, and .[16] An elementary proof of the local central limit theorem. J. Theoret. Probab. 8 (3) (1995) 693–701. | MR | Zbl
and .[17] Distances between pairs of vertices and vertical profile in conditioned Galton–Watson trees. Random Structures Algorithms 38 (4) (2011) 381–395. | MR | Zbl
and .[18] Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics, 4th edition. Cambridge Univ. Press, Cambridge, 2010. | DOI | MR | Zbl
.[19] Lower deviation probabilities for supercritical Galton–Watson processes. Ann. Inst. Henri Poincaré Probab. Stat. 43 (2) (2007) 233–255. | Numdam | MR | Zbl
and .[20] 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] The Theory of Branching Processes. Dover Phoenix Editions. Dover, Mineola, NY, 2002. Corrected reprint of the 1963 original [Springer, Berlin]. | MR | Zbl
.[22] 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] Subdiffusive behavior of random walk on a random cluster. Ann. Inst. Henri Poincaré Probab. Stat. 22 (4) (1986) 425–487. | Numdam | MR | Zbl
.[24] Local structure of random quadrangulations, 2005. Available at arXiv:math/0512304.
.[25] 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
and .[26] Random trees and applications. Probab. Surv. 2 (2005) 245–311. | DOI | MR | Zbl
.[27] Estimation of probabilities of large deviations for a critical Galton–Watson process. Theory Probab. Appl. 20 (1) (1975) 179–180. | MR | Zbl
and .Cited by Sources: