Record number :
1531667
Title of article :
A bijection for covered maps, or a shortcut between Harer–Zagierʼs and Jacksonʼs formulas
Author/Authors :
Bernardi، نويسنده , , Olivier and Chapuy، نويسنده , , Guillaume، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
31
From page :
1718
To page :
1748
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]. d 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. o 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.
Keywords :
Unicellular map , spanning tree , Tree-rooted map , Quasi-tree , Graph on orientable surfaces , Spanning submap
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
2011
Link To Document :
بازگشت