Asymptotic enumeration of large genus maps using random walks
We are interested in counting combinatorial maps by size and genus, asymptotically as both the size and the genus go to infinity. We focus on the class of unicellular or one-face maps, which are graphs that are embedded in an orientable surface such that their complement is a topological disc. For these, we prove an asymptotic equivalence valid in the full range $\frac{n-2g}{\log n} \to \infty$ for $n,g \to \infty$. While enumeration in one parameter is a well-studied topic and many powerful methods are available, this problem belongs to the class of bivariate enumeration problems for which very few results exist. Our new method consists of studying a linear recurrence formula for these maps and modeling it by a random walk. We do not use any combinatorics of the model, nor any results on generating functions, but work only with the recurrence. This is joint work with Andrew Elvey Price, Wenjie Fang, and Baptiste Louf.