# Generating functions of bipartite maps on orientable surfaces (extended abstract)

Guillaume Chapuy, Wenjie Fang

► To cite this version:

Guillaume Chapuy, Wenjie Fang. Generating functions of bipartite maps on orientable surfaces (extended abstract). 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.607-618, 10.46298/dmtcs.2531. hal-01337789

HAL Id: hal-01337789

https://hal.science/hal-01337789

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Generating functions of bipartite maps on
orientable surfaces (extended abstract)

Guillaume Chapuy and Wenjie Fang†

LIAFA, UMR CNRS 7089, Université Paris-Diderot, Paris Cedex 13, France.

**Abstract.** We compute, for each genus $g \ge 0$, the generating function $L_g \equiv L_g(t; p_1, p_2, \dots)$ of (labelled) bipartite maps on the orientable surface of genus $g$, with control on all face degrees. We exhibit an explicit change of variables such that for each $g$, $L_g$ is a rational function in the new variables, computable by an explicit recursion on the genus. The same holds for the generating function $F_g$ of *rooted* bipartite maps. The form of the result is strikingly similar to the Goulden/Jackson/Vakil and Goulden/Guay-Paquet/Novak formulas for the generating functions of classical and monotone Hurwitz numbers respectively, which suggests stronger links between these models. Our result strengthens recent results of Kazarian and Zograf, who studied the case where the number of faces is bounded, in the equivalent formalism of *dessins d'enfants*. Our proofs borrow some ideas from Eynard's "topological recursion" that he applied in particular to even-faced maps (unconventionally called "bipartite maps" in his work). However, the present paper requires no previous knowledge of this topic and comes with elementary (complex-analysis-free) proofs written in the perspective of formal power series.

**Résumé.** Nous calculons, pour chaque genre $g \ge 0$, la série génératrice $L_g \equiv L_g(t; p_1, p_2, \dots)$ des cartes bipartites (étiquetées) sur la surface orientable de genre $g$, avec contrôle des degrés des faces. On exhibe un changement de variable explicite tel que pour tout $g$, $L_g$ est une fonction rationnelle des nouvelles variables, calculable par une récurrence explicite sur le genre. La même chose est vraie de la série génératrice $L_g$ des cartes biparties *enracinées*. La forme du résultat est similaire aux formules de Goulden/Jackson/Vakil et Goulden/Guay-Paquet/Novak pour les séries génératrices de nombres de Hurwitz classiques et monotones, respectivement, ce qui suggère des liens plus forts entre ces modèles. Notre résultat renforce des résultats récents de Kazarian et Zograf, qui étudient le cas où le nombre de faces est borné, dans le formalisme équivalent des *dessins d'enfants*. Nos démonstrations utilisent deux idées de la "récurrence topologique" d'Eynard, qu'il a appliquée notamment aux cartes paires (appelées de manière non-standard "cartes biparties" dans son travail). Cela dit, ce papier ne requiert pas de connaissance préliminaire sur ce sujet, et nos démonstrations (sans analyse complexe) sont écrites dans le language des séries formelles.

**Keywords:** Enumeration, Maps on surfaces, Topological recursion

**Note:** This paper is an extended abstract of [CF15], to which we refer for full proofs of the results.

<footnote>†Both authors acknowledge partial support from Agence Nationale de la Recherche, grant number ANR 12-JS02-001-01 "Car-taplus", and from the City of Paris, grant "Émergences Paris 2013, Combinatoire à Paris". G.C. is currently visiting McGill University, School of Computer Science, Montréal, Canada, and acknowledges partial support (and hospitality!) from Luc Devroye. W.F. acknowledges hospitality from LaBRI, UMR CNRS 5800, Université de Bordeaux, France. Emails: {Guillaume.Chapuy, Wenjie.Fang}@liafa.univ-paris-diderot.fr.</footnote>
# 1 Introduction

A map of genus $g \ge 0$ is a graph embedded into the $g$-torus (the sphere with $g$ handles attached), in such a way that the connected components of the complement of the graph are simply connected. See Section 2.1 for complete definitions. The enumeration of maps is a classical topic in combinatorics, motivated both from the beautiful enumerative questions it unveils, and by its many connections with other areas of mathematics, see e.g. [LZ04]. The enumeration of planar maps (when the underlying surface is the sphere) was initiated by Tutte who showed [Tut63] that the generating function $Q_0(t)$ of rooted planar maps by the number of edges is an algebraic function given by:

$$Q_0(t) = s(4-s)/3, \text{ where } s = 1 + 3ts^2. \qquad (1)$$

The enumeration of planar maps has since grown into an enormous field of research on its own, out of the scope of this introduction, and we refer to [Sch] for an introduction and references.

The enumeration of maps on surfaces different from the sphere was pioneered by Bender and Canfield, who showed [BC91] that for each $g \ge 1$, the generating function $Q_g(t)$ of rooted maps embedded on the $g$-torus (see again Section 2.1 for definitions) is a rational function of the parameter $s$ defined in (1). For example, for the torus, one has $Q_1(t) = \frac{1}{3} \frac{s(s-1)^2}{(s+2)(s-2)^2}$. This deep and important result was the first of a series of rationality results established for generating functions of maps or related combinatorial objects on higher genus surfaces. Gao [Gao93] proved several rationality results for the generating functions of maps with prescribed degrees using a variant of the kernel method (see Remark 1 for a comment about this). Later, Goulden, Jackson and Vakil [GJV01] proved a rationality statement for the generating functions of Hurwitz numbers via deep algebraic methods. More recently, Goulden, Guay-Paquet, and Novak [GGPN13] introduced a variant called monotone Hurwitz numbers, for which they proved a rationality statement very similar to the one of [GJV01]. We invite the reader to compare our main result (Theorem 1) with [GJV01, Thm. 3.2] and [GGPN13, Thm. 1.4] (see also [GGPN13, Sec. 1.5]). The analogy between those results is striking and worth further investigation.

In parallel to this story, mathematical physicists have developed various tools to attack problems in map enumeration, motivated by their many connections with high energy physics, and notably matrix integrals (see e.g. [LZ04, Chapter 5] and [Eyn11]). Among them, the topological recursion is a general framework pioneered by [ACM92] and developed by Eynard and his school [Eyn, EO09] that solves many models related to map enumeration and algebraic geometry in a universal way. In [Eyn, Chap. 3 Sec. 4.5], this technique is applied to the enumeration of maps on surfaces, and in particular a rationality theorem is obtained for generating functions of maps with faces of even degrees (unconventionally called “bipartite” maps in [Eyn], although they are not bipartite in the graph-theoretic sense). The proofs in these references use a complex-analytic viewpoint, and are often not easy to read for the pure combinatorialist.

The purpose of the present paper is to establish a rationality theorem for bipartite maps, which is a very natural and widely considered model of maps from both the topological and combinatorial viewpoint, see Section 2.1. Our proof recycles two ideas of the topological recursion, however previous knowledge of the latter is not required, and our proofs rely only on a concrete viewpoint on Tutte equations and on formal power series. To be precise, the two crucial steps that are directly inspired from the topological recursion, and that differ from traditional kernel-like methods often used by combinatorialists are Proposition 4 and Theorem 4. Once these two results are proved (with a formal series viewpoint), an important part of the work deals with making explicit the auxiliary variables that underlie the rationality statements (the “Greek” variables in Theorem 1 below). This requires a rather long work, much of which is omitted in
this abstract. Finally, the “integration step” needed to prove our statement in the labelled case (Theorem 1)
from the rooted case (Theorem 3) is an *ad hoc* proof, partly relying on a bijective insight from [Cha09],
and is only very briefly sketched in Section 4.

Bipartite maps have been considered before in the literature. The first author studied them by *bijective* methods [Cha09], and obtained rationality statements that are weaker than the ones we obtain here (since [Cha09] deals only with a finite set of allowed face degrees, and uses a change of variables that depends on this set). More recently, Kazarian and Zograf [KZ14], using a variant of the topological recursion, proved a *polynomiality statement* for the generating functions of bipartite maps with *finitely many* faces (these authors deal with *dessins d'enfant* rather than bipartite maps, but the two models are equivalent, see [LZ04, Chap. 1]). On the contrary our main result covers the case of arbitrarily many faces, which is much more general. Indeed, not only does it prove that the generating function for *dessins d'enfant* with a fixed number of faces is a polynomial in our chosen set of parameters (by a simple derivation), but it also gives a very strong information on the mutual dependency of these different generating functions.

This paper is organized as follows. In Section 2, we give necessary definitions and notation, and we state the main results (Theorems 1 and 3). In Section 3 we write the Tutte/loop equation, and we describe the general program to prove the main result in the rooted case, leaving some technical proofs and many calculations to the full version [CF15]. Section 4 contains a very quick sketch of the proof of the result in the unrooted labelled case, mostly reported to [CF15], together with some comments.

**Acknowledgements:** Both authors thank Mireille Bousquet-Mélou for interesting discussions and for reading a first draft of this paper.

**On omitted proofs:** All the results stated in this document have full proofs in [CF15]. If a result cited in this extended abstract is not followed by a proof, this implicitly refers to [CF15].

2 Surfaces, maps, and the main results

2.1 *Surfaces, maps*

In this paper, a *surface* is a connected, compact, oriented 2-manifold without boundary, considered up to
oriented homeomorphism. For each integer $g \ge 0$, let $S_g$ be the *g-torus* that is obtained from the 2-sphere
$S_0$ by adding $g$ handles. Hence $S_1$ is the torus, $S_2$ is the double torus, etc. By the theorem of classification,
each surface is homeomorphic to one of the surfaces $S_g$ for some $g \ge 0$ called its *genus*.

A *map* is a graph *G* (with loops and multiple edges allowed) properly embedded into a surface *S*, in such a way that the connected components of *S* \ *G*, called *faces*, are topological disks. The *genus* of a map is the genus of the underlying surface. A map is *rooted* if an edge (called the *root edge*) is distinguished and oriented. The origin of the root edge is the *root vertex*, and the face incident to the right of the (oriented) root edge is the *root face*. A rooted map is *bipartite* if its vertices are coloured in black and white without monochromatic edge and with the root vertex coloured white. Note that a bipartite map may have multiple edges but no loops. We consider rooted maps up to oriented homeomorphisms preserving the oriented root edge. The *degree* of a vertex in a bipartite map is its degree in the underlying multigraph, i.e. the number of edges incident to it, with multiplicity. The *degree* of a face in a bipartite map is the number of edges bounding this face, counted with multiplicity. Because colors alternate along an edge, the degree of faces in a bipartite maps are even<sup>(i)</sup>. If a bipartite map has *n* edges, all its face-degrees sums to 2*n*.

<footnote>(i) Note, however that the converse is true only for genus 0: for each genus $g \ge 1$, there exist maps with all faces of even degree but not bipartite (in genus 1, and example is the $m \times n$ square grid with toroidal identifications, when $m$ or $n$ is odd).</footnote>
From the algebraic viewpoint (and for the comparison with Hurwitz numbers as defined in [GJV01, GGPN13]), it is sometimes convenient to consider a variant of rooted maps called labelled maps, which can be seen as an unrooted version of bipartite maps. A labelled bipartite map of size $n$ is a bipartite map with $n$ edges equipped with a labelling of its edges from 1 to $n$ such that its root edge receives label 1. Clearly, there is a 1-to-$(n-1)!$ correspondence between rooted bipartite maps and labelled bipartite maps of size $n$. Given a labelled bipartite map, one can define two permutations $\sigma_\circ$ and $\sigma_\bullet$ in $\mathfrak{S}_n$ whose cycles record the counter-clockwise ordering of edges around white and black vertices, respectively. This is a bijection between labelled bipartite maps of size $n$ and pairs $(\sigma_\circ, \sigma_\bullet)$ of permutations in $\mathfrak{S}_n$ such that the subgroup $\langle \sigma_\circ, \sigma_\bullet \rangle \subset \mathfrak{S}_n$ acts transitively on $[1 \dots n]$. In this correspondence, cycles of $\sigma_\circ, \sigma_\bullet$, and $\sigma_\circ \sigma_\bullet$ are in natural correspondence with white vertices, black vertices, and faces, and the lengths of these cycles correspond to degrees (for vertices) and half-degrees (for faces). The genus $g$ of the underlying surface is related to the number of cycles of the three permutations $\sigma_\circ, \sigma_\bullet$ and $\sigma_\circ \sigma_\bullet$ by Euler's formula:

$$ \ell(\sigma_\circ) + \ell(\sigma_\bullet) + \ell(\sigma_\circ \sigma_\bullet) = n + 2 - 2g. $$

## 2.2 Notation for series and changes of variables

In this paper, $t$, $x$, and $p_1, p_2, \dots$ are indeterminates. Indices of the variables $(p_i)_{i \ge 1}$ will be extended multiplicatively from integers to integer partitions, for example $p_{3,3,1} = p_1(p_3)^2$, and the same convention will be used for other indexed sequences of variables in the paper, such as $(\eta_i)_{i \ge 1}$ or $(\zeta_i)_{i \ge 1}$.

If $\mathbb{B}$ is a ring (or field) and $s$ an indeterminate, we denote by $\mathbb{B}[s]$, $\mathbb{B}(s)$, $\mathbb{B}[[s]]$, $\mathbb{B}((s))$, $\mathbb{B}((s^*))$ the ring (or field) of polynomials, rational functions, formal power series (f.p.s.), formal Laurent series, and Puiseux series in $s$ with coefficients in $\mathbb{B}$, respectively. If $\mathbb{B}$ is a field, $\mathbb{B}$ is its algebraic closure. We will often omit the dependency of generating functions on the variables in the notation, for example we will write $L_g$ for $L_g(t; p_1, p_2, \dots)$ and $F_g$ for $F_g(t; x; p_1, p_2, \dots)$. In this paper all fields have characteristic 0.

Finally, an important role will be played by the “change of variables” $(t, x) \leftrightarrow (z, u)$ given by Equations (2) and (4) below. These equations define two unique f.p.s. $z \equiv z(t) \in \mathbb{Q}[p_1, p_2, \dots][[t]]$ and $u \equiv u(t, x) \in \mathbb{Q}[x, p_1, p_2, \dots][[t]]$. Moreover, this change of variables is reversible, via $t(z) = \frac{z}{1+\sum_k (\frac{2k-1}{k})p_k z^k}$ and $x(z, u) = \frac{u}{(1+zu)^2}$. Note also that, if $H \equiv H(t, x) \in \mathbb{B}[x][[t]]$ is a f.p.s. in $t$ with polynomial coefficients in $x$ over some ring $\mathbb{B}$ containing all $p_i$, then $H(t(z), x(z, u))$ is an element of $\mathbb{B}[u][[z]]$. In this paper we abuse notations and switch without warning between a series $H \in \mathbb{B}[x][[t]]$ and its image in $\mathbb{B}[u][[z]]$ via the change of variables. We are going to use the single letter $H$ for both objects, relying on the context that should prevent any misunderstanding.

## 2.3 Main results

For $n \ge 1$ and $\mu$ a partition of $n$ (denoted as $\mu \vdash n$), let $l_g(\mu)$ be the number of labelled bipartite maps of size $n$ and genus $g \ge 0$ whose half-degrees of faces are given by the parts of $\mu$. Equivalently:

$$ l_g(\mu) := \# \left\{ \begin{array}{l} (\sigma_\circ, \sigma_\bullet) \in (\mathfrak{S}_n)^2 \ ; \ \ell(\sigma_\circ) + \ell(\sigma_\bullet) + \ell(\sigma_\circ \sigma_\bullet) = n + 2 - 2g \ ; \\ \langle \sigma_\circ, \sigma_\bullet \rangle \text{ is transitive} \ ; \ \sigma_\circ \sigma_\bullet \text{ has cycle type } \mu. \end{array} \right\}. $$

We now form the exponential generating function of these numbers, where $t$ marks the number of edges, which is also the size, and for $i \ge 1$, the variable $p_i$ marks the number of faces of degree $2i$:

$$ L_g \equiv L_g(t; p_1, p_2, \dots) := \mathbf{1}_{g=0} + \sum_{n \ge 1} \frac{t^n}{n!} \sum_{\mu \vdash n} l_g(\mu) p_\mu, $$
where the indicator function accounts for the special case of the unique map of genus 0 with 1 vertex and 0 edge. Similarly, for $k \ge 1$ and $\mu \vdash n - k$, we let $b_g(k; \mu)$ be the number of rooted bipartite maps of genus $g$ with $n$ edges, such that the root face has half-degree $k$, and the half-degrees of non-root faces are given by the parts of $\mu$. We let $F_g \equiv F_g(t; x; p_1, p_2, \dots)$ be the corresponding ordinary generating function:

$$F_g \equiv F_g(t; x; p_1, p_2, \dots) := \mathbf{1}_{g=0} + \sum_{n \ge 1} t^n \sum_{\substack{k \ge 1 \\ \mu \vdash n - k}} b_g(k, \mu) x^k p_\mu.$$

**Theorem 1 (Main result – unrooted case ($g \ge 2$))** Let $z \equiv z(t)$ be the unique formal power series that verifies the following equation

$$z = t \left( 1 + \sum_{k \ge 1} \binom{2k-1}{k} p_k z^k \right). \qquad (2)$$

Define moreover $\gamma$, $\eta$ and $\zeta$ as the following formal power series:

$$\gamma := \sum_{k \ge 1} \binom{2k-1}{k} p_k z^k, \quad \eta := \sum_{k \ge 1} (k-1) \binom{2k-1}{k} p_k z^k, \quad \zeta := \sum_{k \ge 1} \frac{k-1}{2k-1} \binom{2k-1}{k} p_k z^k,$$

and $(\eta_i)_{i \ge 1}$ and $(\zeta_i)_{i \ge 1}$ by

$$\eta_i := \sum_{k \ge 1} (k-1)k^i \binom{2k-1}{k} p_k z^k, \quad \zeta_i := \sum_{k \ge 1} \frac{4k(-1)^i(2i-1)!!(2k-2i-3)!!}{(2k-1)!!} \binom{2k-1}{k} p_k z^k.$$

Then for $g \ge 2$, the exponential generating function $L_g$ of labelled bipartite maps of genus $g$ is equal to

$$L_g = \sum_{\alpha, \beta, a \ge 0, b \ge 0, d \ge 0} c_{a,b}^{\alpha, \beta, d} \frac{\eta_{\alpha} \zeta_{\beta} (1+\gamma)^d}{(1-\eta)^a (1+\zeta)^b}, \qquad (3)$$

for rational numbers $c_{a,b}^{\alpha, \beta, d}$ where $\alpha, \beta$ are integer partitions, and $c_{a,b}^{\alpha, \beta, d} \ne 0$ implies $|\alpha| + |\beta| + d/2 \le 3g$ and $a + b = d + \ell(\alpha) + \ell(\beta) + 2g - 2$. The sum above is finite.

**Example 1 (Unrooted generating function for genus 2)**

$$L_2 = \frac{1}{120} - \frac{1}{23040} \frac{\eta_1 (185\eta_1 - 58\eta_2)}{(1-\eta)^4} - \frac{1}{46080} \frac{20\eta_3 - 168\eta_2 + 415\eta_1}{(1-\eta)^3} - \frac{53/15360}{(1-\eta)^2} - \frac{7}{2880} \frac{\eta_1^3}{(1-\eta)^5} - \frac{1/512}{(1-\eta)(1+\zeta)} + \frac{\eta_1/1536}{(1-\eta)^2(1+\zeta)} - \frac{3}{2048} \frac{1}{(1+\zeta)^2} - \frac{3}{8192} \frac{4\gamma - \zeta_1 + 4}{(1+\zeta)^3}.$$

The case of genus 1 is stated separately since it involves logarithms.

**Theorem 2 (Unrooted case for genus 1)** The exponential generating function $L_1 \equiv L_1(t; p_1, p_2, \dots)$ of bipartite maps on the torus is given by the following expression, with the notation of Theorem 1:

$$L_1 = \frac{1}{24} \ln \frac{1}{1-\eta} + \frac{1}{8} \ln \frac{1}{1+\zeta},$$
In order to establish Theorem 1 we will first prove its (slightly weaker) rooted counterpart.

**Theorem 3 (Main result – rooted case)** Let $z \equiv z(t)$ and the variables $\gamma, \eta, \zeta$ and $(\eta_i)_{i \ge 1}$ and $(\zeta_i)_{i \ge 1}$ be defined as in Theorem 1. Let $u \equiv u(t, x)$ be the formal power series defined by

$$u = x(1 + zu)^2. \qquad (4)$$

Then for all $g \ge 1$, the generating function $F_g \equiv F_g(t; x; p_1, p_2, \dots)$ of rooted bipartite maps of genus $g$ is equal to

$$F_g = \sum_{c=1}^{6g-1} \sum_{\alpha, \beta, a \ge 0, b \ge 0, d \ge 0} \frac{\eta_\alpha \zeta_\beta (1+\gamma)^d}{(1-\eta)^a (1+\zeta)^b} \left( \frac{d_{a,b,c,+}^{\alpha,\beta,d}}{(1-uz)^c} + \frac{d_{a,b,c,-}^{\alpha,\beta,d}}{(1+uz)^c} \right), \qquad (5)$$

for $d_{a,b,c,\pm}^{\alpha,\beta,d} \in \mathbb{Q}$, with the same notation as in Theorem 1. Furthermore, $d_{a,b,c,\pm}^{\alpha,\beta,d} \ne 0$ implies $(2 \pm 1)g \ge \lceil \frac{1+c}{2} \rceil + |\alpha| + |\beta| + d/2$ and $a+b = d+\ell(\alpha) + \ell(\beta) + 2g-1$ for both signs, and the sum above is finite.

**Comments:**

* The “Greek variables” $\gamma, \eta, \zeta, \eta_i, \zeta_i$ are all infinite linear combinations of the $p_k z^k$ with explicit coefficients. Moreover, for fixed $g$ the sums (3), (5) depend only on finitely many Greek variables, see e.g. Example 1. Note also that if only finitely many $p_i$'s are non-zero, then all the Greek letters are polynomials depending uniquely on variable $z$. For example, if $p_i = 1_{i=2}$, i.e. if we enumerate bipartite quadrangulations, all Greek variables are polynomials in the variable $s$ (= $z+1$) defined in Equation (1). In particular, and since bipartite quadrangulations are in bijection with general rooted maps (see e.g. [Sch]), the rationality results of [BC91] are a (very) special case of our results.

* Readers familiar with the bijective techniques of map enumeration will notice that the change of variables $(t, x) \leftrightarrow (z, u)$ is very natural in view of the link between bipartite maps and mobiles [Cha09] (and indeed the transformation $t \leftrightarrow z$ already appears in [BDFG04]). However, those bijections are still far for giving combinatorial proofs of Theorems 1 and 3.

* The case of genus 0 is not covered by the theorems above but is well known, and we will use it thoroughly. See (7) page 613 below.

# 3 The Tutte equation, and the proof strategy of Theorem 3

## 3.1 The Tutte equation

In this section, we state the main Tutte/loop equation that is the starting point of our proofs. We first define some useful operators. The *rooting operator* $\Gamma$ is defined by $\Gamma := \sum_{k \ge 1} kx^k \frac{\partial}{\partial p_k}$. Combinatorially, the effect of $\Gamma$ is to mark a face of degree $2k$, distinguish one of its $k$ white corners, and record the size of this face using the variable $x$. In other words, $\Gamma$ is the operator that selects a root face in a map. From the discussion of Section 2.1, it is easy to see that $F_g = \Gamma L_g$, and with some computations we can prove that Theorem 1 implies Theorem 3, which means that the latter is indeed weaker.

If $F \equiv F(x)$ is a f.p.s whose coefficients are polynomials in $x$ (over some ring), we let $\Delta F(x) = \frac{F(x)-F(0)}{x}$. We define the operator: $\Omega := \sum_{k \ge 1} p_k \Delta^k = [x^{\ge 0}] \sum_{k \ge 1} \frac{p_k}{x^k}$, where $[x^{\ge 0}]$ is the operator that takes only non-negative powers of $x$ in a Laurent series in $x$.
**Proposition 1 (Tutte equation)** The sequence $(F_g)_{g \ge 0}$ of formal power series in $\mathbb{Q}[p_1, p_2, \dots][x][\lfloor t \rfloor]$ is uniquely determined by the equations, for $g \ge 0$:

$$F_g = \mathbf{1}_{g=0} + xt\Omega F_g + xtF_{g-1}^{(2)} + xt \sum_{\substack{g_1+g_2=g \\ g_1, g_2 \ge 0}} F_{g_1}F_{g_2}, \qquad (6)$$

where $F_{g-1}^{(2)} := \Gamma F_{g-1}$ is the g.f. of bipartite maps of genus g with two root faces.

In genus 0, this equation was solved by Bender and Canfield [BC94] who gave the following remarkable expression in terms of the variables $z \equiv z(t)$, $u \equiv u(t; x)$ defined in Theorems 1 and 3:

$$F_0 = 1 + uz - uz(1 + uz) \sum_{k \ge 1} p_k z^k \sum_{\ell=0}^{k-2} \binom{2k-1}{k+\ell+1} u^\ell z^\ell. \qquad (7)$$

The strategy of our proof of Theorem 3 is to solve (6) recursively on the genus g: indeed, for $g \ge 1$, assuming that all the series $F_h$, $F_h^{(2)}$ are known for $h < g$, we see (6) as a linear “catalytic” equation for the unknown series $F_g$ with one “catalytic” (i.e. auxiliary) variable. Therefore it is tempting to solve it via the kernel method or one of its variants.

In what follows, in order to make the induction step feasible, we will need to fix an arbitrary integer $K \ge 2$, and to make the substitution $p_i = 0$ for $i > K$ in (6). The integer K will be sent to infinity at the end of the induction step. To prevent a possible misunderstanding, we warn the reader that the substitution of $p_i$ to zero does not commute with $\Gamma$, and in particular:

$$F_g^{(2)}|_{p_i=0} = (\Gamma F_g)|_{p_i=0} \neq \Gamma (F_g)|_{p_i=0}.$$

In concrete terms, even after we set the variables $p_i$ to zero for all $i > K$, the series $F_g^{(2)}$ still counts maps in which the two root faces may have arbitrarily large degrees. We now proceed with the inductive part of the proof, that will occupy the rest of this section. The base case $g = 1$ of the induction will be proved separately. To formulate our induction hypothesis, we need the following notion: if $A(u)$ is a rational function over some field containing $z$, we say that $A$ is *uz-symmetric* if $A(z^{-2}u^{-1}) = A(u)$, and *uz-antisymmetric* if $A(z^{-2}u^{-1}) = -A(u)$.

**Induction Hypothesis:** In the rest of Section 3, we fix $g \ge 1$. We assume that for all genera $g' \in [1..g-1]$, Theorem 3 holds for genus $g'$. In particular $F_{g'}$ is a rational function of $u$. Moreover, we assume that $F_{g'}$ is *uz-antisymmetric*.

We now start examining the induction step. **From now on, we assume that $p_i = 0$ for $i > K$.** In other words, each series mentioned below is considered under the substitution $\{p_i = 0, i > K\}$, even if the notation does not make it apparent. Our first observation is the following:

**Proposition 2 (Kernel form of the Tutte equation)** Let $Y := 1 - 2txF_0 - tx \sum_{k=1}^{K} \frac{p_k}{x^k}$. Then one has:

$$YF_g = xtF_{g-1}^{(2)} + xt \sum_{\substack{g_1+g_2=g \\ g_1, g_2 > 0}} F_{g_1}F_{g_2} + xtS, \qquad (8)$$

where $S \equiv S(t, p_1, p_2, \dots; x)$ is an element of $\mathbb{Q}[p_1, p_2, \dots][\lfloor t \rfloor] [\frac{1}{x}]$ of degree at most $K-1$ in $\frac{1}{x}$ without constant term.
## 3.2 Rational structure of $F_g$ and the topological recursion

To prove Proposition 2, it is natural to study the properties of the “kernel” $Y$. In what follows, we will consider elements in $A[z][u]$ or $A[[z]][u]$ where $A := Q(p_1, p_2, \dots, p_K)$. Note that any such element, viewed as a polynomial in $u$, is split over $\mathbb{P} := \mathbb{A}((z^*))$. An element $u_0 \in \mathbb{P}$ is large if it starts with a negative power in $z$, and is small otherwise. The following can be proved from (7) and a meticulous analysis of the expression of $Y$. As explained in Section 2.2, all following generating functions are considered under the change of variables $(t, x) \leftrightarrow (z, u)$:

**Proposition 3 (Structure of the kernel)** The series $Y$ is an element of $Q(z, u, p_1, p_2, \dots, p_K)$ of the form:

$$Y = \frac{N(u)(1 - uz)}{u^{K-1}(1 + \gamma)(1 + uz)}$$

where $N(u) \in A[z][u]$ is a polynomial of degree $2(K-1)$ in $u$. Moreover, $Y$ is uz-antisymmetric, and among the $2(K-1)$ zeros of $N(u)$ in $\mathbb{P}$, $(K-1)$ of them are small and $(K-1)$ are large. Large and small zeros are exchanged by the transformation $u \leftrightarrow \frac{1}{z^2 u}$.

Before solving (6), we need to examine closely the structure of $F_g$. In what follows, each $R(u) \in \mathbb{B}(u)$ for some field $\mathbb{B}$ is implicitly considered as an element of $\mathbb{B}(u)$. In particular, its denominator is split, and the notion of pole is well defined (poles are elements of $\mathbb{B}$). Moreover, $R(u)$ has a partial fraction expansion with coefficients in $\mathbb{B}$, and its residue at a pole $u_* \in \mathbb{B}$ is defined as the coefficient of $(u-u_*)^{-1}$ in the expansion. We define the degree of $R(u)$ as the difference of degree between its numerator and its denominator. The following result is perhaps the most crucial conceptual step of the proof of Theorem 3.

**Proposition 4 (Structure and poles of $F_g$)** For $g \ge 1$, the series $F_g$ is an uz-antisymmetric element of $A[[z]](u)$. Its poles, as elements of $\mathbb{P}$, are contained in $\{\frac{1}{z}, -\frac{1}{z}\}$. Moreover, $F_g$ has negative degree in $u$.

The proof of Proposition 4 uses the next two lemmas (the first follows from rather long computations).

**Lemma 1** If $A$ is an element of $Q(u, z, \gamma, \eta, \zeta, (\eta_i)_{i \ge 1}, (\zeta_i)_{i \ge 1})$ involving finitely many variables with negative degree in $u$ whose poles in $u$ are among $\{\pm \frac{1}{z}\}$, then so is $\Gamma A(u)$. Moreover, if $A(u)$ is uz-antisymmetric, then $\Gamma A(x)$ is uz-symmetric.

**Lemma 2** Let $A(u) \in \mathbb{B}[[z]](u) \cap \mathbb{B}[u]((z)) \subset \mathbb{B}(u)((z))$. Then when seen as a rational function in $u$, $A(u)$ has no small pole.

**Proof:** By the Newton-Puiseux theorem, we can write $A(u) = \frac{P(u)}{c \cdot Q_1(u) Q_2(u)}$ with $P(u) \in \mathbb{B}[[z]][u]$, $c \in \mathbb{B}((z^*))$, $Q_1(u) = \prod_i (1 - uu_i)$ and $Q_2(u) = \prod_j (u - v_j)$, where the $u_i, v_j$ are small Puiseux series over an algebraic closure $\mathbb{B}$ of $\mathbb{B}$ and $v_j$ without constant term. Since $P(u)/Q_2(u) = cA(u)Q_1(u)$, and since $\mathbb{B}[u]((z^*))$ is a ring, we see that $P(u)/Q_2(u) \in \mathbb{B}[u]((z^*))$. But since $1/Q_2(u) = \prod_j \sum_{k \ge 0} u^{-1-k} v_i^k$ is in $\mathbb{B}[u^{-1}]((z^*))$, this is impossible unless $Q_2$ divides $P$ in $\mathbb{B}((z^*))$[u], which concludes the proof. $\square$

**Proof of Proposition 4:** The base case of induction $g = 1$ is proved with an explicit resolution of Equation (10), see [CF15]. We will now prove the induction step.

First, the R.H.S. of (8) is uz-symmetric: indeed by induction each term $F_{g_1}F_{g_2}$ is uz-symmetric as a product of two uz-antisymmetric factors, the term $F_{g_1}^{(2)}$ is uz-symmetric by Lemma 1, and $S$, as any
rational fraction in $x$, is symmetric since $x(u) = \frac{u}{(1+zu)^2}$ is symmetric. Hence by Proposition 3, $F_g$ is $uz$-antisymmetric, being the quotient of the $uz$-symmetric right-hand side by $Y$.

Now, by the induction hypothesis and Lemma 1, the R.H.S. of (8) is in $\mathbb{A}[[z]](u)$, and its poles are contained in $\{\pm\frac{1}{z}, 0\}$. Hence solving (8) for $F_g$ and using Proposition 3, we deduce that $F_g$ belongs to $\mathbb{A}[[z]](u)$ and that its only possible poles are $\pm\frac{1}{z}, 0$ and the zeros of $N(u)$.

Now, viewed as a series in $z$, $F_g$ is an element of $\mathbb{A}[u][[z]]$. Indeed, in the variables $(t, x)$, $F_g$ belongs to $\mathbb{Q}[p_1, \dots, p_K][x][[t]]$ for clear combinatorial reasons, and as explained in Section 2.2 the change of variables $t, x \leftrightarrow z, u$ preserves the polynomiality of coefficients. Therefore by Lemma 2, $F_g$ has no small poles. This excludes 0 and all small zeros of $N(u)$. Since $F_g$ is $uz$-antisymmetric and since by Proposition 3, the transformation $z \leftrightarrow \frac{1}{z^2u}$ exchanges small and large zeros of $N(u)$, this also implies that $F_g$ has no pole at the large zeros of $N(u)$.

The last thing to do is to examine the degree of $F_g$ in $u$. We know that $S$ is a polynomial in $x^{-1}$ of degree at most $K-1$, thus has degree at most $K-1$ in $u$. By induction and Lemma 1, the degree in $u$ of the R.H.S. of (8) is at most $K-2$. Since the degree of $Y$ is $K-1$, the degree of $F_g$ in $u$ is at most $-1$. $\square$

**Remark 1** Analogues of the previous proposition, stated in similar contexts [Eyn, Chap. 3] play a crucial role in Eynard's "topological recursion" framework. To understand the importance of Proposition 4, let us make a historical comparison. The "traditional" way of solving (8) with the kernel method would be to substitute in (8) all the small roots of $N(u)$, and use the $(K-1)$ equations thus obtained to eliminate the "unknown" polynomial $S$. Not surprisingly, this approach was historically the first one to be considered, see e.g. [Gao93]. It leads to much weaker rationality statements than the kind of methods we use here, since the cancellations that appear between those $(K-1)$ equations are formidable and very hard to track. As we will see, Proposition 4 circumvents this problem by showing that we just need to study (8) at the two points $u = \pm\frac{1}{z}$ rather than at the $(K-1)$ small roots of $N$.

With Proposition 4, we can now apply one of the main idea of the topological recursion, namely that the whole object $F_g$ can be recovered from the expansion of (8) at the critical points $u = \pm\frac{1}{z}$. In what follows, all generating functions considered are rational functions of the variable $u$ over $\mathbb{A}[[z]]$. In particular, the notation $F_g(u)$ is a shorthand notation for the series $F_g(t; x; p_1, \dots, p_K)$ considered as an element of $\mathbb{A}[[z]](u)$ (or even $\mathbb{Q}[p_1, p_2, \dots, p_K][[z]](u)$), i.e. $F_g(u) := F_g(t(z), x(z, u), p_1, p_2, \dots)$. We let $P(u) = \frac{1-uz}{1+uz}$ (the letter $P$ is for "prefactor"). By Proposition 4 the rational function $P(u)F_g(u)$ has only poles at $u = \pm\frac{1}{z}$ and has negative degree in $u$. Therefore, if $u_0$ is some new indeterminate, we can write $P(u_0)F(u_0)$ as the sum of two residues:

$$P(u_0)F(u_0) = \mathrm{Res}_{u=\pm\frac{1}{z}} \frac{1}{u_0 - u} P(u)F(u). \qquad (9)$$

Note that this equality only relies on the (algebraic) fact that the sum of the residues of a rational function at all poles (including $\infty$) is equal to zero; no complex analysis is required. Now, multiplying (8) by $P(u)$, we find:

$$P(u)F_g(u) = \frac{xtP(u)H_g(u)}{Y(u)} + \frac{xtP(u)S(x)}{Y(u)}.$$

with $H_g(u) = F_{g-1}^{(2)}(u) + \sum_{g_1, g_2 \ge 0} F_{g_1}^{(g_1)}(u)F_{g_2}^{(g_2)}(u)$. Now observe that the second term in the right-hand side has no pole at $u = \pm\frac{1}{z}$: indeed the factor $(1-uz)$ in $Y(u)$ simplifies thanks to the prefactor $P(u)$, and $xS(x)$ is a polynomial in $\frac{1}{x} = \frac{(1+uz)^2}{u}$. Returning to (9) we have proved:
**Theorem 4 (Topological recursion for bipartite maps)** The series $F_g(u_0)$ can be computed as:

$$F_g(u_0) = \frac{1}{P(u_0)} \mathrm{Res}_{u=\pm\frac{1}{z}} \frac{P(u)}{u_0 - u} \frac{xt}{Y(u)} \left( F_{g-1}^{(2)}(u) + \sum_{\substack{g_1+g_2=g \\ g_1, g_2>0}} F_{g_1}(u) F_{g_2}(u) \right). \quad (10)$$

Note that the R.H.S. of (10) involves only series $F_h$ for $h < g$ and the series $F_{g-1}^{(2)}$, which are covered by the induction hypothesis. This contrasts with (8), where the term $S(x)$ involves small coefficients of $F_g$.

### 3.3 Structure of $F_g$ and proof of Theorem 3

In order to compute $F_g(u_0)$ from Theorem 4, it is sufficient to be able to compute the expansion of the rational fraction $\frac{H_g(u)}{Y(u)}$ at the points $u = \pm \frac{1}{z}$. The expansion of the product terms $F_{g_1}(u)F_{g_2}(u)$ is well covered by the induction hypothesis, so the main point will be to study the structure of the term $F_{g-1}^{(2)}(u)$, and the derivatives of $Y(u)$ at $u = \pm \frac{1}{z}$. The first point will require to study closely the action of the operator $\Gamma$ on Greek variables (Theorem 6), and the second one requires a specific algebraic work (Theorem 5). Note also that, in order to close the induction step, we will need to take the projective limit $K \to \infty$. Therefore, we need to prove not only that the derivatives of $\frac{H_g(u)}{Y(u)}$ at $u = \pm \frac{1}{z}$ are rational functions in the Greek variables, but also that these functions do not depend on $K$. The program just sketched requires some lengthy work and will not be fully covered in this extended abstract. We list here the main steps and refer to [CF15] for the proofs.

The derivatives of $Y(u)$ at the critical points, shown in the following theorem, can be studied by explicit computations, which require some algebraic work. This is where the Greek variables appear.

**Theorem 5 (Expansion of $xtP(u)/Y(u)$ at $u = \pm \frac{1}{z}$)** The rational function in $u$, $\frac{xtP(u)}{Y(u)}$, has the following formal expansions at $u = \pm \frac{1}{z}$:

$$\frac{xtP(u)}{Y(u)} = \frac{1}{4(1-\eta)} + \sum_{\alpha, a \ge 2 | \alpha|} c''_{\alpha, a} \frac{\eta_{\alpha}}{(1-\eta)^{\ell(\alpha)+1}} (1-uz)^a,$$

$$\frac{xtP(u)}{Y(u)} = -\frac{1}{(1+\zeta)(1+uz)^2} + \sum_{\substack{\alpha, a \ge 0, b \ge 2 | \alpha| + a}} c''_{\alpha, a, b} \frac{(1+\gamma)^a \zeta_{\alpha}}{(1+\zeta)^{\ell(\alpha)+a+1}} (1+uz)^{b-2},$$

where $c''_{\alpha, a, b}$, $c'''_{\alpha, a, b}$ are computable rational numbers independent of $K$.

Note that the expansion above is entirely formal, with no consideration of convergence.

We can now sketch the proof for the base case of the induction, $g = 1$. From the explicit computation of the first four orders of the expansion above, and from the explicit expression $F_0^{(2)} = u^2 z^2 (1 - uz)^4$ (deduced from (7) by a computation), one can use (10) to deduce an explicit expression of $F_1$. See [CF15].

We then have to study the action of $\Gamma$.

**Theorem 6** The operator $\Gamma$ is a derivation on $\mathbb{Q}[x, p_1, p_2, \dots][[z]]$. Moreover, the image of $\Gamma$ on any Greek variable is a rational function of Greek variables and $s = \frac{1-uz}{1+uz}$, given by an explicit formula.

See [CF15] for the list of “explicit formulas” giving the action of $\Gamma$ on Greek variables. For example:

$$\Gamma \zeta_i = \frac{s^{-1} - s}{8(1 - \eta)s^2} ((2i + 1)\zeta_i - (2i - 1)\zeta_{i-1}) + \frac{1}{2}(s^{-1} - s)((2i + 1)s^{2i} - (2i - 1)s^{2i-2}).$$
**Sketch of the proof of Theorem 3.** Consider (10). From the induction hypothesis, Theorem 5 and Theorem 6, all the successive derivatives at $u = \pm\frac{1}{z}$ of the quantity inside the residue are rational functions in the Greek variables, independent of $K$, and with explicit control on the indices and exponents that appear. The only thing to verify for the induction step is the bounds on indices and degrees given in Theorem 3, which is an elementary task but has to be done meticulously, see [CF15]. □

# 4 Sketch of the unrooting step and final comments

We now give a very brief idea of how we deduced Theorem 1 from Theorem 3. Full proofs are available in [CF15]. Recall that $F_g = \Gamma L_g$, so to obtain $L_g$, we need to find some way to invert the rooting operator $\Gamma$. The first idea of the proof is inspired from [GGPN13], and consists in inverting the operator $\Gamma$ in two steps. More precisely we introduce the linear operators $\Box$ and $\diamond$ on $\mathbb{Q}[x, p_1, p_2, \dots][[z]]$ defined by $\Box x^k = (\frac{1}{k} - \frac{\gamma}{1+\gamma})p_k$, and $\diamond = \sum_k p_k \partial_{p_k}$, where $\partial_{p_k}$ is the partial differentiation with respect to $p_k$ over $\mathbb{Q}[x, p_1, p_2, \dots][[z]]$ (without consideration of the dependency of $z$ over $p_k$). Then, one can show by explicit computation (using the chain rule) that $\diamond A = \Box \Gamma A$ for any series $A \in \mathbb{Q}[p_1, p_2, \dots][[z]] \cap \mathbb{Q}[[p_1z, p_2z^2, p_3z^3, \dots]]$. One can show that $L_g$ is such a series and therefore, $\diamond L_g = \Box F_g$.

It is relatively easy to show by explicit computation that $\Box F_g$ is a rational function of the Greek variables from (5) (see [CF15]). To compute $L_g$, we thus only need to invert the operator $\diamond$ on such functions. Now, since Greek variables are linear combinations of the $p_i$, a simple computation shows the action of $\diamond$ on such functions to be essentially a univariate differentiation. Thus the action of $\diamond^{-1}$ on a rational function in the Greek variables can be computed by a univariate integration (see [CF15], or analogous situation in [GGPN13, Eq. (5.10)]). We thus know that $L_g$ is a rational function of Greek variables plus maybe some mixed products of a rational function by a logarithmic factor of the form $\log(1 - \eta)$ or $\log(1 + \zeta)$.

The second half of the proof is thus to show that the integration gives rise to no logarithm. In the analogous situation in [GGPN13], this is shown with a simple degree argument, which unfortunately does not work in our case. We thus proceed differently. We first note that, given what we already know about $L_g$, it is rational in the Greek variables if and only if it is algebraic in them. Moreover, it follows from Euler's formula that $(2 - 2g)L_g = L_g^{\text{vertex}} + L_g^{\text{face}} - L_g^{\text{edge}}$, where $L_g^{\{\text{vertex,face,edge}\}}$ is the exponential generating function of labelled bipartite maps with a marked vertex, face, or edge, respectively. Now, it is easy to compute $L_g^{\text{face}}$ and $L_g^{\text{edge}}$ from the series $F_g$, by applying the operators $x^k \to \frac{p_k}{k}$ and $x^k \to p_k$, respectively, and to show that the results are algebraic. Therefore if $2 - 2g \neq 0$, we only need to prove that $L_g^{\text{vertex}}$ is algebraic. Luckily(!) this result is already known: it was proved by the first author with bijective methods [Cha09, Eq. (8.2)] (more precisely this reference proves algebraicity of $L_g^{\text{vertex}}$ when $p_i = 1_{i \in D}$ for any finite set $D$, but it is an easy exercise to see that this is sufficient for our purpose). This ends the sketch of the proof of Theorem 1, and we refer to [CF15] for a full proof along these lines.

We conclude this paper with several comments. First, as explained in the introduction, we have only used two basic ideas from the topological recursion of [EO09]. It may be the case that other features of the latter can be applied to bipartite maps, for example a parallel way to perform the "unrooting" step sketched in Section 4, similar to [Eyn, Sec. 4.2]. However the proof we gave has the nice advantage of shedding a bijective light on the absence of logarithms in genus $g > 1$. Our next comment is about computational efficiency. While it is tempting to use (10) to compute the explicit expression of $F_g$, it is much easier to simply compute the first few terms of $L_g$ using recursively the Tutte equations (6), and then determine the unknown coefficients in (3) or (5) by solving a linear system. Third, structural results similar to (5) for the generating functions of bipartite maps with $m \ge 2$ marked faces are easily derived from our results
by successively applying to $L_g$ the operator $\Gamma_i$ defined for different variables $x_i$, $1 \le i \le m$. Finally, it is
natural to investigate further links between our results and those in [GJV01, GGPN13]. One may look for
a general model encapsulating all these rationality statements. This is the subject of a work in progress.

References

[ACM92] J. Ambjørn, L. Chekhov, and Yu. Makeenko. Higher genus correlators from the Hermitian one-matrix model. *Phys. Lett. B*, 282(3-4):341-348, 1992.

[BC91] E. A. Bender and E. R. Canfield. The number of rooted maps on an orientable surface. *J. Combin. Theory Ser. B*, 53(2):293-299, 1991.

[BC94] E. A. Bender and E. R. Canfield. The number of degree-restricted rooted maps on the sphere. *SIAM J. Discrete Math.*, 7(1):9-15, 1994.

[BDFG04] J. Bouttier, P. Di Francesco, and E. Guitter. Planar maps as labeled mobiles. *Electron. J. Combin.*, 11(1):Research Paper 69, 27, 2004.

[CF15] G. Chapuy and W. Fang. Generating functions of bipartite maps on orientable surfaces. *ArXiv e-prints*, February 2015.

[Cha09] G. Chapuy. Asymptotic enumeration of constellations and related families of maps on orientable surfaces. *Combin. Probab. Comput.*, 18(4):477-516, 2009.

[EO09] B. Eynard and N. Orantin. Topological recursion in enumerative geometry and random matrices. *J. Phys. A*, 42(29):293001, 117, 2009.

[Eyn] B. Eynard. *Counting Surfaces*. Book in preparation, available on the author's webpage.

[Eyn11] B. Eynard. Formal matrix integrals and combinatorics of maps. In John Harnad, editor, *Random Matrices, Random Processes and Integrable Systems*, CRM Series in Mathematical Physics, pages 415-442. Springer New York, 2011.

[Gao03] Z. Gao. The number of degree restricted maps on general surfaces. *Discrete Math.*, 123(1-3):47-63, 1993.

[GGPN13] I. P. Goulden, M. Guay-Paquet, and J. Novak. Polynomiality of monotone Hurwitz numbers in higher genera. *Adv. Math.*, 238:1-23, 2013.

[GJV01] I. P. Goulden, D. M. Jackson, and R. Vakil. The Gromov-Witten potential of a point, Hurwitz numbers, and Hodge integrals. *Proc. London Math. Soc. (3)*, 83(3):563-581, 2001.

[KZ14] M. Kazarian and P. Zograf. Virasoro constraints and topological recursion for Grothendieck's dessin counting. *ArXiv e-prints*, June 2014.

[LZ04] S. K. Lando and A. K. Zvonkin. *Graphs on surfaces and their applications*, volume 141 of *Encyclopaedia of Mathematical Sciences*. Springer-Verlag, 2004. Appendix by D. B. Zagier.

[Sch] G. Schaeffer. Chapter for a handbook of enumerative combinatorics. *in preparation*.

[Tut63] W. T. Tutte. A census of planar maps. *Canad. J. Math.*, 15:249-271, 1963.