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 ; Valentin Feray ORCID-iD; Eric Fusy

    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]
    Fundings :
      Source : OpenAIRE Research Graph
    • Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471

    Linked data

    Source : ScholeXplorer IsReferencedBy DOI 10.1142/s2010326320500100
    Source : ScholeXplorer IsReferencedBy ARXIV 1808.08554
    Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1808.08554
    • 10.1142/s2010326320500100
    • 10.1142/s2010326320500100
    • 10.1142/s2010326320500100
    • 1808.08554
    • 10.48550/arxiv.1808.08554
    The joint distribution of the marginals of multipartite random quantum states
    Dartois, Stephane ; Lionni, Luca ; Nechita, Ion ;

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 132 times.
    This article's PDF has been downloaded 174 times.