Paper Info
Title
A bijection for covered maps, or a shortcut between Harer–Zagierʼs and Jacksonʼs formulas
Abstract
We consider maps on orientable surfaces. A map is called unicellular if it has a single face. A covered map is a map (of genus g ) with a marked unicellular spanning submap (which can have any genus in { 0 , 1 , … , g } ). Our main result is a bijection between covered maps with n edges and genus g and pairs made of a plane tree with n edges and a unicellular bipartite map of genus g with n + 1 edges. In the planar case, covered maps are maps with a marked spanning tree and our bijection specializes into a construction obtained by the first author in Bernardi (2007) [4] . Covered maps can also be seen as shuffles of two unicellular maps (one representing the unicellular submap, the other representing the dual unicellular submap). Thus, our bijection gives a correspondence between shuffles of unicellular maps, and pairs made of a plane tree and a unicellular bipartite map. In terms of counting, this establishes the equivalence between a formula due to Harer and Zagier for general unicellular maps, and a formula due to Jackson for bipartite unicellular maps. We also show that the bijection of Bouttier, Di Francesco and Guitter (2004) [8] (which generalizes a previous bijection by Schaeffer, 1998 [33] ) between bipartite maps and so-called well-labeled mobiles can be obtained as a special case of our bijection.
Year
DOI
Venue
2011
10.1016/j.jcta.2011.02.006
Journal of Combinatorial Theory Series A
Keywords
Field
DocType
Unicellular map,Tree-rooted map,Quasi-tree,Graph on orientable surfaces,Spanning submap,Spanning tree
Discrete mathematics,Combinatorics,Bijection,Bipartite graph,Equivalence (measure theory),Spanning tree,Mathematics,Special case
Journal
Volume
Issue
ISSN
118
6
Journal of Combinatorial Theory, Series A
Citations 
PageRank 
References 
4
0.54
13
Authors
2
Name
Order
Citations
PageRank
Olivier Bernardi110614.20
Guillaume Chapuy27311.25