Geodesic
A simple model of trees for unicellular maps
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2012_special_263_a19,
     author = {Chapuy, Guillaume and Feray, Valentin and Fusy, Eric},
     title = {A simple model of trees for unicellular maps},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)},
     year = {2012},
     doi = {10.46298/dmtcs.3033},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3033/}
}
TY  - JOUR
AU  - Chapuy, Guillaume
AU  - Feray, Valentin
AU  - Fusy, Eric
TI  - A simple model of trees for unicellular maps
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3033/
DO  - 10.46298/dmtcs.3033
LA  - en
ID  - DMTCS_2012_special_263_a19
ER  - 
%0 Journal Article
%A Chapuy, Guillaume
%A Feray, Valentin
%A Fusy, Eric
%T A simple model of trees for unicellular maps
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3033/
%R 10.46298/dmtcs.3033
%G en
%F DMTCS_2012_special_263_a19
Chapuy, Guillaume; Feray, Valentin; Fusy, Eric. A simple model of trees for unicellular maps. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012). doi : 10.46298/dmtcs.3033. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3033/

Cité par Sources :