Universal Asymptotics and Exact Enumeration of Eulerian Maps

Abstract

We calculate the asymptotics of the number of connected, labeled, genus $g$ Eulerian maps with an arbitrary degree sequence, in the limit as the total number of vertices tends to infinity. This asymptotic is universal, in the sense that the leading-order term depends on only three map characteristics, regardless of the choice of the degree sequence. The constant factor in this formula is related to the Painlevé I equation. Our methods combine for the first time the analysis of the recurrence coefficients associated to a particular family of orthogonal polynomials, and the theory of analytic combinatorics of several variables. We also derive an exact formula for the number of connected, labeled, genus $1$ Eulerian maps. These are the first results on this kind of enumeration problem for $g\ge 1$, non-regular (mixed-valence) maps.

Corrected some minor typos, and some slight changes in notation