An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

DOI10.1016/J.AAM.2011.06.005zbMATH Open1233.05090arXiv1011.2311OpenAlexW2075766233MaRDI QIDQ651055FDOQ651055

Authors: Olivier Bernardi 

Publication date: 8 December 2011

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

Abstract: A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with $n$ edges, and with vertices colored using every color in $[q]$ (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces. Our approach is bijective and is inspired by Lass's proof of the Harer-Zagier formula. We first revisit Lass's proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in $[q]$, and maps with vertex set $[q]$ on orientable surfaces emph{with a marked spanning tree}. The bijection immediately implies Harer-Zagier's formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in $[q]$, and maps on orientable surfaces with vertex set $[q]$ emph{with a marked planar submap}. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.

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

Recommendations

• An analog of the Harer-Zagier formula for unicellular bicolored maps
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• A simple model of trees for unicellular maps

zbMATH Keywords

bijectionnon-orientable surfaceone-face mapmoments of the GOE

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• A Census of Planar Maps
• Graphs on surfaces
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• The Euler characteristic of the moduli space of curves
• Some combinatorial problems associated with products of conjugacy classes of the symmetric group
• Title not available (Why is that?)
• A bijective proof of Jackson's formula for the number of factorizations of a cycle
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• Maps in Locally Orientable Surfaces, the Double Coset Algebra, and Zonal Polynomials
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• A recursion formula for the moments of the Gaussian orthogonal ensemble
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• 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 unicellular maps on non-orientable surfaces

Cited In (26)

• 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
• Factorization problems in complex reflection groups
• Bijections and symmetries for the factorizations of the long cycle
• Separation probabilities for products of permutations
• The Harer-Zagier and Jackson formulas and new results for one-face bipartite maps
• A direct bijection for the Harer-Zagier formula
• \(\operatorname{GL}_n(\mathbb{F}_q)\)-analogues of factorization problems in the symmetric group
• Maps of unfixed genus and blossoming trees
• A versatile combinatorial approach of studying products of long cycles in symmetric groups
• Hypergraph matrix models and generating functions
• \(\mathrm{GL}_n(\mathbf{F}_q)\)-analogues of factorization problems in \(\mathfrak{S}_n\)
• A simple model of trees for unicellular maps
• Large unicellular maps in high genus
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• Direct bijective computation of the generating series for 2 and 3-connection coefficients of the symmetric group
• Moments of normally distributed random matrices given by generating series for connection coefficients -- explicit bijective computation
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• Factorization problems in complex reflection groups
• Szeged-like entropies of graphs
• Bijective enumeration of some colored permutations given by the product of two long cycles
• A bijection for rooted maps on general surfaces
• Simple recurrence formulas to count maps on orientable surfaces
• Counting unicellular maps on non-orientable surfaces
• A simple model of trees for unicellular maps
• Combinatorial theory of the semiclassical evaluation of transport moments II: Algorithmic approach for moment generating functions

This page was built for publication: An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

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