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 ORCID2; 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

1 Document citing this article

Consultation statistics

This page has been seen 221 times.
This article's PDF has been downloaded 256 times.