Simple recurrence formulas to count maps on orientable surfaces

DOI10.1016/J.JCTA.2015.01.005MaRDI QIDQ2347875zbMATH OpenOpenAlexFDO

Authors S. R. Carrell, Guillaume Chapuy

Publication date 10 June 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

enumerationHarer-Zagier formulaKP hierarchymaps on surfacesquadrangulations

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Abstract: We establish a simple recurrence formula for the number $Q_g^n$ of rooted orientable maps counted by edges and genus. We also give a weighted variant for the generating polynomial $Q_g^n(x)$ where $x$ is a parameter taking the number of faces of the map into account, or equivalently a simple recurrence formula for the refined numbers $M_g^{i,j}$ that count maps by genus, vertices, and faces. These formulas give by far the fastest known way of computing these numbers, or the fixed-genus generating functions, especially for large $g$. In the very particular case of one-face maps, we recover the Harer-Zagier recurrence formula. Our main formula is a consequence of the KP equation for the generating function of bipartite maps, coupled with a Tutte equation, and it was apparently unnoticed before. It is similar in look to the one discovered by Goulden and Jackson for triangulations, and indeed our method to go from the KP equation to the recurrence formula can be seen as a combinatorial simplification of Goulden and Jackson's approach (together with one additional combinatorial trick). All these formulas have a very combinatorial flavour, but finding a bijective interpretation is currently unsolved.

Recommendations

• scientific article; zbMATH DE number 6928902
• Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces
• Enumeration of non-oriented maps via integrability
• Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices
• Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices

Cites work

• A Bijection for Rooted Maps on Orientable Surfaces
• A Census of Planar Maps
• A Character Theoretic Approach to Embeddings of Rooted Maps in an Orientable Surface of Given Genus
• A simple model of trees for unicellular maps
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Asymptotic enumeration of constellations and related families of maps on orientable surfaces
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• scientific article; zbMATH DE number 1399679 (Why is no real title available?)
• Hypergeometric solutions of soliton equations
• Maps, hypermaps and their automorphisms: A survey. I
• Singularity Analysis of Generating Functions
• Symmetric functions, codes of partitions and the KP hierarchy
• The asymptotic number of rooted maps on a surface
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The Euler characteristic of the moduli space of curves
• The KP hierarchy, branched covers, and triangulations
• The map asymptotics constant \(t_{g}\)
• The number of degree restricted maps on general surfaces
• The number of rooted maps on an orientable surface
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• Toda equations for Hurwitz numbers

Cited in

(22)

• Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
• Enumeration of non-oriented maps via integrability
• Planarity and non-separating cycles in uniform high genus quadrangulations
• Szeged-like entropies of graphs
• Local limits of uniform triangulations in high genus
• Simple formulas for constellations and bipartite maps with prescribed degrees
• Virasoro constraints and topological recursion for Grothendieck's dessin counting
• Blossoming bijection for higher-genus maps
• Generating functions of bipartite maps on orientable surfaces
• On a conjecture by Chapuy about Voronoï cells in large maps
• The joint distribution of the marginals of multipartite random quantum states
• scientific article; zbMATH DE number 6928902 (Why is no real title available?)
• scientific article; zbMATH DE number 6806777 (Why is no real title available?)
• Enumeration of hypermaps of a given genus
• Rationality in map and hypermap enumeration by genus
• Simple formulas for constellations and bipartite maps with prescribed degrees
• On tessellations of random maps and the t_g-recurrence
• On tessellations of random maps and the \(t_g\)-recurrence
• Random partitions under the Plancherel-Hurwitz measure, high-genus Hurwitz numbers and maps
• Combinatorial proof for the rationality of the bivariate generating series of maps in positive genus
• Last car decomposition of planar maps
• Generating plane quadrangulations and symmetry-preserving operations on maps

This page was built for publication: Simple recurrence formulas to count maps on orientable surfaces

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