Combinatorics of Even-Valent Graphs on Riemann Surfaces

Using connections to random matrix theory and orthogonal polynomials, we develop a framework for obtaining explicit closed-form formulae for the number, ${\mathcal{N}}_g(2\nu ,j)$, of connected $2\nu$-valent labeled graphs with $j$ vertices that can be embedded on a compact Riemann surface of minimal genus $g$. We also derive formulae for their two-legged counterparts ${\mathcal{N}}_g(2\nu ,j)$. Our method recovers the known explicit results for graphs embedded on the plane and the torus, and extends them to all genera $g\ge 2$. In earlier work, Ercolani, Lega, and Tippings (2023) showed that ${\mathcal{N}}_g(2\nu ,j)$ and ${\mathcal{N}}_g(2\nu ,j)$ admit structural expressions as linear combinations of, respectively, $3g-2$ and $3g$ Gauss hypergeometric functions ${}_2{F}_1$, but with coefficients left undetermined. The framework developed here provides a systematic procedure to compute these coefficients, thereby turning the structural expressions into fully explicit formulae for ${\mathcal{N}}_g(2\nu ,j)$ and ${\mathcal{N}}_g(2\nu ,j)$ as functions of both $j$ and $\nu$. Detailed results are given for $g=2,3,$ and $4$, and the framework extends naturally to all $g\ge 5$ with increasing computational effort. This closes the fixed genus combinatorics for even-valent graphs.