A simple model of trees for unicellular maps

详细信息    查看全文

• 作者：Guillaume Chapuy ; Valentin F¨¦ray ; ¨¦ric Fusy
• 关键词：One-face map ; Stanley character polynomial ; Bijection ; Harer&ndash ; Zagier formula ; Ré ; my?s bijection
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2013
• 出版时间：November, 2013
• 年：2013
• 卷：120
• 期：8
• 页码：2064-2092
• 全文大小：542 K

文摘

We consider unicellular maps, or polygon gluings, of fixed genus. A few years ago the first author gave a recursive bijection transforming unicellular maps into trees, explaining the presence of Catalan numbers in counting formulas for these objects. In this paper, we give another bijection that explicitly describes the ¡°recursive part¡± of the first bijection. As a result we obtain a very simple description of unicellular maps as pairs made by a plane tree and a permutation-like structure.

All the previously known formulas follow as an immediate corollary or easy exercise, thus giving a bijective proof for each of them, in a unified way. For some of these formulas, this is the first bijective proof, e.g. the Harer-Zagier recurrence formula, the Lehman-Walsh formula and the Goupil-Schaeffer formula. We also discuss several applications of our construction: we obtain a new proof of an identity related to covered maps due to Bernardi and the first author, and thanks to previous work of the second author, we give a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group. Finally, we show that our techniques apply partially to unicellular 3-constellations and to related objects that we call quasi-3-constellations.