A new combinatorial identity for unicellular maps, via a direct bijective approach

DOI10.1016/J.AAM.2011.04.004zbMATH Open1234.05037arXiv1006.5053OpenAlexW2154871611WikidataQ114214535 ScholiaQ114214535MaRDI QIDQ720600FDOQ720600

Guillaume Chapuy

Publication date: 11 October 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: A unicellular map, or one-face map, is a graph embedded in an orientable surface such that its complement is a topological disk. In this paper, we give a new viewpoint to the structure of these objects, by describing a decomposition of any unicellular map into a unicellular map of smaller genus. This gives a new combinatorial identity for the number $epsilo{n}_g(n)$ of unicellular maps of size $n$ and genus $g$. Contrarily to the Harer-Zagier recurrence formula, this identity is recursive in only one parameter (the genus). Iterating the construction gives an explicit bijection between unicellular maps and plane trees with distinguished vertices, which gives a combinatorial explanation (and proof) of the fact that $epsilo{n}_g(n)$ is the product of the $n$-th Catalan number by a polynomial in $n$. The combinatorial interpretation also gives a new and simple formula for this polynomial. Variants of the problem are considered, like bipartite unicellular maps, or unicellular maps with cubic vertices only.

Full work available at URL: https://arxiv.org/abs/1006.5053

Recommendations

• scientific article; zbMATH DE number 6909270
• A simple model of trees for unicellular maps
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• A simple model of trees for unicellular maps
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees

zbMATH Keywords

bijectionHarer-Zagier numberspolygon gluings

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

Cites Work

• Planar Maps are Well Labeled Trees
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• Graphs on surfaces
• Plane and projective meanders
• Factoring \(n\)-cycles and counting maps of given genus
• The Euler characteristic of the moduli space of curves
• Title not available (Why is that?)
• A bijective proof of Jackson's formula for the number of factorizations of a cycle
• A Bijection for Rooted Maps on Orientable Surfaces
• Counting rooted maps by genus. I
• The asymptotic number of tree-rooted maps on a surface
• An analog of the Harer-Zagier formula for unicellular bicolored maps
• A direct bijection for the Harer-Zagier formula
• A combinatorial proof of the Harer-Zagier formula
• Counting Cycles in Permutations by Group Characters, With an Application to a Topological Problem
• Title not available (Why is that?)
• Counting 1-vertex triangulations of oriented surfaces

Cited In (46)

• Random 2-cell embeddings of multistars
• Combinatorial study of graphs arising from the Sachdev-Ye-Kitaev model
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Random generation and scaling limits of fixed genus factorizations into transpositions
• Calculating the Euler characteristic of the moduli space of curves
• Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
• Generating series of non-oriented constellations and marginal sums in the Matching-Jack conjecture
• Curves on surfaces and surgeries
• Generation of RNA pseudoknot structures with topological genus filtration
• Local limits of uniform triangulations in high genus
• Contribution of \(n\)-cylinder square-tiled surfaces to Masur-Veech volume of \(\mathcal{H}(2g-2)\)
• On RNA-RNA interaction structures of fixed topological genus
• Enumeration of regular maps on surfaces of a given genus
• Planarity and non-separating cycles in uniform high genus quadrangulations
• A new family of bijections for planar maps
• Loop homology of bi-secondary structures
• The Harer-Zagier and Jackson formulas and new results for one-face bipartite maps
• Roaming moduli space using dynamical triangulations
• Moduli spaces and macromolecules
• A topological framework for signed permutations
• A versatile combinatorial approach of studying products of long cycles in symmetric groups
• Hypergraph matrix models and generating functions
• A bijection for tricellular maps
• Statistics of topological RNA structures
• Shapes of topological RNA structures
• A simple model of trees for unicellular maps
• Topological language for RNA
• Virtual Euler characteristics via topological recursion
• Large unicellular maps in high genus
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• A bijection for essentially 4-connected toroidal triangulations
• Classical curves via one-vertex maps
• Combinatorially refine a Zagier-Stanley result on products of permutations
• Title not available (Why is that?)
• Szeged-like entropies of graphs
• Loop homology of bi-secondary structures. II
• A combinatorial way of counting unicellular maps and constellations
• Simple Formulas for Constellations and Bipartite Maps with Prescribed Degrees
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations
• Enumeration of 4-regular one-face maps
• Counting unicellular maps on non-orientable surfaces
• The joint distribution of the marginals of multipartite random quantum states
• Simple maps, Hurwitz numbers, and topological recursion
• Integrality in the matching-Jack conjecture and the Farahat-Higman algebra
• Fatgraph models of RNA structure
• Encoding toroidal triangulations

This page was built for publication: A new combinatorial identity for unicellular maps, via a direct bijective approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q720600)