%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}

\articlenumber{48}
\addbibresource{48.bib}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}
\usepackage{physics}
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\usepackage[utf8]{inputenc}
\newcommand{\too}{\longrightarrow}
\newcommand{\eps}{\varepsilon}
%\newcommand{\tr}{\mathrm{tr}\,}
\newcommand{\pgcd}{\mathop{\mathrm{pgcd}}}
\newcommand{\spec}{\mathrm{spec} \,}
%\newcommand{\var}{\mathrm{var}}
\newcommand{\Int}{\mathrm{Int}}
\newcommand{\Aut}{\mathrm{Aut}}
\newcommand{\loc}{\mathrm{loc}}
%\newcommand{\deg}{\mathrm{deg}}

\def\restriction#1#2{\mathchoice
              {\setbox1\hbox{${\displaystyle #1}_{\scriptstyle #2}$}
              \restrictionaux{#1}{#2}}
              {\setbox1\hbox{${\textstyle #1}_{\scriptstyle #2}$}
              \restrictionaux{#1}{#2}}
              {\setbox1\hbox{${\scriptstyle #1}_{\scriptscriptstyle #2}$}
              \restrictionaux{#1}{#2}}
              {\setbox1\hbox{${\scriptscriptstyle #1}_{\scriptscriptstyle #2}$}
              \restrictionaux{#1}{#2}}}
\def\restrictionaux#1#2{{#1\,\smash{\vrule height .8\ht1 depth .85\dp1}}_{\,#2}}

\newcommand{\T}{\mathcal{T}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\K}{\mathbb K}
\newcommand{\E}{\mathbb E}
\renewcommand{\H}{\mathscr H}
\renewcommand{\S}{\mathfrak{ S}}
\renewcommand{\P}{\mathbb P}
\newcommand{\p}{\boldsymbol{\mathcal{P}}}
\newcommand{\hp}{\boldsymbol{\mathcal{P}}^h}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\SL}{\mathrm{SL}}
\newcommand{\PGL}{\mathrm{PGL}}
\newcommand{\PSL}{\mathrm{PSL}}
\renewcommand{\O}{\mathrm{O}}
\newcommand{\SO}{\mathrm{SO}}
\newcommand{\card}{\mathop{\mathrm{card}}}
\renewcommand{\Re}{\mathrm{Re}\,}
\renewcommand{\Im}{\mathrm{Im}\,}
\newcommand{\rg}{\mathrm{rg}\,}
\newcommand{\lin}{\mathscr L}
\newcommand{\1}{\mathds 1}
\newcommand{\argsh}{\mathrm{argsh}\,}
\newcommand{\cau}{\mathcal{C}}
\newcommand{\hcau}{\mathcal{H}}
\newcommand{\bcau}{\mathcal{B}}
\newcommand{\sli}{\mathcal{S}}
\newcommand{\uu}{\mathcal{U}}
\newcommand{\expl}{\mathcal{E}}
\newcommand{\eff}{\mathrm{eff}}
\newcommand{\back}{\mathbf{B}}
\newcommand{\f}{\mathcal{F}}
\newcommand{\bdd}{\mathrm{bdd}}
\newcommand{\fil}{\mathrm{Fill}}
\newcommand{\m}{\mathcal{M}}
\newcommand{\bdy}{\widehat{\partial} \mathbf{T}}
\newcommand{\bd}{\widehat{\partial}}

\newcommand{\diam}{\mathrm{diam}}
\newcommand{\Alt}{\mathfrak{A}}
\newcommand{\Sym}{\mathfrak{S}}
\newcommand{\supp}{\mathrm{supp}\,}
\newcommand{\ie}{\textit{i.e.} }

%\linespread{1.1}

\newtheorem{thm}{Theorem}
%\newenvironment{thmbis}[1]
%  {\renewcommand{\thethm}{\ref{#1} bis}%
%   \addtocounter{thm}{-1}%
%   \begin{thm}}
%  {\end{thm}}

\newenvironment{preuve}{
  \noindent \textit{Proof. }}{\hfill \(\square\) }

\newenvironment{idproof}{
  \noindent \textit{Sketch of proof. }}{\hfill \(\square\) }




\newtheorem{prop}[thm]{Proposition}
\newtheorem{corr}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{defn}{Definition}%[section]
\newtheorem{exemple}{Example}
\newtheorem{ex}[exemple]{Example}

\theoremstyle{remark}
\newtheorem{rem}{Remark}
\newtheorem{rems}[rem]{Remarks}


\newcommand{\louf}[1]{{\color{red}#1}}
\newcommand{\budz}[1]{{\color{blue}#1}}
\usepackage{lipsum}

%% define your title in the usual way
\title{Simple formulas for constellations and bipartite maps with prescribed degrees}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Baptiste Louf\thanks{\href{mailto:blouf@irif.fr}{blouf@irif.fr}. Baptiste LOUF is fully supported by ERC-2016-STG 716083 "CombiTop".}}

%% then use \addressmark to match authors to institutions here
\address{IRIF, Universit\'e Paris Diderot, Paris, France}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We obtain simple quadratic recurrence formulas counting bipartite maps on surfaces with prescribed degrees (in particular, $2k$-angulations), and constellations. These formulas are the fastest known way of computing these numbers.

Our work is a natural extension of previous works on integrable hierarchies (2-Toda and KP), namely the Pandharipande recursion for Hurwitz numbers (proven by Okounkov and simplified by Dubrovin--Yang--Zagier), as well as formulas for several models of maps (Goulden--Jackson, Carrell--Chapuy, Kazarian--Zograf).  As for those formulas, a bijective interpretation is still to be found.

We also include a formula for monotone simple Hurwitz numbers derived in the same fashion.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{maps, Hurwitz numbers, Toda hierarchy, constellations}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
A map is  a combinatorial object describing the embedding up to homeomorphism of a multigraph on a compact oriented surface. A bipartite map is a map with black and white vertices, each edge having a black end and a white end. Constellations are generalizations of bipartite maps with more colors (see \cref{sec:def_results} for precise definitions).

Map enumeration has been an important research topic for many years now, going back to Tutte \cite{Tutte} with planar maps. He used analytic techniques on generating functions, and later on, Schaeffer enumerated planar maps bijectively \cite{theseSch}, with many generalizations (see for instance \cite{BDG,BF,AP}).  The enumeration of maps was extended to other models : for instance, asymptotic formulas were obtained by Bender and Canfield \cite{BC} for maps of higher genus, by Gao \cite{Gao} for maps with prescribed degrees, and Chapuy \cite{Constellations} for constellations. Another way to count maps is to see them as factorizations of permutations and to use algebraic properties of $\S_n$. In particular, maps fit in the more general context of weighted Hurwitz numbers (see e.g. \cite{ACEH}). Their generating functions satisfy integrable hierarchies of PDEs that arose from mathematical physics, namely the KP and 2-Toda hierarchies (a good introduction can be found in \cite{Solitons}).

The first numbers that were studied from the point of view of integrable hierarchies were Hurwitz numbers, that enumerate ramified coverings of the sphere. Pandharipande conjectured a recurrence formula for those numbers \cite{Pandharipande}, which was proven by Okounkov \cite{Ok} and later simplified by Dubrovin, Yang and Zagier \cite{Zagier}. Later, recurrence formulas for maps were found, starting with Goulden and Jackson for triangulations \cite{GJ}. They were followed by Carrell and Chapuy for general maps \cite{CC}, and Kazarian and Zograf for bipartite maps \cite{KZ}. All these works start from the fact that an underlying generating function is a "tau function" of an integrable hierarchy, and then use ad-hoc techniques to obtain explicit recurrence formulas. The generality of this second step is not well understood. In particular, although the methods mentioned in the previous page enable to control face degrees, this is not the case of the efficient recurrences of \cite{Zagier,GJ,CC,KZ}.  This raises the question of obtaining similar formulas for other models of maps.

\textbf{Contributions of this article:} We show that similar techniques as in \cite{Ok,Zagier} apply more generally in the context of maps, and we derive recurrence formulas for bipartite maps with prescribed degrees, allowing us in particular to derive a formula for bipartite $2k$-angulations. We also find recurrence formulas for constellations. These formulas are, up to our knowledge, the simplest and fastest way to calculate those numbers (in all models, it takes $O(n^2g^3)$ arithmetic operations to calculate the coefficient for $n$ edges and genus $g$, see \cref{rem_fastest}). We insist on the fact that the underlying "tau function" structure is well-known, the contribution of this paper is to show that it can be used to control face degrees and count constellations.

\textbf{Structure of the paper:}
In \cref{sec:def_results}, we will give precise definitions and state our main results. The rest of the paper presents the main steps of the proof.
The first part of the proof is common to all models : we introduce the "tau function" $\tau$, a certain generating function for constellations. This function, along with some auxiliary functions $\tau_n$, classically satisfies a set of differential equations called the $2$-Toda hierarchy. Our first contribution, inspired by \cite{Ok}, is to link $\tau$ to the $\tau_n$ and derive an equation involving $\tau$ only (\cref{eq_tau}). This will be presented in \cref{sec:weighted_hurwitz}.
From this equation, specialized to the model we wish for (bipartite maps or constellations), we perform a few combinatorial operations (that are specific to the model, similarly as in \cite{CC, GJ, KZ}) to obtain our formulas. We will present this in details for bipartite maps in \cref{sec:rec_formulas}, and we briefly mention the case of constellations.
\section{Definitions and main results}\label{sec:def_results}

\begin{defn}
A map $M$ is the data of a connected multigraph (multiple edges and loops are allowed) $G$ (called the underlying graph) embedded in a compact oriented surface $S$, such that $S\setminus G$ is homeomorphic to a collection of disks. The connected components of $S\setminus G$ are called the \textit{faces}. %Equivalently, $M$ is the data of $G$ and a rotation system which describes the cyclic order of the half-edges around each vertex.
The \textit{genus} $g$ of $M$ is the genus of $S$ (the number of "handles" in $S$). $M$ is defined up to orientation-preserving homeomorphism.
A \textit{bipartite map} is a map with two types of vertices (black or white), such that each edge connects two vertices of different colors. A bipartite map is said to be \textit{rooted} if a particular edge is distinguished. 

An \textit{$m$-constellation} is a particular kind of map with special vertices : colored vertices, carrying a "color" between $1$ and $m$, and star vertices. Each edge connects a star vertex to a colored vertex. A star vertex has degree $m$, and its neighbors have color $1$,$2$,…,$m$ in the clockwise cyclic order. Bipartite maps are in bijection with $2$-constellations, since each star vertex and its two adjacent edges can be merged into a single edge connecting a black and a white vertex. A constellation is said to be rooted if a particular star vertex is distinguished. A constellation with $n$ star vertices is said to be \textit{labeled} if each star vertex carries a different label between $1$ and $n$. Since rooting kills all possible automorphisms, there is a $(n-1)!$-to-$1$ correspondence between labeled and rooted constellations with $n$ star vertices. From now on, we will only consider rooted objects unless stated otherwise. 
\end{defn}

Some basic, well-known, properties of maps and constellations will be useful later.

\begin{prop}\label{prop_constellation_bipartite}
Labeled (non-necessarily connected) $m$-constellations with $n$ star vertices are in bijection with $(m+1)$-uples $(\sigma_1,\sigma_2,…,\sigma_m,\phi)$ of permutations of $\S_n$ such that $\sigma_1\cdot\sigma_2\cdot …\cdot \sigma_m= \phi$. The permutation $\sigma_i$ represents the vertices of color $i$ : each vertex is a cycle of $\sigma_i$, and the elements of the cycle represent the neighboring star vertices, in that cyclic order. The permutation $\phi$ encodes the faces. See \cref{constellation} for an example.
\end{prop}

\begin{figure}[!h]

\centering
\includegraphics[scale=1]{constellation}
\caption{Left : a (labeled) $3$-constellation (of genus $0$) and the corresponding permutations, right : the permutation $\phi$, whose cycles describe the faces.}
\label{constellation}
\end{figure}

\newpage
Our main results are the following theorems :
\begin{thm}\label{thm_angulations}
The number $A^{(k)}_{g,n}$ of bipartite $2k$-angulations of genus $g$ with $n$ faces satisfies the following recurrence formula :
\begin{align*}
\binom{kn+1}{2}A^{(k)}_{g,n}=&\sum_{\substack{n_1+n_2=n\\n_1,n_2\geq 1\\g_1+g_2+g^*=g}} (kn_1+1) \binom{(k-1)n_2+2-2g_2}{2g^*+2}A^{(k)}_{g_1,n_1}A^{(k)}_{g_2,n_2}\\&+\sum_{g^*\geq 0}\binom{(k-1)n+2-2(g-g^*)}{2g^*+2}A^{(k)}_{g-g*,n}.
\end{align*}
\end{thm}
\cref{thm_angulations} is actually a particular case of the following theorem for bipartite maps with prescribed degrees :
\begin{thm}\label{thm_biparti_degre}
The number $B_g(\textbf{f})$ of bipartite maps of genus $g$ with $f_i$ faces of degree $2i$ (for $\textbf{f}=(f_1,f_2,…)$) satisfies :
\begin{align}\label{rec_biparti_genre}
\binom{n+1}{2}B_g(\textbf{f})&=\sum_{\substack{\textbf{s}+\textbf{t}=\textbf{f}\\\textbf{s},\textbf{t}\neq \textbf{0}\\g_1+g_2+g^*=g}}(1+n_1)\binom{v_2}{2g^*+2}B_{g_1}(\textbf{s})B_{g_2}(\textbf{t})+\sum_{g^*\geq 0}\binom{v+2g^*}{2g^*+2}B_{g-g*}(\textbf{f})
\end{align}
where $n=\sum_i if_i$, $n_1=\sum_i is_i$, $v=2-2g+n-\sum_i f_i$, $v_2= 2-2g_2+n_2-\sum_i t_i$ and $n_2=\sum_i it_i$ (the $n$'s  count edges, the $v$'s count vertices, in accordance with the Euler formula).
\end{thm}
\begin{thm}\label{thm_constellations}
The numbers $C^{(m)}_{g,n}$ of $m$-constellations of genus $g$ with $n$ star vertices satisfy the following recurrence formula :
\[\binom{n}{2}C^{(m)}_{g,n}=\sum_{\substack{n_1+n_2=n\\n_1,n_2\geq 1\\g=g_1+g_2+g^*}} n_1\binom{(m-1)n_2+2-2g_2}{2g^*+2}C^{(m)}_{g_1,n_1}C^{(m)}_{g_2,n_2}.\]
\end{thm}
\begin{rem}\label{rem_fastest}
\cref{thm_biparti_degre} allows to compute the number of maps with prescribed degrees way faster than the usual Tutte-Lehman-Walsh approach \cite{LW,BC,Gao} or the topological recursion (see e.g. \cite{Eynard}), especially for higher genus (because these methods require counting maps with up to $g$ boundaries to enumerate maps of genus $g$). It can also be specialized to maps with bounded face degrees (contrarily to the Tutte equation).

We observe that \cref{thm_constellations} applies to bipartite maps (for $m=2$). It is also possible to obtain an analogue of \cref{thm_biparti_degre} (with prescribed degrees) for $m$-constellations with $m\geq 3$, but the formula is more complicated and is not quadratic anymore (we do not include it in this short version). We give a brief explanation of that fact in \cref{sec:constellations}.

We can also derive a similar-looking formula for monotone simple Hurwitz numbers, see \eqref{eq_monotone}.
\end{rem}
%\section{Structure of the proof}
%The outline of the proof is the following. There is a first part which is common to all models, where we introduce the weighted Hurwitz numbers and their generating function $\tau$. This function $tau$, along with some auxiliary functions $\tau_n$, satisfies a set of differential equations called the $2$-Toda hierarchy. Similarly as in REF Ok, we interpret one of those equations, and derive an equation involving $\tau$ only (PROPO).
%
%We then specialize this function to the model we wish for. Using a trick similar to Zagier's in REF, we transform our equation on generatic series into a quadratic one (see REF)
%
%Finally,  we do some combinatorial interpretation (similarly as in REF CC, GJ, KZ) to get rid of the derivatives, and then we extract coefficients to obtain our formulas.
\section{Generating functions for constellations}\label{sec:weighted_hurwitz}
Our goal is to prove \cref{eq_tau}. In order to do this, we first have to introduce Maya diagrams and the semi infinite wedge space.
\subsection{The semi infinite wedge space}
We give some definitions, mostly following the notations of the appendix in \cite{Ok2} : 
\begin{defn}
A \textit{Maya diagram} is a decoration of $\Z+\frac{1}{2}$ with a particle or an antiparticle at each position, such that for some $n_1,n_2$ there are only particles at positions $<n_1$ and only antiparticles at positions $>n_2$. The semi infinite wedge space $\Lambda^{\frac{\infty}{2}}$ is the vector space whose orthonormal basis elements are the Maya diagrams.

For any $k\in \Z+\frac{1}{2}$, we define the \textit{fermion operators} $\psi_k$ and $\psi_k^*$. For each Maya diagram $\textbf{m}$, we define :
\begin{align*}
\psi_k \textbf{m} &= \begin{cases}
0 & \text{if } \textbf{m} \text{ has a particle in position } k\\
\tilde{\textbf{m}} & \text{otherwise}\\
\end{cases} \\
\psi_k^* \textbf{m} &= \begin{cases}
0 & \text{if } \textbf{m} \text{ has an antiparticle in position } k\\
\overline{\textbf{m}} & \text{otherwise}\\
\end{cases}
\end{align*}
where $\tilde{\textbf{m}}$ is the same as $\textbf{m}$ except there is a particle in position $k$, and $\overline{\textbf{m}}$ is the same as $\textbf{m}$ except there is an antiparticle in position $k$.

We can now define the \textit{boson operators} : for all $n\in\Z\setminus \lbrace 0\rbrace $, let \[\alpha_n=\sum_{\substack{k\in \Z+\frac{1}{2}}} \psi_{k-n}\psi_k^*.\]

Finally, the two \textit{vertex operators} are  \[\Gamma_\pm(\textbf{p})=\exp(\sum_{n=1}^\infty  \frac{p_n}{n}\alpha_{\pm n}).\]
\end{defn}

\begin{defn}
We define the \textit{normally ordered products} 
\[:\psi_k\psi_k^*:=\begin{cases}
\psi_k\psi_k^* &\text{if } k>0\\
-\psi_k^*\psi_k &\text{if } k<0\\

\end{cases}\]
and the \textit{charge} and \textit{energy operators} :
\[C=\sum_{\substack{k\in \Z+\frac{1}{2}}} :\psi_k\psi_k^*: \hspace{1cm} H=\sum_{\substack{k\in \Z+\frac{1}{2}}} k:\psi_k\psi_k^*:.\]
The Maya diagrams are eigenvectors of $C$. The eigenvalue of a Maya diagram $\textbf{m}$ is the number of particles in positive position minus the number of antiparticles in negative position. We call this number the \textit{charge} of $\textbf{m}$.
We introduce the translation operator $R$ : for any $\textbf{m}$, $R\textbf{m}$ has a particle in position $k+1$ if and only if $\textbf{m}$ has a particle in position $k$. Note that if the charge of $\textbf{m}$ is $c$, the charge of $R\textbf{m}$ is $c+1$.

There is a bijection between Maya diagrams of charge $0$ and partitions, as depicted in \cref{maya_diagram}. Thus, any Maya diagram $\textbf{m}$ can be encoded by its charge $c$ and a partition $\lambda$ (that corresponds to the Maya diagram $R^{-c} \textbf{m}$). 
\begin{figure}[!h]
\centering
\includegraphics[scale=0.3]{maya}
\caption{A maya diagram of charge $0$ and its corresponding partition (above it, presented as a rotated Young diagram). In blue, a box and its content (the abscissa of the projection of the center of the box on $\Z$)}
\label{maya_diagram}
\end{figure}

We will use the braket notation, and denote the Maya diagram corresponding to the empty partition by $\ket{\emptyset}$, and set $\ket{\emptyset_n}=R^n\ket{\emptyset}$. We will also set $\ket{\lambda}$ to be the Maya diagram of charge $0$ corresponding to the partition $\lambda$. In particular,  $H\ket{\lambda}=|\lambda| \ket{\lambda}$, where $|\lambda |$ is the number of boxes in $\lambda $. 

\end{defn}

\subsection{Constellations and content products}
\begin{defn}\label{def_W}
Fix integers $r$, $n$ and $g$, fix $\lambda,\mu$ two partitions of $n$. Let $W_{n}^{\lambda,\mu}(l_1,l_2,…,l_r)$ be the number of $(r+2)$-uples of permutations $(\sigma_1,\sigma_2,…,\sigma_{r},\sigma_\lambda,\sigma_\mu)$ of $\S_n$ such that $\sigma_1\cdot \sigma_2\cdot …\cdot \sigma_{r}=\sigma_\lambda\sigma_\mu$ and $\sigma_i$ has $l_i$ cycles, and $\sigma_\lambda,\sigma_\mu$ have respective cycle types $\lambda$ and $\mu$.
The $W_{n}^{\lambda,\mu}$ enumerate (labeled, non-necessarily connected) constellations, in accordance with \cref{prop_constellation_bipartite}. Let $\tau$ be the associated generating function (that implicitly depends on $r$):
\[ \tau(z,\textbf{p},\textbf{q},(u_j)) =\sum_{\substack{n\geq 0\\|\mu |=|\lambda |=n\\ l_i\geq 1\text{ }  \forall i} }\frac{z^n}{n!} \prod_{i=1}^r u_i^{n-l_i} p_\lambda q_\mu W_{n}^{\lambda,\mu}(l_1,l_2,…,l_r) \]
\end{defn}

It is a classical result (under different forms and variants, see for instance \cite{GJ,Ok}) that the function $\tau$ can be expressed in terms of elements and operators of $\Lambda^{\frac{\infty}{2}}$ :
\begin{lem}[Classical]
\begin{equation}\label{eqn_tau_operators}
\tau(z,\textbf{p},\textbf{q},(u_j))=\mel{\emptyset}{\Gamma_+(\textbf{p})z^H\Lambda \Gamma_-(\textbf{q})}{\emptyset}
\end{equation}
with 
\[F(u)=\sum_{\substack{k>0}}\sum_{\substack{i=0}}^{k-1/2}\log(1+ui)\psi_k\psi_k^*+\sum_{\substack{k<0}}\sum_{\substack{i=0}}^{-k-1/2}\log(1-ui)\psi_k^*\psi_k\]
and  $\Lambda=\prod_{j=1}^r\exp(F(u_j))$.

\end{lem}
%\louf{réécrire cette preuve}
\begin{proof}
For reasons of space, we only include the main ideas of the proof.

First, we have 
\[F(u)\ket{\nu}=\left(\sum_{\Box\in\nu} \log(1+uc(\Box)) \right)\ket{\nu}\]
where the $c(\Box)$ are the contents of the partition $\nu$ (see \cref{maya_diagram}). It can be shown using the Jacobi-Trudi rule (see e.g. \cite{Ok2}) that 

\[\Gamma _ { - } ( \textbf{q}) \ket { \emptyset } = \sum _ { \nu } s _ { \nu } ( \textbf{q}) \ket { \nu }\quad \text{and}\quad \bra { \emptyset }\Gamma _ {+} ( \textbf{p})  = \sum _ { \nu } s _ { \nu } ( \textbf{p}) \bra { \nu }.\]

Thus the RHS of \eqref{eqn_tau_operators} can be rewritten as :
\[\sum_{\substack{n>0\\|\nu|=n}} z^n \prod_{j=1}^r  \prod_{\Box\in\nu} (1+u_jc(\Box))s _ { \nu } ( \textbf{p}) s _ { \nu } ( \textbf{q}).\]

Here we recognize the "content product form" of the generating function of constellations, as in \cite{GJ}, which concludes the proof.% Familiar readers may like to know that it uses the fact that the Jucys-Murphy elements of $\C[\S_n]$ act as the contents of partitions \cite{JM}.
%On the other hand, let
%\[W^{\lambda,\mu}=\sum_{\substack{ l_i\geq 1  \forall i} }\prod_{i=1}^r u_i^{n-l_i}  W_{n}^{\lambda,\mu}(l_1,l_2,…,l_r)\]
%we have 
%\begin{align*}
%W^{\lambda,\mu}&=[\textbf{1}]\prod_{j=1}^r\sum_{\sigma_j \in \mathfrak{S}_n} u_j^{n-l(\sigma_j)}\sigma_jK_\lambda K_{\mu}\\&=[\textbf{1}]\prod_{j=1}^r\prod_{i=2}^n (1+u_jJ_i)K_\lambda K_{\mu}
%%\\&=\frac{1}{(n!)^2}\sum_{|\nu | =n} \chi^{\nu} (K_{\lambda})\chi^{\nu} (K_{\mu})\prod_{j=1}^r\prod_{\Box \in \nu} (1+u_jc(\Box))
%\end{align*}
%
%
%where $[\textbf{1}]$ means taking the coefficient of $\textbf{1}$ (the identity permutation) in the canonical basis of $\C[\S_n]$, or equivalently to take the trace in the regular representation of $\S_n$.  $K_\lambda=\sum_{\substack{\sigma \in C_\lambda}} \sigma$ where $C_\lambda$ is the conjugacy class of cycle-type $\lambda$ in $\S_n$, and the $J_k$ are the Jucys-Murphy elements of $\C[\S_n]$, namely \[J _ { 1 } = 0 , J _ { k } = ( 1 , k ) + ( 2 , k ) + \cdots + ( k - 1 , k ) \quad \text { for } \quad k \geqslant 2\] It is known that a symmetric polynomial in the Jucys-Murphy has the partitions as eigenvectors, with eigenvalues being the same polynomial in the contents of the said partition.
%
%Therefore, classical representation-theoretic considerations imply
%\[\tau(z,\textbf{p},\textbf{q},(u_j))=\sum_{\substack{n\geq 0,|\mu |=|\lambda |=|\nu|=n }}\frac{z^n}{(n!)^2} \prod_{i=1}^r  p_\lambda q_\mu\chi^{\nu}_\mu\chi^{\nu}_\lambda |C_{\mu}| |C_\lambda|\prod_{j=1}^r\prod_{\Box \in \nu} (1+u_jc(\Box)) \]
%where the $\chi$'s are the irreducible characters of $\S_n$ associated to the partitions. \eqref{eqn_tau_operators} follows from the fact that they are also the coefficients in the change of basis between Schur functions and powersums.
\end{proof}
We introduce the auxiliary functions $\tau_n$, for $n\in\Z$ :
 \[\tau_n =\mel{\emptyset_n}{\Gamma_+(\textbf{p})z^H\Lambda \Gamma_-(\textbf{q})}{\emptyset_n}.\]
We have $\tau=\tau_0$. The previous lemma, along with classical considerations (see for instance Section 2.6 in \cite{Ok}), imply that the $\tau_n$ satisfy an infinite set of equations, the $2$-Toda hierarchy. In particular, the following equation holds :

\begin{equation}\label{eq_tau_pm_1}
\frac { \partial ^ { 2 } } { \partial p _ { 1 } \partial q _ { 1 } } \log \tau_0  = \frac { \tau _ {  1 } \tau _ { - 1 } } { \tau_0 ^ { 2 } }.
\end{equation}
So far, the content presented was classical. Our first main contribution is to transform the previous equation into an equation implying $\tau$ only.
\begin{prop}\label{eq_tau}
The function $\tau$ introduced in \cref{def_W} satisfies
\begin{equation}\label{eq_tau_tout_seul}
\frac { \partial ^ { 2 } } { \partial p _ { 1 } \partial q _ { 1 } } \log \tau  = z\frac { \tau(z\cdot\prod_{j=1}^r (1+ u_j),\textbf{p},\textbf{q},(\frac{u_j}{1+ u_j}))\tau(z\cdot\prod_{j=1}^r (1- u_j),\textbf{p},\textbf{q},(\frac{u_j}{1- u_j})) } { \tau  ^ { 2 } }.
\end{equation}
\end{prop}

%\louf{Preuve très elliptique, peut être tailler un peu qq part pour rajouter 2 lignes au calcul de décalage).
\begin{proof}
It is easily verified that $R$ commutes with $\Gamma_+(\textbf{p})$ and $\Gamma_-(\textbf{q})$, as well as $R^{-n}HR^n=H+nC+\frac{n^2}{2}$.
Thus,
\[\tau_n=\mel{\emptyset}{R^{-n}\Gamma_+(\textbf{p})z^H\Lambda \Gamma_-(\textbf{q})R^n}{\emptyset}=\mel{\emptyset}{\Gamma_+(\textbf{p})z^{H+nC+\frac{n^2}{2}}R^{-n}\Lambda R^n\Gamma_-(\textbf{q})}{\emptyset}.\]
But, by a careful change of indices,
\begin{align*}
 RFR^{-1}&=\sum_{\substack{k>0}}\sum_{\substack{i=0}}^{k-1/2}\log(1+ui)\psi_{k+1}\psi_{k+1}^*+\sum_{\substack{k<0}}\sum_{\substack{i=0}}^{-k-1/2}\log(1-ui)\psi_{k+1}^*\psi_{k+1}\\
 %&=\sum_{\substack{k>1}}\sum_{\substack{i=0}}^{k-3/2}\log(1-u+ui)\psi_k\psi_k^*+\sum_{\substack{k<1}}\sum_{\substack{i=0}}^{-k+1/2}\log(1--u-ui)\psi_k^*\psi_k\\
% &=\sum_{\substack{k>0}}\sum_{\substack{i=1}}^{k-3/2}\log(1-u+ui)\psi_k\psi_k^*+\sum_{\substack{k<0}}\sum_{\substack{i=1}}^{-k+1/2}\log(1--u-ui)\psi_k^*\psi_k\\
&=\sum_{\substack{k>0}}\sum_{\substack{i=1}}^{k-1/2}\log(1-u+ui)\psi_{k}\psi_{k}^*+\sum_{\substack{k<0}}\sum_{\substack{i=1}}^{-k-1/2}\log(1-u-ui)\psi_{k}^*\psi_{k}\\
 &=F(\frac{u}{1-u})+(H-C/2)\log(1-u).
\end{align*}

Similarly, \[R^{-1}FR=F(\frac{u}{1+u})+(H+C/2)\log(1+u).\]

Thus, we get :
\[\tau_{\pm 1}(z,\textbf{p},\textbf{q},(u_j))=z^{1/2}\tau(z\cdot\prod_{j=1}^r (1\pm u_j),\textbf{p},\textbf{q},(\frac{u_j}{1\pm u_j})),\]
and the result follows by plugging this into \eqref{eq_tau_pm_1}.
\end{proof}
\begin{rem}
The idea of expressing $\tau_{\pm 1}$ in terms of $\tau$ by calculating $R^{\mp 1}\Lambda R^{\pm 1}$ is inspired by the calculation performed in \cite{Ok}, Section 2.7.
\end{rem}
\section{Recurrence formulas}\label{sec:rec_formulas}
\subsection{Bipartite maps}\label{sec:bipartite}
In this section we study bipartite maps, therefore we work with $r=2$. The objects we are interested in are connected, thus, in accordance with the "exp-log principle" (see for instance \cite{Flajolet}), we need to consider $H=\log(\tau)$.
Let $H^{\lambda,\mu}$ be its coefficients in the series expansion, namely 
\[H=\sum_{n\geq 0,|\mu |=|\lambda |=n} \frac{z^n}{n!} H^{\lambda,\mu}p_\lambda q_\mu.\]
Note that $H^{\lambda,\mu}$ is a polynomial in $u_1$ and $u_2$.
We will set $u_1=u_2$ (which is equivalent to counting vertices regardless of their color) and "get rid" of the $\textbf{q}$ variables.
More precisely, let $H_n^\lambda=\restriction{H^{\lambda,1^n}}{u_1=u_2=u}$ and 
\[H^*(z,\textbf{p},u)=\restriction{H}{q_i=\delta_{i,1},\text{ } u_1=u_2=u}=\sum_{n\geq 0, |\lambda|=n}H_n^\lambda\frac{z^n}{n!}p_\lambda .\]
By \cref{prop_constellation_bipartite}, $H_n^\lambda$ counts (connected, labeled) bipartite maps with $n$ edges, with $\lambda$ describing the face type and a weight $u$ per vertex.

The next step, inspired by the case of classical Hurwitz numbers \cite{Zagier}, is to obtain a quadratic (differential) equation for $H^*$ from \eqref{eq_tau_tout_seul}.
\begin{lem}
\begin{equation}\label{eq_h_star_biparti}
D^2 H_1^*-D H_1^*=D H_1^*\left( DH^*(z(1+u)^2,\textbf{p},\frac{u}{1+u})+DH^*(z(1-u)^2,\textbf{p},\frac{u}{1-u})-2DH^*  \right)
\end{equation}
with $H_1^*=\frac { \partial  } { \partial p _ { 1 }  } H^*$ and  $D=z\frac{\partial}{\partial z}$.

\end{lem}
\begin{proof}
We have

\[\restriction{\frac { \partial ^ { 2 } } { \partial p _ { 1 } \partial q _ { 1 } } \log \tau}{q_i=\delta_{i,1},\text{ } u_1=u_2=u}=\restriction{\left(\sum_{n> 0}H_n^\lambda\frac{z^n}{n!}np_\lambda q_1^{n-1}\right)}{q_1=1}=z\frac { \partial} { \partial z}H_1^*.\]

Hence \eqref{eq_tau_tout_seul} now reads
\[D H_1^*(z,\textbf{p},u)=z\exp(H^*(z(1+u)^2,\textbf{p},\frac{u}{1+u})+H^*(z(1-u)^2,\textbf{p},\frac{u}{1-u})-2H^*).\]
Applying $D$ to the previous equation, and eliminating the exponential term between the two equations, one gets the result.
\end{proof}

We will now interpret $H^*$ and $H_1^*$ in \eqref{eq_h_star_biparti} in terms of bipartite maps, using a local combinatorial operation that is specific to bipartite maps. This step is conceptually similar to what was done in \cite{GJ,CC,KZ}.
\begin{lem}
Let $B(z,\textbf{p},u)$ be the ordinary generating function of connected rooted bipartite maps, and $B_g(\textbf{f})$ be the number of bipartite maps of genus $g$ with $f_i$ faces of degree $2i$, such that
\[B=\sum_{\substack{g,\textbf{f}}} z^d u^{2n-v} \prod_{i\geq 1}p_i^{f_i} B_g(\textbf{f}).\]
with $n=\sum_i if_i$ and $v-n+\sum_i f_i = 2-2g$ (Euler formula).
$B$ satisfies the following equation :
\begin{equation}\label{eq_biparti_GF}
(D+1)DB=(u^{-2}+(D+1)B)\left( B(z(1+u)^2,\textbf{p},\frac{u}{1+u})+B(z(1-u)^2,\textbf{p},\frac{u}{1-u})-2B \right).
\end{equation}
\end{lem}

\begin{proof}

$H^*$ is the exponential generating function of labeled connected bipartite maps, where $u$ records the number of vertices, $z$  records edges, and $p_i$ records faces of degree $2i$. We directly have $B=DH^*$, as there is an $(n-1)!$-to-$1$ correspondence between labeled and rooted bipartite maps.

The function $p_1H^*_1$ would be the EGF of the same objects, with a marked digon (face of degree $2$). There is a $n!$-to-$1$ correspondence between labeled and unlabeled-unrooted bipartite maps with a marked digon and $n$ edges.
A marked digon can be contracted into a root edge (see \cref{digon}) except when the bipartite map is just one edge, thus $H^*_1=z+u^2zB$ (the $u^2z$ factor comes from the fact that we lose an edge when we contract the digon, and the $z$ term is the case where we cannot contract the digon). 

\begin{figure}
\centering
\includegraphics[scale=0.4]{digon}
\caption{Contraction of a digon.}
\label{digon}
\end{figure}
\end{proof}

We are finally ready to prove \cref{thm_biparti_degre}.
%\begin{thm}
%\begin{align}\label{rec_biparti_genre}
%(d+1)dB_g(\textbf{f})&=2\sum_{\substack{\textbf{f}=\textbf{s}+\textbf{t}\\\textbf{p},\textbf{q}\neq \textbf{0}\\g_1+g_2+g^*=g}}(1+d_1)\binom{v_2}{2g^*+2}B_{g_1}(\textbf{s})B_{g_2}(\textbf{t})+2\sum_{g^*\geq 0}\binom{v+2g^*}{2g^*+2}B_{g-g*}(\textbf{f})
%\end{align}
%where $d=\sum_i if_i$, $d_1=\sum_i is_i$, $v=2-2g+d-\sum_i f_i$, $v_2= 2-2g_2+d_2-\sum_i t_i$ and $d_2=\sum_i it_i$ (the $d$'s  count edges, the $v$'s count vertices, and we are just using the Euler formula).
%\end{thm}
\begin{proof}[Proof of \cref{thm_biparti_degre}]
We look at the factor $B(z(1+u)^2,\textbf{p},\frac{u}{1+u})+B(z(1-u)^2,\textbf{p},\frac{u}{1-u})-2B$ in \eqref{eq_biparti_GF}.
The coefficient of $z^n \prod_{i\geq 1} p_i^{f_i}$ in it is :
\begin{align*}
\sum_{v>0} B_g(\textbf{f})u^{2n-v}\left( (1+u)^{v}+(1-u)^v-2\right)=\sum_{v>0}B_g(\textbf{f})u^{2n-v}\ \left( 2 \sum_{0<k\leq\frac{v}{2}} u^{2k}\binom{v}{2k}\right).
\end{align*}

Extracting coefficients in \eqref{eq_biparti_GF}, one gets the result.
\end{proof}




%A nice particular case of \eqref{rec_biparti_genre} is bipartite $2k$-angulations. Fixing and arbitrary $k$, setting $f_i=0$ for all $i\neq k$ in \eqref{rec_biparti_genre}, we recover Theorem \ref{thm_angulations}.

\begin{rem}\label{rem_color_tracking}
If we don't specialize $u_1=u_2=u$ as we did at the beginning of this subsection, we can obtain formulas for more precise coefficients of bipartite maps (namely knowing the number of vertices of each color). This will appear in the long version.
\end{rem}
%\subsection{Controlling the degrees of black and white vertices}
%We can also look at  more precise coefficients for bipartite maps, namely with control over the degrees of black and white vertices. Let $Bip_{g,d}(\textbf{b},\textbf{w})$ be the number of bipartite maps of genus $g$, with $d$ edges, $b_i$ black vertices of degree $i$, $w_i$ white vertices of degree $i$. 
%
%We can do the same analysis as in the previous subsection: but this time we consider weighted Hurwitz numbers with $r=1$ and we do not specialize $\textbf{q}$. The combinatorial argument about a marked digon becomes a similar one with a marked black leaf and a marked with leaf, and in the end we get 
%\begin{equation}\label{rec_biparti_blackwhite}
%blabla
%\end{equation} 
%
%By "duality", $Bip_{g,d}(\textbf{b},\textbf{w})$ is also the number of bipartite maps of genus $g$, with $d$ edges, $b_i$ faces of degree $2i$ and $w_i$ white vertices of degree $i$. Since bipartite quadrangulations are in bijection with maps, with white vertices being in correspondence with faces, taking $b_i=\delta_{i,2}$ in \eqref{rec_biparti_blackwhite}, one gets a recurrence formula for maps with control over the degree of the faces. Let $Q_g(d,\textbf{f})$ be the number of maps  of genus $g$ with $d$ edges and $f_i$ faces of degree $i$, we have :
%\begin{equation}\label{rec_maps_faces}
%blabla
%\end{equation}
%As before, we can specialize this formula to $k$-angulations :
%\begin{equation}\label{rec_maps_k_angulations}
%blabla
%\end{equation}
%\section{Other models}
\subsection{Constellations}\label{sec:constellations}

The proof of \cref{thm_constellations} is similar to the proof of \cref{thm_biparti_degre} that was presented in the previous section : for $m$-constellations, we consider our function $\tau$ with $r=m+1$. However, we now "get rid" of both the $\textbf{p}$ variables and the $\textbf{q}$ variables by specializing $p_i=q_i=\delta_{i,1}$, hence we do not control over the degrees of the faces.


As mentioned in the introduction, one can also study the effect of the specialization $q_i=\delta_{i,1}$ (leaving the $p_i$ non specialized) in the case of constellations with $m>2$. However the operation of contracting an $m$-gon (that can be defined similarly as the contraction of a digon presented in \cref{digon}) might disconnect the map, and the formula we obtain is more complicated (it will be included in a full version). %Similarly as noted in Remark \ref{rem_color_tracking}, we also obtain formulas for constellations &counted by vertices of each color (included in a full version of this paper).

%Also we can blabla simplify, obtain other formulas …
%\subsection{Monotone Hurwitz numbers}
%We briefly mention another type of Hurwitz numbers for which we can obtain recurrence relations with the same techniques.
%
%\begin{defn}
%Fix integers $d$ and $g$, fix $\lambda,\mu$ two partitions of $d$ and $\sigma_\lambda,\sigma_\mu$ two arbitrary permutations of $\S_d$ with respective cycle types $\lambda$ and $\mu$. For two transpositions $(i,j)$ and $(k,l)$ of $\S_d$, we say that $(i,j)\preceq (k,l)$ if $\max(i,j)\leq \max(k,l)$. Let $Mon_{g,d}^{\lambda,\mu}$ be $\frac{1}{d!}$ times the number of $XXX$-uples of transpositions $(t_1,t_2,…,t_{XXX})$ such that $t_1\cdot t_2\cdot …\cdot t_{XXX}=\sigma_\lambda,\sigma_\mu$ and the sequence $(t_1,t_2,…,t_{XXX})$ is increasing with respect to $\preceq$. Let $Mon_{g,d}=Mon_{g,d}^{1^d,1^d}$.
%
%The $Mon_{g,d}$ (resp. the $Mon_{g,d}^{\lambda,\mu}$) are called monotone Hurwitz numbers (resp. biramified Hurwitz numbers).
%\end{defn}
%
%The tau-function of biramified monotone Hurwitz numbers can be written in the form
%\[\tau =\mel{\emptyset}{\Gamma_+(\textbf{p})z^H\Lambda \Gamma_-(\textbf{q})}{\emptyset}\]
%with $\Lambda=\exp(-F(-u))$, thus everything works the same as for weighted Hurwitz numbers, and we obtain the following recurrence formula :
%\begin{equation}\label{rec_monotone}
%blabla
%\end{equation}
%
%Note that monotone Hurwitz numbers have a graphical equivalent, see THESE GUAYPAQUET for instance.

\section{Conclusion}
The coefficients in our recurrence formulas have a combinatorial flavor. It is a natural question to ask for a bijective proof of these formulas. However, the bijective interpretation of formulas  derived from the KP/2-Toda hierarchies is still a widely open question, as bijections have only been found for certain formulas, in the particular cases of one-faced \cite{CFF} and planar maps \cite{Louf}.

Using the same technique, we can also obtain recurrence formulas for similar numbers called monotone simple (i.e. unramified at $0$ and $\infty$) Hurwitz numbers, introduced in \cite{monotone}, that are also particular cases of weighted Hurwitz numbers. These numbers $\vec{H}_{g,n}$ (of genus $g$, in $\S_n$) satisfy the following recurrence formula :
\begin{equation}\label{eq_monotone}
(n^3-n^2)\vec{H}_{g,n}=2\sum_{\substack{n_1+n_2=n\\g^*\geq 0\\g_1+g_2+g^*=g}}n_1^2n_2\binom{2n_2+2g_2+2g^*-1}{2g^*+2}\vec{H}_{g_1,n_1}\vec{H}_{g_2,n_2}.
\end{equation}

\acknowledgements{The author is grateful to his advisor, Guillaume Chapuy, for suggesting this problem, useful comments and guidance.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\sloppy
\printbibliography
\fussy


\end{document}
