×

The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees. (English) Zbl 1195.60013

Author’s abstract: A unicellular map is a map which has only one face. We give a bijection between a dominant subset of rooted unicellular maps of given genus and a set of rooted plane trees with distinguished vertices. The bijection applies as well to the case of labelled unicellular maps, which are related to all rooted maps by Marcus and Schaeffer’s bijection. This gives an immediate derivation of the asymptotic number of unicellular maps of given genus, and a simple bijective proof of a formula of Lehman and Walsh on the number of triangulations with one vertex. From the labelled case, we deduce an expression of the asymptotic number of maps of genus \(g\) with \(n\) edges involving the ISE random measure, and an explicit characterization of the limiting profile and radius of random bipartite quadrangulations of genus \(g\) in terms of the ISE.

MSC:

60C05 Combinatorial probability
05A17 Combinatorial aspects of partitions of integers
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D., Tree-based models for random distribution of mass, J. Stat. Phys., 73, 3-4, 625-641 (1993) · Zbl 1102.60318 · doi:10.1007/BF01054343
[2] Bender, E. A.; Canfield, E. R., The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A, 43, 2, 244-257 (1986) · Zbl 0606.05031 · doi:10.1016/0097-3165(86)90065-8
[3] Bouttier, J.; Di Francesco, P.; Guitter, E., Census of planar maps: from the one-matrix model solution to a combinatorial proof, Nuclear Phys. B, 645, 3, 477-499 (2002) · Zbl 0999.05052 · doi:10.1016/S0550-3213(02)00813-1
[4] Bouttier, J.; Di Francesco, P.; Guitter, E., Geodesic distance in planar graphs, Nuclear Phys. B, 663, 3, 535-567 (2003) · Zbl 1022.05022 · doi:10.1016/S0550-3213(03)00355-9
[5] Bouttier, J., Di Francesco, P., Guitter, E.: Planar maps as labeled mobiles. Electron. J. Combin. 11(1):Research Paper 69, 27 pp. (electronic) (2004) · Zbl 1060.05045
[6] Bouttier, J., Guitter E.: The three-point function of planar quadrangulations. arXiv:0805.2355 [math-ph] (2008) · Zbl 1459.82102
[7] Bender, E., Gao, Z.C., Richmond, L.B.: The map asymptotics constant t_g. Electron. J. Combin. 15 (2008) · Zbl 1159.05026
[8] Billingsley, P., Convergence of probability measures (1968), New York: Wiley, New York · Zbl 0172.21201
[9] Bousquet-Mélou, M.; Janson, S., The density of the ISE and local limit laws for embedded trees, Ann. Appl. Probab., 16, 3, 1597-1632 (2006) · Zbl 1132.60009 · doi:10.1214/105051606000000213
[10] Bousquet-Mélou, M.; Schaeffer, G., Enumeration of planar constellations, Adv. Appl. Math., 24, 4, 337-368 (2000) · Zbl 0955.05004 · doi:10.1006/aama.1999.0673
[11] Bacher, R.; Vdovina, A., Counting 1-vertex triangulations of oriented surfaces, Discrete Math., 246, 1-3, 13-27 (2002) · Zbl 0994.05058 · doi:10.1016/S0012-365X(01)00249-7
[12] Chapuy, G.: Asymptotic enumeration of constellations and related families of maps on orientable surfaces. Combin. Probab. Comput. (2009, to appear) · Zbl 1221.05204
[13] Chapuy, G., Marcus, M., Schaeffer, G.: On the number of rooted maps on orientable surfaces. arXiv:0712.3649 [math.CO] (2007) · Zbl 1207.05087
[14] Chassaing, P.; Schaeffer, G., Random planar lattices and integrated superBrownian excursion, Probab. Theory Relat. Fields, 128, 2, 161-212 (2004) · Zbl 1041.60008 · doi:10.1007/s00440-003-0297-8
[15] Flajolet, P.; Odlyzko, A., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 2, 216-240 (1990) · Zbl 0712.05004 · doi:10.1137/0403019
[16] Goulden, I.P., Jackson, D.M.: The KP hierarchy, branched covers, and triangulations. arXiv:0803.3980 (2008) · Zbl 1158.37026
[17] Goupil, A.; Schaeffer, G., Factoring n-cycles and counting maps of given genus, Eur. J. Combin., 19, 7, 819-834 (1998) · Zbl 0915.05007 · doi:10.1006/eujc.1998.0215
[18] Harer, J.; Zagier, D., The Euler characteristic of the moduli space of curves, Invent. Math., 85, 3, 457-485 (1986) · Zbl 0616.14017 · doi:10.1007/BF01390325
[19] Jackson, D. M., Counting cycles in permutations by group characters, with an application to a topological problem, Trans. Am. Math. Soc., 299, 2, 785-801 (1987) · Zbl 0655.05005 · doi:10.2307/2000524
[20] Kallenberg, O., Foundations of modern probability. Probability and its applications (New York) (1997), New York: Springer, New York · Zbl 0892.60001
[21] Le Gall, J.-F., The topological structure of scaling limits of large planar maps, Invent. Math., 169, 621-670 (2007) · Zbl 1132.60013 · doi:10.1007/s00222-007-0059-9
[22] Le Gall, J.F.: Geodesics in large planar maps and in the brownian map. arXiv:0804.3012 (2008) · Zbl 1214.53036
[23] Le Gall, J.-F., Paulin, F.: Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. Geometr. Funct. Anal. (2009, to appear) · Zbl 1166.60006
[24] Lando, S.K., Zvonkin, A.K.: Graphs on surfaces and their applications. Encyclopaedia of Mathematical Sciences, vol. 141. Springer, Berlin (2004) (with an appendix by Don B. Zagier, Low-Dimensional Topology, II) · Zbl 1040.05001
[25] Miermont, G.: Tessellations of random maps of arbitrary genus. arXiv:0712.3688 [math.PR] (2007) · Zbl 1228.05118
[26] Marckert, J.-F.; Mokkadem, A., Limit of normalized quadrangulations: the Brownian map, Ann. Probab., 34, 6, 2144-2202 (2006) · Zbl 1117.60038 · doi:10.1214/009117906000000557
[27] Marcus, M., Schaeffer, G.: Une bijection simple pour les cartes orientables. manuscript (see http://www.lix.polytechnique.fr/schaeffe/Biblio/) (2001)
[28] Mohar, B.; Thomassen, C., Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences (2001), Baltimore: Johns Hopkins University Press, Baltimore · Zbl 0979.05002
[29] Schaeffer, G.: Conjugaison d’arbres et cartes combinatoires aléatoires, PhD thesis. Universit Bordeaux I (1998)
[30] Tutte, W. T., A census of planar maps, Canad. J. Math., 15, 249-271 (1963) · Zbl 0115.17305
[31] Walsh, T. R.S.; Lehman, A. B., Counting rooted maps by genus. I, J. Comb. Theory Ser. B, 13, 192-218 (1972) · Zbl 0228.05108 · doi:10.1016/0095-8956(72)90056-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.