Blossoming bijection for higher-genus maps. (English) Zbl 1414.05149
Summary: G. Schaeffer [Electron. J. Comb. 4, No. 1, Research paper R20, 14 p. (1997; Zbl 0885.05076)] described a bijection between Eulerian planar maps and some trees. In this work we generalize his work to a bijection between maps on an orientable surface of any fixed genus and some unicellular maps with the same genus. An important step of this construction is to exhibit a canonical orientation for maps, that allows to apply the same local opening algorithm as Schaeffer [loc. cit.] did.
As an important byproduct, we obtain the first bijective proof of a result of E. A. Bender and E. R. Canfield [J. Comb. Theory, Ser. B 53, No. 2, 293–299 (1991; Zbl 0751.05052)], when they proved that the generating series of maps in higher genus is a rational function of the generating series of planar maps.
As an important byproduct, we obtain the first bijective proof of a result of E. A. Bender and E. R. Canfield [J. Comb. Theory, Ser. B 53, No. 2, 293–299 (1991; Zbl 0751.05052)], when they proved that the generating series of maps in higher genus is a rational function of the generating series of planar maps.
MSC:
| 05C30 | Enumeration in graph theory |
References:
| [1] | Albenque, M.; Poulalhon, D., A generic method for bijections between blossoming trees and planar maps, Electron. J. Combin., 22, 2, Article P2-38, (2015) · Zbl 1327.05028 |
| [2] | Bender, E. A.; Canfield, E. R., The number of rooted maps on an orientable surface, J. Combin. Theory Ser. B, 7, 1, 9-15, (1991) · Zbl 0751.05052 |
| [3] | Bender, A. E.; Canfield, E. R.; Richmond, L. B., The asymptotic number of rooted maps on a surface: II. Enumeration by vertices and faces, J. Combin. Theory Ser. A, 63, 2, 318-329, (1993) · Zbl 0777.05065 |
| [4] | Bender, E. A.; Canfield, E. Rodney; Robinson, R. W., The asymptotic number of tree-rooted maps on a surface, J. Combin. Theory Ser. A, 48, 2, 156-164, (1988) · Zbl 0644.05027 |
| [5] | Bernardi, O., Bijective counting of tree-rooted maps and shuffles of parenthesis systems, Electron. J. Combin., 14, 1 R, 1-36, (2006) · Zbl 1115.05002 |
| [6] | Bernardi, O.; Chapuy, G., A bijection for covered maps, or a shortcut between Harer-Zagier’s and Jackson’s formulas, J. Combin. Theory Ser. A, 118, 6, 1718-1748, (2011) · Zbl 1227.05128 |
| [7] | Bernardi, O.; Fusy, É., A bijection for triangulations, quadrangulations, pentagulations, etc, J. Combin. Theory Ser. A, 119, 1, 218-244, (2012) · Zbl 1232.05019 |
| [8] | Bernardi, O.; Fusy, É., Unified bijections for maps with prescribed degrees and girth, J. Combin. Theory Ser. A, 119, 6, 1351-1387, (2012) · Zbl 1242.05124 |
| [9] | Bettinelli, J., A bijection for nonorientable general maps, (Canada DMTCS Proc. BC, (2016)), 227-238 · Zbl 1440.05115 |
| [10] | Bonichon, N.; Lévêque, B., A bijection for essentially 4-connected toroidal triangulations, Manuscript · Zbl 1409.05107 |
| [11] | 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 |
| [12] | Bouttier, J.; Di Francesco, P.; Guitter, E., Planar maps as labeled mobiles, Electron. J. Combin., 11, 1 R, 1-27, (2004) · Zbl 1060.05045 |
| [13] | Carrell, S. R.; Chapuy, G., Simple recurrence formulas to count maps on orientable surfaces · Zbl 1315.05010 |
| [14] | Chapuy, G., Asymptotic enumeration of constellations and related families of maps on orientable surfaces, Combin. Probab. Comput., 18, 4, 477-516, (2009) · Zbl 1221.05204 |
| [15] | Chapuy, G.; Dołȩga, M., A bijection for rooted maps on general surfaces, J. Combin. Theory Ser. A, 145, 3, 252-307, (2017) · Zbl 1355.05094 |
| [16] | Chapuy, G.; Marcus, M.; Schaeffer, G., A bijection for rooted maps on orientable surfaces, SIAM J. Discrete Math., 23, 3, 1587-1611, (2009) · Zbl 1207.05087 |
| [17] | Cori, R.; Vauquelin, B., Planar maps are well labeled trees, Canad. J. Math., 33, 5, 1023-1042, (1981) · Zbl 0415.05020 |
| [18] | Despré, V.; Gonçalves, D.; Lévêque, B., Encoding toroidal triangulations, Discrete Comput. Geom., 57, 3, 507-544, (2017) · Zbl 1370.68296 |
| [19] | Eynard, B., Counting Surfaces, Progress in Mathematical Physics, vol. 70, (2011), Springer |
| [20] | Felsner, S., Lattice structures from planar graphs, Electron. J. Combin., 11, 1, 15, (2004) · Zbl 1056.05039 |
| [21] | Felsner, S.; Knauer, K. B., ULD-lattices and Δ-bonds, Combin. Probab. Comput., 18, 5, 707-724, (2009) · Zbl 1194.06002 |
| [22] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics, (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 |
| [23] | Gonçalves, D.; Knauer, K.; Lévêque, B., On the structure of Schnyder woods on orientable surfaces · Zbl 1428.05077 |
| [24] | Lando, S. K.; Zvonkin, A. K., Graphs on Surfaces and Their Applications, (2004), Springer, Appendix by Don B. Zagier · Zbl 1040.05001 |
| [25] | Miermont, G., Tessellations of random maps of arbitrary genus, Ann. Sci. Éc. Norm. Supér., 42, 5, 725-781, (2009) · Zbl 1228.05118 |
| [26] | Poulalhon, D.; Schaeffer, G., Optimal coding and sampling of triangulations, Algorithmica, 46, 3-4, 505-527, (2006) · Zbl 1106.68114 |
| [27] | Propp, J., Lattice structure for orientations of graphs, (1993) |
| [28] | Schaeffer, G., Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees, Electron. J. Combin., 4, 1 R, 1-14, (1997) · Zbl 0885.05076 |
| [29] | Schaeffer, G., Conjugaison d’arbres et cartes combinatoires aléatoires, (1998), Université Bordeaux I, Ph.D. thesis |
| [30] | Tutte, W. T., A census of planar maps, Canad. J. Math., 15, i, 249-271, (1963) · Zbl 0115.17305 |
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.
