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 maps
Authors: Guillaume Chapuy 1; Valentin Feray 2; Eric Fusy 3
NULL##0000-0002-9060-0696##NULL
Guillaume Chapuy;Valentin Feray;Eric Fusy
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
The Euler characteristic of the moduli space of curves
1 Document citing this article
Source : OpenCitations
Li, Thomas J. X.; Reidys, Christian M., 2013, The Topological Filtration Of -Structures, Mathematical Biosciences, 241, 1, pp. 24-33, 10.1016/j.mbs.2012.09.006.