A new combinatorial identity for unicellular maps, via a direct bijective approach

详细信息    查看全文

• 作者：Guillaume  ; Chapuy¹ ;   ; ^{Guillaume.Chapuy@liafa.jussieu.fr}
• 关键词：Polygon gluings ; Bijection ; Harer&ndash ; Zagier numbers
• 刊名：Advances in Applied Mathematics
• 出版年：2011
• 出版时间：October 2011
• 年：2011
• 卷：47
• 期：4
• 页码：874-893
• 全文大小：411 K

文摘

A unicellular map, or one-face map, is a graph embedded in an orientable surface such that its complement is a topological disk. In this paper, we give a new viewpoint to the structure of these objects, by describing a decomposition of any unicellular map into a unicellular map of smaller genus. This gives a new combinatorial identity for the number of unicellular maps with n edges and genus g. Unlike the Harer¨CZagier recurrence formula, this identity is recursive in only one parameter (the genus).

Iterating the construction gives an explicit bijection between unicellular maps and plane trees with distinguished vertices, which gives a combinatorial explanation (and proof) of the fact that is the product of the n-th Catalan number by a polynomial in n. The combinatorial interpretation also gives a new and simple formula for this polynomial. Variants of the problem are considered, like bipartite unicellular maps, or unicellular maps with only cubic vertices.