A simple model of trees for unicellular maps

Abstract

We consider unicellular maps, or polygon gluings, of fixed genus. A few years ago 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, the Lehman-Walsh formula and the Goupil-Schaeffer formula. We also discuss several applications of our construction: we obtain a new proof of an identity related to covered maps due to Bernardi and the first author, and thanks to previous work of the second author, we give a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group. Finally, we show that our techniques apply partially to unicellular 3-constellations and to related objects that we call quasi-constellations.

v5: minor revision after reviewers comments, 33 pages, added a refinement by degree of the Harer-Zagier formula and more details in some proofs

References in corpus (5)

• A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group
• Separation probabilities for products of permutations
• Explicit monomial expansions of the generating series for connection coefficients
• Counting trees using symmetries
• Stanley's character polynomials and coloured factorizations in the symmetric group

Cited by in corpus (23)

• Combinatorial study of graphs arising from the Sachdev-Ye-Kitaev model
• Colored discrete spaces: higher dimensional combinatorial maps and quantum gravity
• Shifted symmetric functions and multirectangular coordinates of Young diagrams
• The Harer--Zagier recursion for an irregular spectral curve
• GL_n(F_q)-analogues of factorization problems in the symmetric group
• On the joint distribution of the marginals of multipartite random quantum states
• Factorization problems in complex reflection groups
• Planarity and non-separating cycles in uniform high genus quadrangulations
• Simple recurrence formulas to count maps on orientable surfaces
• Simple formulas for constellations and bipartite maps with prescribed degrees
• Reflection length with two parameters in the asymptotic representation theory of type B/C and applications
• Narayana polynomials and some generalizations
• Separation probabilities and analogues of a Zagier-Stanley formula
• Explicit formulas for a family of hypermaps beyond the one-face case
• New formulas counting one-face maps and Chapuy's recursion
• The Wilson loop in the Gaussian Unitary Ensemble
• Generalisations of the Harer-Zagier recursion for 1-point functions
• The local limit of unicellular maps in high genus
• Contribution of $n$-cylinder square-tiled surfaces to Masur-Veech volume of $\mathcal{H}(2g-2)$
• Maps of unfixed genus and blossoming trees
• On products of permutations with the most uncontaminated cycles by designated labels
• From unicellular fatgraphs to trees
• Length spectrum of large genus random metric maps