Counting unicellular maps on non-orientable surfaces

DOI10.1016/J.AAM.2010.09.001MaRDI QIDQ550259zbMATH OpenOpenAlexFDO

Authors Olivier Bernardi, Guillaume Chapuy

Publication date 8 July 2011

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

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

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)

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.

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

Cites work

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

Cited in

(16)

• 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
• A bijection for nonorientable general maps
• Classes of graphs embeddable in order-dependent surfaces
• scientific article; zbMATH DE number 6909270 (Why is no real title available?)
• A bijection for rooted maps on general surfaces
• scientific article; zbMATH DE number 6806777 (Why is no real title available?)
• 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)