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).
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).
@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},
volume = {51},
year = {2015},
pages = {1432-1456},
doi = {10.1214/14-AIHP618},
mrnumber = {3414452},
language = {en},
url = {http://dml.mathdoc.fr/item/AIHPB_2015__51_4_1432_0}
}
Ray, Gourab. Large unicellular maps in high genus. Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) pp. 1432-1456. doi : 10.1214/14-AIHP618. http://gdmltest.u-ga.fr/item/AIHPB_2015__51_4_1432_0/
[1] , and . Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees. Ann. Probab. 41 (2) (2013) 1072–1087. | MR 3077536 | Zbl 1278.60128
[2] . The continuum random tree. I. Ann. Probab. 19 (1) (1991) 1–28. | MR 1085326 | Zbl 0722.60013
[3] . Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 (5) (2003) 935–974. | MR 2024412 | Zbl 1039.60085
[4] , , and . The local limit of unicellular maps in high genus. Electron. Commun. Probab. 18 (2013) 1–8. | MR 3141795 | Zbl 06346935
[5] and . Classification of half planar maps. Ann. Probab. 43 (2015) 1315–1349. | MR 3342664
[6] and . Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2-3) (2003) 191–213. | MR 2013797 | Zbl 1098.60010
[7] and . The local limit theorem and some related aspects of supercritical branching processes. Trans. Amer. Math. Soc. 152 (2) (1970) 233–251. | MR 268971 | Zbl 0214.16203
[8] . Euclidean vs graph metric. Available at www.wisdom.weizmann.ac.il/~itai/erd100.pdf.
[9] and . Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (23) (2001) 1–13. | MR 1873300 | Zbl 1010.82021
[10] . An analogue of the Harer–Zagier formula for unicellular maps on general surfaces. Adv. in Appl. Math. 48 (1) (2012) 164–180. | MR 2845513 | Zbl 1233.05090
[11] . Scaling limits for random quadrangulations of positive genus. Electron. J. Probab. 15 (52) (2010) 1594–1644. | MR 2735376 | Zbl 1226.60047
[12] and . Large deviations in the supercritical branching process. Adv. in Appl. Probab. 25 (4) (1993) 757–772. | MR 1241927 | Zbl 0796.60090
[13] . A new combinatorial identity for unicellular maps, via a direct bijective approach. Adv. in Appl. Math. 47 (4) (2011) 874–893. | MR 2832383 | Zbl 1234.05037
[14] , and . A simple model of trees for unicellular maps. J. Combin. Theory Ser. A 120 (8) (2013) 2064–2092. | MR 3102175 | Zbl 1278.05081
[15] , and . A bijection for rooted maps on orientable surfaces. SIAM J. Discrete Math. 23 (3) (2009) 1587–1611. | MR 2563085 | Zbl 1207.05087
[16] and . An elementary proof of the local central limit theorem. J. Theoret. Probab. 8 (3) (1995) 693–701. | MR 1340834 | Zbl 0841.60013
[17] and . Distances between pairs of vertices and vertical profile in conditioned Galton–Watson trees. Random Structures Algorithms 38 (4) (2011) 381–395. | MR 2829308 | Zbl 1223.05049
[18] . Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics, 4th edition. Cambridge Univ. Press, Cambridge, 2010. | MR 2722836 | Zbl 1202.60001
[19] and . Lower deviation probabilities for supercritical Galton–Watson processes. Ann. Inst. Henri Poincaré Probab. Stat. 43 (2) (2007) 233–255. | Numdam | MR 2303121 | Zbl 1112.60066
[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 2307192 | Zbl 1113.53001
[21] . The Theory of Branching Processes. Dover Phoenix Editions. Dover, Mineola, NY, 2002. Corrected reprint of the 1963 original [Springer, Berlin]. | MR 163361 | Zbl 1037.60001
[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 2021211 | Zbl 1048.60008
[23] . Subdiffusive behavior of random walk on a random cluster. Ann. Inst. Henri Poincaré Probab. Stat. 22 (4) (1986) 425–487. | Numdam | MR 871905 | Zbl 0632.60106
[24] . Local structure of random quadrangulations, 2005. Available at arXiv:math/0512304.
[25] and . 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 2036721 | Zbl 1040.05001
[26] . Random trees and applications. Probab. Surv. 2 (2005) 245–311. | MR 2203728 | Zbl 1189.60161
[27] and . Estimation of probabilities of large deviations for a critical Galton–Watson process. Theory Probab. Appl. 20 (1) (1975) 179–180. | MR 370807 | Zbl 0356.60043