## Guillaume Chapuy ; Valentin Feray ; Eric Fusy - A simple model of trees for unicellular maps

dmtcs:3033 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) - https://doi.org/10.46298/dmtcs.3033
A simple model of trees for unicellular mapsArticle

Authors: Guillaume Chapuy 1; Valentin Feray 2; Eric Fusy 3

• 1 Laboratoire d'informatique Algorithmique : Fondements et Applications
• 2 Laboratoire Bordelais de Recherche en Informatique
• 3 Laboratoire d'informatique de l'École polytechnique [Palaiseau]

We consider unicellular maps, or polygon gluings, of fixed genus. In FPSAC '09 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, or the Lehman-Walsh/Goupil-Schaeffer formulas. Thanks to previous work of the second author this also leads us to a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group.

Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: one-face map, Stanley character polynomial, bijection, Harer-Zagier formula, Rèmy's bijection.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
Source : OpenAIRE Graph
• Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471