A combinatorial interpretation of the ${\kappa }_g^{\star }(n)$ coefficients

Abstract

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 }_g^{\star }(n)$, which fully determine the series $C_g(z)$. The main result of this paper is a combinatorial interpretation of ${\kappa }_g^{\star }(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é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 }_g^{\star }(n)$, respectively. We then prove a two term recursion for ${\kappa }_g^{\star }(n)$ and that for any fixed $g$, the sequence $\{{\kappa }_{g,t}{\}}_{t=0}^g$ is log-concave, where ${\kappa }_g^{\star }(n)={\kappa }_{g,t}$, for $n=2g+t-1$.

22 pages, 5 figures. arXiv admin note: text overlap with arXiv:1202.3252 by other authors