Counting unicellular maps on non-orientable surfaces

DOI10.1016/J.AAM.2010.09.001zbMATH Open1234.05019arXiv1006.5172OpenAlexW2013194786MaRDI QIDQ550259FDOQ550259

Authors: Olivier Bernardi, Guillaume Chapuy 

Publication date: 8 July 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 a topological disk. In this paper we present a bijective link between unicellular maps on a non-orientable surface and unicellular maps of a lower topological type, with distinguished vertices. From that we obtain a recurrence equation that leads to (new) explicit counting formulas for non-orientable unicellular maps of fixed topology. In particular, we give exact formulas for the precubic case (all vertices of degree 1 or 3), and asymptotic formulas for the general case, when the number of edges goes to infinity. Our strategy is inspired by recent results obtained by the second author for the orientable case, but significant novelties are introduced: in particular we construct an involution which, in some sense, "averages" the effects of non-orientability.

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

Recommendations

• scientific article; zbMATH DE number 6806777
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Counting rooted maps on a surface
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• A simple model of trees for unicellular maps

zbMATH Keywords

bijectionHarer-Zagier formulaone-face mapone-vertex triangulation

Mathematics Subject Classification ID

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

Cites Work

• Enumerating simplicial decompositions of surfaces with boundaries
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• Graphs on surfaces
• The Euler characteristic of the moduli space of curves
• Title not available (Why is that?)
• A Bijection for Rooted Maps on Orientable Surfaces
• Maps in Locally Orientable Surfaces, the Double Coset Algebra, and Zonal Polynomials
• Counting rooted maps by genus. I
• A recursion formula for the moments of the Gaussian orthogonal ensemble
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• A direct bijection for the Harer-Zagier formula
• A combinatorial proof of the Harer-Zagier formula

Cited In (15)

• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Calculating the Euler characteristic of the moduli space of curves
• Jungerman ladders and index 2 constructions for genus embeddings of dense regular graphs
• Enumerating simplicial decompositions of surfaces with boundaries
• Combinatorial classification of nonorientable maps
• Enumeration of non-oriented maps via integrability
• A general framework for the polynomiality property of the structure coefficients of double-class algebras
• A topological framework for signed permutations
• A simple model of trees for unicellular maps
• A bijection for nonorientable general maps
• Classes of graphs embeddable in order-dependent surfaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• A bijection for rooted maps on general surfaces
• A combinatorial way of counting unicellular maps and constellations

This page was built for publication: Counting unicellular maps on non-orientable surfaces

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