A combinatorial interpretation of the $κ^{\star}_{g}(n)$ coefficients

Thomas J. X. Li, Christian M. Reidys

Published 2014-06-12, updated 2014-06-24Version 2

Studying the virtual Euler characteristic of the moduli space of curves, Harer and Zagier compute the generating function $C_g(z)$ of unicellular maps of genus $g$. They furthermore identify coefficients, $\kappa^{\star}_{g}(n)$, which fully determine the series $C_g(z)$. The main result of this paper is a combinatorial interpretation of $\kappa^{\star}_{g}(n)$. We show that these enumerate a class of unicellular maps, which correspond $1$-to-$2^{2g}$ to a specific type of trees, referred to as O-trees. O-trees are a variant of the C-decorated trees introduced by Chapuy, F\'{e}ray and Fusy. We exhaustively enumerate the number $s_{g}(n)$ of shapes of genus $g$ with $n$ edges, which is a specific class of unicellular maps with vertex degree at least three. Furthermore we give combinatorial proofs for expressing the generating functions $C_g(z)$ and $S_g(z)$ for unicellular maps and shapes in terms of $\kappa^{\star}_{g}(n)$, respectively. We then prove a two term recursion for $\kappa^{\star}_{g}(n)$ and that for any fixed $g$, the sequence $\{\kappa_{g,t}\}_{t=0}^g$ is log-concave, where $\kappa^{\star}_{g}(n)= \kappa_{g,t}$, for $n=2g+t-1$.