%% 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[finalversion]{FPSAC2018}
\articlenumber{33}

%% 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}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{definition}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}

\usepackage{lipsum}

%% define your title in the usual way
\title{A new family of bijections for planar maps}

%% 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''.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}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 present bijections for the planar cases of two formulas on
maps that arise from the KP hierarchy (Goulden--Jackson and
Carrell--Chapuy formulas), relying on a ``cut-and-slide'' operation. 
This is the first time a bijective proof is given for quadratic map-counting formulas derived from the KP hierarchy. Up to now, only the linear one-faced case was known (Harer--Zagier recurrence and Chapuy--F\'eray--Fusy bijection).
As far as we know, this bijection is new and not equivalent to any of the well-known bijections between planar maps and tree-like objects.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous pr\'esentons une preuve bijective, dans le cas planaire, de
deux formules sur les cartes  qui proviennent de la hi\'erarchie KP
(formules de Goulden--Jackson et Carrell--Chapuy), gr\^ace \`a une
op\'eration de type ``cut-and-slide''.
% La formule de Carell-Chapuy est une formule de r\'ecurrence sur les cartes de n'importe quel genre, avec un nombre quelconque de faces. Sa restriction aux cartes \`a une face, la r\'ecurrence d'Harer-Zagier, a une explication bijective gr\^ace \`a Chapuy, F\'eray et Fusy. Dans cet article, un autre cas particulier, \`a savoir les cartes planaires, est trait\'e.
% Nous esp\'erons qu'un jour ces deux approches seront unifi\'ees pour fournir une explication bijective de Carell-Chapuy dans le cas g\'en\'eral. 
%Les bijections reposent toutes sur une exploration particuli\`ere de la carte, puis une op\'eration de type "cut-and-slide". 
Il s'agit de la premi\`ere explication bijective de formules quadratiques sur les cartes issues de la hi\'erarchie KP. Jusqu'ici, seul le cas lin\'eaire des cartes \`a une face \'etait connu (r\'ecurrence d'Harer--Zagier et bijection de Chapuy--F\'eray--Fusy).
Il semble que la bijection propos\'ee soit d'un genre nouveau et ne soit pas \'equivalente aux bijections classiques entre les cartes planaires et des objets arborescents.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{planar maps, bijections, the KP hierarchy, R\'emy's bijection}

%% 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{33-Louf.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}

\textbf{Context:} A map is  a combinatorial object describing the embedding up to homeomorphism of a multigraph on a compact orientable surface (see Section \ref{sec:def} for precise definitions).
Map enumeration has been an important research topic for many years now. Tutte first enumerated planar maps \cite{Tutte}, raising the natural concern of finding bijections explaining those formulas. Such bijections have since been found, mostly thanks to the family of bijections between maps and decorated trees (blossoming trees and mobiles) \cite{Cori1981},\cite{BDG},\cite{AP},\cite{BF},\cite{theseSch}. Some of these bijections have recently been extended to maps on surfaces of higher genus (see for instance \cite{Schaeffer}) and on non orientable surfaces \cite{CD}.

Another powerful tool for map enumeration is the KP hierarchy. The Kadomtsev--Petviashvili hierarchy is an infinite set of PDEs on functions with a infinite number of variables, which arose from mathematical physics (see \cite{Solitons},\cite{Ok} and references therein). The first equation of the hierarchy 
%(which is the one that is used the most in map enumeration)
is
\[{F_{3,1}=\frac{1}{12}F_{1^4}+F_{2^2}+\frac{1}{2}(F_{1^2})^2},\]
where the indices indicate partial derivatives (e.g. $F_{3,1}=\frac{\partial^2}{\partial p_1\partial p_3}F$). First, links with objects connected to maps, such as Hurwitz numbers, have been observed (see for instance \cite{Ok}). In 2008, Goulden and Jackson \cite{GJ} showed that certain generating functions for maps (with variables controlling the degrees of vertices or faces) are solutions to the KP hierarchy. It allowed them to derive a very simple recurrence formula for triangulations
\begin{equation}
\begin{split}
(n+1)T(n,g)=&4n(3n-2)(3n-4)T(n-2,g-1)+4(3n-1)T(n-1,g)\\
&+4\sum_{\substack{i+j=n-2\\i,j\geq 0}}\sum_{\substack{g_1+g_2=g\\g_1,g_2\geq 1}}  (3i+2)(3j+2)T(i,g_1)T(j,g_2)+2\mathbb{1}_{n=g=1},
\end{split}
\label{GJ}
\end{equation}
where $T(n,g)$ is the number of rooted triangulations of genus $g$ with $3n$ edges. Then, using similar methods, Carrell and Chapuy \cite{CC} proved a recurrence formula on general maps
\begin{equation}
\begin{split}
(n+1)Q_g(n,f)=&2(2n-1)Q_g(n-1,f)+2(2n-1)Q_g(n-1,f-1)\\&+(2n-3)(n-1)(2n-1)Q_{g-1}(n-2,f)\\
&+3\sum_{\substack{k+l=n\\k,l\geq 1}}\sum_{\substack{u+v=f\\u,v\geq 1}}\sum_{\substack{i+j=g\\i,j\geq 1}}(2k-1)(2l-1)Q_i(k-1,u)Q_j(l-1,v),
\end{split}
\label{CC}
\end{equation}
where $Q_g(n,f)$ is the number of rooted maps of genus $g$ with $n$ edges and $f$ faces. Taking $f=1$, one recovers the famous Harer--Zagier recurrence \cite{HZ}.\\


\textbf{Contributions of this article:} Finding bijections for formulas arising from the KP hierarchy on maps would allow us to understand maps in greater depth, but for now it is still mainly an open problem. The only special case known for Formulas \eqref{CC} and \eqref{GJ} is the case of one-faced maps \cite{CFF}. In this paper, we present bijective proofs for the planar case (g=0) of Goulden--Jackson and Carrell--Chapuy formulas. Note that contrarily to the one-faced case which is linear, the planar formulas are, as in the general case, quadratic.

We prove a more general formula on precubic maps (see Section
\ref{sec:def} for a definition) which implies the Goulden--Jackson
formula. The Carrell--Chapuy formula comes from two separate (but somehow related by their bijective proofs) formulas that were not predicted by the KP hierarchy, one of them being a generalization of the famous R\'emy bijection on trees \cite{Remy} to all planar maps.

Our bijections rely on a particular exploration of the map and on a ``cut
and slide'' operation. A similar (although slightly different) operation is defined in \cite{Bettinelli} (see Remark \ref{rem} for more details).  Although non-local, this operation allows us to keep track of the degrees of the vertices, which gives us more precise formulas. One can hope to unite the concepts that arise in the bijective proofs of the higher genus case with 1 face (the trisections, see for instance \cite{CFF}) and of the planar case with several faces (the cut and slide operation, defined in this article) into one general framework. However, putting it all together seems to be a challenge of its own.

The bijective study of planar maps is a well understood topic, especially thanks to bijections with tree-like objects \cite{Cori1981},\cite{BDG},\cite{AP},\cite{BF},\cite{theseSch}. However, as far as we know, our bijection is not equivalent to the bijections above (although certain similarities can be observed, such as a search of the dual map, DFS in our case, BFS in the bijections above). 
%What's more, the bijections act directly on the maps, and we don't have to go through tree models.

We also have a bijective proof of the precubic recurrence for two-faced maps (not included in this paper), but it is already very complicated and involves separate cases. Using the second KP equation, we can derive an equation on maps with vertices of degrees $1$ or $4$, whose planar case is very similar to Formula \eqref{precubic} and is also proved by our bijection. This suggests that this exploration+cut-and-slide scheme is somehow underlying in the KP hierarchy for maps.

In Section \ref{sec:def}, we will give some definitions on maps. In Section \ref{sec:results}, we will state the main results of this article. The bijections will be described in Section \ref{sec:bij}. Section \ref{sec:deg} will present refined formulas with control over the degrees of the vertices.

%\textbf{Ommited proofs:} An extended version with an appendix that includes the proofs can be found at \url{https://www.irif.fr/_media/users/blouf/loufplanarmapswithappendix.pdf}
\section{Definitions}
\label{sec:def}
\begin{definition}
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 orientable 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 \textbf{rotation system} which describes the cyclic order of the half-edges around each vertex.
The \textbf{genus} $g$ of $M$ is the genus of $S$ (the number of
``handles'' in $S$). $M$ is defined up to homeomorphism. A \textbf{corner} of $M$ is an angular sector between two consecutive half-edges around a vertex. A \textbf{rooted map} is a map with a distinguished corner. A small arrow is placed in the distinguished corner, thus splitting the corner in two separate corners (left and right of the arrow).
If a rooted map $M$ of genus $g$ has $n$ edges, $v$ vertices and $f$ faces, the Euler formula links those quantities: $v-n+f=2-2g$. $M$ has $2n+1$ corners.

A \textbf{planar map} is a rooted map of genus $0$. It can be drawn on the plane with the root lying on the outer face. A \textbf{precubic map} is a map with vertices of degree $1$ or $3$ only, rooted on a vertex of degree $1$. A \textbf{leaf} is a vertex of degree $1$ that is not the root.
\end{definition}
\begin{figure}[!h]
\centering
\includegraphics[scale=0.5]{map}
\caption{A planar map}
\label{map}
\end{figure}

\section{Main results}
\label{sec:results}
\begin{thm}
\label{cs}
There is a bijection between planar maps $M$ with a marked discovery (discoveries are specific edges whose sides lie in different faces, see Section \ref{sec:bij} for a precise definition) and pairs of planar maps $(M_1,M_2)$ such that $M_1$ has a marked vertex and $M_2$ has a marked leaf. This bijection preserves the total number of edges and faces. It gives the following formula on planar maps
\begin{equation}
(f-1)Q(n,f)=\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}v_1Q(i,f_1)(2j+1)Q(j,f_2),
\label{cut-slide}
\end{equation}
where $Q(n,f)$ is the number of planar maps with $n$ edges and $f$ faces, and $v_1$ counts the number of vertices in the first map (i.e. $v_1=2+i-f_1$)

This bijection adapts to precubic maps, and the marked vertex of $M_1$ is now a marked leaf
\begin{equation}
(f-1)\alpha(n,f)=\sum\limits_{i+j=n}\sum\limits_{f_1+f_2=f}\alpha^{(1)}(i,f_1)\alpha^{(1)}(j,f_2),
\label{precubic}
\end{equation}
where $\alpha(n,f)$ counts the number of (planar) precubic maps with $n$ edges and $f$ faces, and $\alpha^{(1)}(n,f)$ counts the number of precubic maps with $n$ edges and $f$ faces and a marked leaf. 
\end{thm}
\begin{thm}[Generalized R\'emy bijection]
\label{re}
There is a bijection between planar maps $M$ with a marked leaf and planar maps $M'$ with a marked corner, such that $M'$ has as many faces and one edge less than $M$.

There is a bijection between planar maps $M$ with a marked node (i.e. a vertex that is not a leaf) and the union of planar maps $M'$ with a marked corner and pairs of planar maps $M_1$ and $M_2$ such that they both have a marked vertex. The total number of faces is preserved, and the total number of edges decreases by one.

It gives us the following formula
\begin{equation}
vQ(n,f)=2(2n-1)Q(n-1,f)+\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}v_1Q(i,f_1)v_2Q(j,f_2),
\label{remy}
\end{equation}
where the ``$v$-variables'' count the number of vertices. This holds for $n>0$.
\end{thm}
Taking $n=3m+2$ and $f=m+2$ in \eqref{precubic}, one recovers
\begin{cor}[Goulden--Jackson planar case]
\label{cor}
\[(n+1)T(n)=4(3n-1)T(n-1)+4\sum_{\substack{i+j=n-2\\i,j\geq 0}}  (3i+2)(3j+2)T(i)T(j),\]
where $T(n)$ counts the number of planar triangulations with $3n$ edges.
\end{cor}

Combining Formulas \eqref{cut-slide} and \eqref{remy} and doing some manipulations, one recovers
\begin{cor}[Carrell--Chapuy planar case]
\begin{equation}
\label{planar}
\begin{split}
(n+1)Q(n,f)=&2(2n-1)Q(n-1,f)+2(2n-1)Q(n-1,f-1)\\
&+3\sum_{\substack{k+l=n\\k,l\geq 1}}\sum_{\substack{u+v=f\\u,v\geq 1}}(2k-1)(2l-1)Q(k-1,u)Q(l-1,v).
\end{split}
\end{equation}
\end{cor}
Formula \eqref{planar} is not straightforwardly derived from Formulas \eqref{cut-slide} and \eqref{remy}. Indeed, the proof (not included here because of lack of space) is actually a proof by induction on $n$, that involves applying Formulas \eqref{cut-slide} and \eqref{remy} several times and even the dual of Formula \eqref{cut-slide}.
\section{The bijections}
\label{sec:bij}
In this section, we will define the exploration of a planar map and the notion of discoveries that result from it, then we will explain our bijections.
\begin{definition}
The \textbf{exploration} of a planar map is defined iteratively in the following way: starting from the root, go along the edges, keeping the edges on the right (progress in clockwise order). When an edge that is at the interface of the current face and a face not yet discovered is found, open this edge into a bud and a stem, and continue the process, thus entering the new face. Continue until the root is reached again.

Each edge that has been opened during the process is called a \textbf{discovery}, and the vertex attached to the bud is called a \textbf{discovery vertex}. If there are $f$ faces, there are $f-1$ discoveries (note that several discoveries can share the same discovery vertex).

The exploration is actually equivalent to a DFS of the dual, with a
``right first'' priority. It defines a partial order on the faces, thus for each face (resp. discovery) (but the outer face) we can define its \textbf{previous face} (resp. \textbf{previous discovery}). It also defines a order on the corners (resp. half edges) incident to each vertex, according to the order in which they were visited during the exploration. 

Let $e$ be a discovery, adjacent to faces $f_1$ and $f_2$, such that $f_1$ is the previous face of $f_2$. We say $e$ \textbf{leaves} $f_1$ and \textbf{enters} $f_2$.
\end{definition}

\begin{rem}
The exploration is a dynamic process that modifies the map along the way, but in the end, once the exploration is over and the discoveries have been found, we will deal with the original, unmodified map, with its original edges and faces. It is as if we did the exploration then closed the map back. Alternatively, one can think of an exploration that doesn't open the discoveries but just crosses them.
\end{rem}
\begin{figure}[!h]
\centering

\includegraphics[scale=0.7]{exploration.pdf}
\caption{The exploration of a planar map. The buds are the outgoing arrows, the stems are the ingoing arrows. Left: the original map. Center: the opened map. Right: The original map, with its discoveries and discovery vertices in purple. The red tree describes the partial order among the faces. The corners are labeled in the order they were found during the discovery}
\end{figure}

We can now relate the bijections and the formulas. In a map with $f$ faces, there are $f-1$ discoveries, so there are $(f-1)Q(n,f)$ maps with $n$ edges, $f$ faces and a marked discovery. A marked leaf can be retracted into a marked corner (see Figure \ref{feuille} left), such that there are $(2i+1)Q(i,f_1)$ maps with $i+1$ edges, $f_1$ faces and a marked leaf. There are $v_2Q(j,f_2)$ maps with $j$ edges, $f_2$ faces and a marked vertex. So Formulas \eqref{cut-slide} and \eqref{remy} are indeed consequences of Theorems \ref{cs} and \ref{re}. In a precubic map, one can retract a leaf into a marked side-edge losing two edges (see Figure \ref{feuille} right), so a precubic map with no leaf is equivalent to a cubic map, and we find corollary \ref{cor}.
\begin{figure}[!h]
\centering
\includegraphics[scale=0.5]{feuille}
\caption{Retracting a leaf: in a general map (left), in a precubic map (right)}
\label{feuille} 
\end{figure}
\subsection{Cut and slide bijection}

Here we will describe the bijection for general maps, but it is straightforward to see that it also applies to precubic maps and gives the bijection we want.
\begin{definition}
A discovery is said to be \textbf{disconnecting} if the corner preceding the discovery and the last corner (in the order defined by the exploration) around the discovery vertex lie in the same face. 
 
\label{disco}
\end{definition}

Any map with a marked disconnecting discovery can be (bijectively) split into two maps, one with a marked vertex, the other with a marked leaf in the outer face (see Figure \ref{split}).
\begin{figure}[!h]
\centering
\includegraphics[scale=1.5]{splitting}
\caption{Splitting a map at a disconnecting discovery. Here we only see what happens locally around the disconnecting discovery. On the left, the discovery and its discovery vertex are in purple, $c$ is the corner preceding the discovery, and $c^*$ is the last corner around the discovery vertex}
\label{split}
\end{figure}

The splitting operation of a disconnecting discovery describes our bijection in the case where the marked discovery is disconnecting, and the reverse bijection in the case where the marked leaf lies in the outer face.

We have the following lemma:
\begin{lem}
If a vertex has a corner in the outer face, then its last corner lies in the outer face.
\label{lem}
\end{lem}

\begin{proof}[Proof of Theorem \ref{cs}]
The general process is iterative (see Figure \ref{bij} for an example).

\textbf{Cut process:} Start from a map $M$ with a marked discovery $e$, let $v$ be its discovery vertex. If the discovery is disconnecting, then split $M$ at $v$ as described after definition \ref{disco}.

Otherwise, open $e$ into a bud $b_0$ and a stem $s_0$, and consider its previous discovery $e_1$ (in the order defined above). If it is disconnecting, then split it, otherwise open it (into $b_1$ and $s_1$) and consider the previous discovery $e_2$, and so on until a splitting operation is made. Note that a discovery that leaves the outer face is always disconnecting (because of Lemma \ref{lem}), so the algorithm terminates. One ends up with two maps $M_1$ and $M_2'$, such that $M_1$ has a marked vertex and $M_2'$ has a marked leaf $l$ and (possibly) some buds and stems, all lying in the outer face.

\textbf{Slide process:} We will not modify $M_1$. If there are no buds and stems in $M_2'$, we are done. Else, consider $s_0$, and make it a marked leaf. Then consider $l$, and make it a stem. Finally, glue back the buds and stems together canonically: starting from the root of $M_2'$, taking a clockwise tour of the outer face, one encounters a certain number of buds, then the same number of stems. There is only one way to match each bud with each stem such that the map remains planar. Equivalently, if there are $k+1$ buds and $k+1$ stems, match $b_0$ with $s_1$, and so on, until $b_k$ is matched with $l$. We obtain a map $M_2$ with a marked leaf, together with the map $M_1$ with a marked vertex.\\

Conversely, starting from $M_2$ with a marked leaf $l$ and $M_1$ with a marked vertex, consider $M_2$. $l$ lies in a certain face $F$, and if $F$ is not the outer face, there is a certain discovery $e_0$ that enters $F$. Open it into a bud $b_0$ and a stem $s_0$, then open the previous discovery $e_1$, and repeat the process until a discovery that leaves the outer face has been opened (in that case there is no previous discovery to open). One ends up with a map $M_2'$ with a marked leaf $l$ and possibly some buds and stems, all lying in the outer face. If there are some buds and stems, let $s$ be the stem that was created last in the process. Make $s$ a marked leaf $l^*$, and make $l$ a marked stem $s^*$, then close the map canonically. One now has a map $M_2^*$ with a marked leaf on the outer face and (possibly) a marked edge $e$ (that comes from the closure of $s^*$). This marked edge is actually a discovery in $M_2^*$ (and will be a discovery in the final map). If $e$ doesn't exist, let $l^*=l$, and mark the edge adjacent to $l^*$ (and call it $e$). Now do the inverse of the splitting operation: glue $l^*$ to the root vertex of $M_2^*$ at its first corner, and then glue the root of the resulting map at the last corner of the marked vertex of $M_1$ to obtain a map $M$ with a marked discovery $e$.\\
Note that, for precubic maps, discovery vertices are always of degree $3$, so that when split, the marked vertex of $M_1$ and the root of $M_2$ are both of degree $1$, which gives us Formula \eqref{precubic}.
\begin{figure}[!h]
\centering
\includegraphics[scale=0.5]{bijection}
\caption{The bijection (above) and its inverse (below)}
\label{bij}
\end{figure}
\end{proof}
\begin{rem}
\label{rem}
The cut and slide operation also appeared in \cite{Bettinelli}. However there are significant differences: the cut path is geodesic (leftmost BFS), and both endpoints of the path need to be specified. Whereas here, the cut path is defined by a leftmost DFS, and only one endpoint of the path (the marked discovery) needs to be specified, the other endpoint (the disconnecting discovery) is uniquely determined. What's more, the bijections in \cite{Bettinelli} imply linear formulas, contrarily to our quadratic formulas.
\end{rem}
\subsection{Generalized R\'emy bijection}
We will now describe a generalized R\'emy bijection on planar maps, that also relies on the cut-and-slide operation. 

We recall R\'emy's bijection for plane tree that proves the formula $(n+1)T(n)=2(2n-1)T(n-1)$ where $T(n)$ counts the number of rooted plane trees with $n$ edges (see Figure \ref{tree} for an example). Start from a tree $T$ with $n$ edges and a marked vertex $v$. If $v$ a leaf, retract it (as in Figure \ref{feuille}) to obtain a tree $T'$ with $n-1$ edges, with a marked corner. Otherwise, $v$ has a last son $v'$, that is its son that is found last during a clockwise tour of the unique face. We can then contract the edge between $v$ and $v'$, and mark a corner around the merging vertex to remember where to grow the edge back. The reverse bijection is then straightforward.
\begin{figure}[!h]

\centering
\includegraphics[scale=0.5]{remy}   \hspace{1cm}
\includegraphics[scale=0.5]{growing}
\caption{R\'emy's bijection for planar trees (left) and the growing operation (right)}
\label{tree}
\end{figure}

We can now describe the generalized R\'emy bijection for planar maps. 
\begin{proof}[Proof of Theorem \ref{re}]

\begin{figure}[!h]
\centering
\label{growing}

\end{figure}
Take a planar map $M$ and mark a vertex $v$. If it is a leaf, contract it
to mark a corner. Otherwise, consider the last corner around $v$, and let
$e$ be the edge that appears just before the last corner around $v$ in
the clockwise order. Let $v'$ be the other end of $e$ (note that it is
possible that $v=v'$). $v'$ will play the role of the ``last son'' of $v$. We can try and contract $e$, marking a corner around the merging vertex to remember where to grow back the edge. Consider the inverse of this operation (growing an edge from $v$): it produces a vertex $v'$ that has to be found after $v$ in the exploration. Thus, the operation of contracting $e$ is well-defined whenever $v$ is found before $v'$ in the exploration. This gives us the first term of the RHS of Formula \eqref{remy}. The remaining case is when $v'$ has actually been seen before $v$ during the exploration (including the case $v=v'$). But this means we reached the end of a cycle, and since we are dealing with planar maps, it means that $e$, the edge we were trying to contract, is actually a discovery! In that case, instead of contracting it, we can just apply the cut and slide operations (as defined in the previous bijection) with $e$ as a marked discovery. We end up with two maps $M_1$ and $M_2$, but now the marked leaf of $M_2$ has to be the last son of its neighbor $v^*$. So we can just contract it and mark $v^*$ (to go back, we just grow the leaf from the last corner of $v^*$). This gives us the second term of the RHS of Formula \eqref{remy}.
\begin{figure}[!h]
\centering
\includegraphics[scale=0.5]{remy2}
\caption{The generalized R\'emy bijection. The case similar to trees (above), and the cut-and-slide case (below)}
\label{remy2}
\end{figure}
\end{proof}
There is also a generalization of R\'emy's bijection on binary trees to precubic maps, that works exactly the same, we leave it as an exercise to the reader.

\section{Controlling the degrees of the vertices}
\label{sec:deg}
Here we present an analogue of \eqref{cut-slide} with control over the degrees of the vertices. If $\textbf{v}=(v_i)_{i\in \mathbb{N}}$ is a sequence of integers, for any $j>0$, we set $\delta_j(\textbf{v})=\textbf{w}$ where $w_j=v_j+1$ and $w_i =v_i$ for $i\neq j$, and $\delta_{-j}=\textbf{w'}$ where $w_j'=v_j-1$ and $w_i '=v_i$ for $i\neq j$. Finally, we set $\delta(\textbf{v},j_1,\hdots,j_k)=\delta_{j_1}\circ \hdots\circ \delta_{j_k}(\textbf{v})$.
Let $M(r,f,\textbf{v})$ the number of planar maps with $f$ faces, with
root of degree $r$, with $\textbf{v}=(v_i)_{i\in \mathbb{N}}$ such that there are $v_i$ vertices of degree $i$ (root included). The cut-and-slide operation only modifies the degrees at the marked leaf and the splitting vertex, so we can immediately derive this more precise formula
\begin{thm} 
\begin{align*}
&(f-1)M(r,f,\textbf{v})\\
=&\sum_{\substack{j,k\geq 1}}\sum_{\textbf{u}+\textbf{w}=\delta(\textbf{v},1,j,k,-(j+k+1))}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(u_j-\mathbb{1}_{j=r})M(r,f_1,\textbf{u})(w_1-\mathbb{1}_{k=1})M(k,f_2,\textbf{w})\\
&+\sum_{\substack{j+k=r-1}}\sum_{\textbf{u}+\textbf{w}=\delta(\textbf{v},1,-r,k,j)}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}M(j,f_1,\textbf{u})(w_1-\mathbb{1}_{k=1})M(k,f_2,\textbf{w}).
\end{align*}
\end{thm}
Note that the second term appears when the vertex that is split is the root (and thus the $(u_j-\mathbb{1}_{j=r})$), and the $(w_1-\mathbb{1}_{k=1})$ term means that the marked leaf in the second map cannot be the root. Note that this recurrence formula allows us to compute the number of maps with bounded vertex degrees.\\

Formula \eqref{remy} also has an analog where the degrees are recorded, but it splits into three different cases, according to whether the marked vertex is a leaf, the root, or another node. If it is a leaf, it is the trivial bijection described in Figure \ref{feuille}. If it is the root vertex, the formula is actually Tutte's formula. We will only include the formula corresponding to the case where the marked vertex is a node. This formula alone suffices to calculate all the terms by induction.
As before, there are extra terms because it depends whether the modification affects the root or not.

%Marking a leaf:
%\begin{align*}
%(v_1-\mathbb{1}_{r=1})M(r,f,\textbf{v})=&\sum_{j\geq 1}j(u_j-\mathbb{1}_{j=r})M(r,f,\textbf{u}=\delta(\textbf{v},-1,-(j+1),j))\\&+ru_{r-1}M(r-1,f,\textbf{u}=\delta(\textbf{v},-1,-r,r-1))
%\end{align*}
%
%
%Marking an "internal node", that is not the root,
For $p\neq 1$:
\begin{align*}
&(v_p-\mathbb{1}_{p=r})M(r,f,\textbf{v})\\
=&\sum_{\substack{j\geq 1}}u_{p+j-2}M(r,f,\textbf{u}=\delta(\textbf{v},-j,-p,j+p-2))\\
&+\sum_{\substack{j,k\geq 0}}\sum_{\substack{\textbf{u}+\textbf{w}=\delta(\textbf{v},-p,p-1,j,k,-(j+k+1))}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(u_j-\mathbb{1}_{j=r})M(r,f_1,\textbf{u})w_{p-1}M(k,f_2,\textbf{w})\\
&+\sum_{k=0}^{r-1} \sum_{\substack{\textbf{u}+\textbf{w}=\delta(\textbf{v},-p,p-1,-r,k,r-k-1)}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}M(r-1-k,f_1,\textbf{u})w_{p-1}M(k,f_2,\textbf{w}).
\end{align*}
%
%
%Finally, if we mark the root:
%\begin{align*}
%M(r,f,\textbf{v})=&\sum_{\substack{j\geq 1}}M(r+j-2,f,\delta(\textbf{v},-j,-p,j+p-2))\\&+\sum_{\substack{j+k=r-2\\j,k\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}\sum_{\substack{\textbf{u}+\textbf{w}=\delta(\textbf{v},-r,j,k)}} M(j,f_1,\textbf{u})M(k,f_2,\textbf{w})
%\end{align*}




\acknowledgements{I am thankful to Guillaume Chapuy for introducing this problem to me, and for being a great PhD advisor in general.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography
%\newpage
%\section*{Appendix}
%\textbf{Note: this appendix contains proofs of statements given in the article. It is only here for the referees who would like to check that the theorems are correct, and is not to be included in the final paper.}
%
%\begin{proof}[Proof of lemma \ref{lem}]
%In a map $M$, let $v$ be a vertex with one of its corners lying in the outer face. If $v$ is the root vertex, then it is obvious that its last corner lies in the outer face. Else, let $e$ be the first edge around $v$, as defined by the exploration (i.e. the edge we see in the exploration just before the first occurrence of $v$). Let $c$ be one corner around $v$ that lies in the outer face. Suppose it is not the last corner around $v$. Let $c_0$ (resp. $c^*$) be the first (resp. the last) corner around $v$, and let $F_0$ (resp. $F^*$) be the face in which $c_0$ (resp. $c^*$) lies. Suppose $F^*$ is not the outer face. (See XXFigure \ref{corners})
%
%\begin{figure}[!h]
%\centering
%\includegraphics[scale=1]{corners}
%\caption{}
%\label{corners}
%\end{figure}
%
%If a face $F'$ is deeper (in terms of the partial order defined by the exploration) than a face $F$ (and $F\neq F'$), then during the exploration (ignoring all other faces), we first see a part of $F$, then all of $F'$, then the rest of $F$. This would mean that during the exploration of $M$, at the time when we see $c$, $F^*$ hasn't been discovered yet. But that would mean that at the time when we see $e$ (which comes before $c$ in the exploration), $F^*$ hasn't been discovered yet. But then $e$ would be a discovery, and thus $c^*$ would be seen before $c_0$, contradiction
%\end{proof}
%
%
%In order to prove that the cut-and-slide operation (and its inverse) presented in Section \ref{sec:bij} is really a bijection, we will describe what happens to the different faces of the map during the operation (see Figure \ref{faces}). Thanks to the exploration, we can consider faces as words on the alphabet of side-edges (each face is described by the list of the side edges that lie inside it, ordered as they appear during the exploration). For any side-egde $e$, we will call $\overline{e}$ its opposite side-edge. By abuse of notation we may also refer to the edge $e$ that is the edge made of the side edges $e$ and $\overline{e}$, but we will stress on the fact that we are referring to an edge.
%Fix a planar map $M$. Let $v_0$ be a discovery vertex, $v_1$ its previous discovery vertex (if it exists), and so on, $v_{i+1}$ being the previous discovery vertex of $v_i$, as long as it exists. For all $i$, the discovery $v_i$ discovers the face $F_i$ while leaving face $F_{i+1}$. For all $i$, let $d_i$ be the discovery side-edge corresponding to $v_i$, that is $d_i$ sits in $F_{i+1}$ and $\overline{d_i}$ sits in $F_i$. Let $k$ be the smallest $i$ such that $v_i$ is a disconnecting discovery. For all $i$ between $1$ and $k$, we can set $F_i=\overline{d_i}A_id_{i-1}B_i$, that is $A_i$ are the side-edges of $F_i$ encountered before $d_{i-1}$ in the exploration, and $B_i$ are the the side-edges of $F_i$ encountered after $d_{i-1}$ in the exploration. We also set $F_0=\overline{d_0}A_0$ and $F_{k+1}=\overline{d_{k+1}}Cd_kB_{k+1}C'$ where $B_{k+1}$ is the word of side-edges of $F_{k+1}$ that appear between $d_k$ and the last corner around $v_k$.\\
%Now let us describe the cut and slide operation when $v_0$ is marked. First, for all $i<k$, all \textbf{edges} $d_i$ are opened into a bud $b_i$ and an stem $s_i$. The \textbf{edge} $d_k$ becomes a marked leaf $s_k$. Then $s_k$ becomes a stem, and $s_0$ becomes the marked leaf. Then $b_i$ is matched with $s_{i+1}$ to create and edge $e_i$. The map has been split into two distinct maps $M_1$ and $M_2$, now let us see what happened to the faces. In $M_1$, there is only one face that has been modified, it is the face of the marked vertex $v^*$, that we call $G^*$. It is straightforward to see that $G^*=\overline{d_{k+1}}CC'$ where the last corner of $v^*$ appears exactly between the end of $C$ and the beginning of $C'$. In $M_2$, the modified faces will be called $G_i$. We have $G_0=\overline{e_0}A_0s_0\overline{s_0}B_1$, $G_i=\overline{e_i}A_ie_{i-1}B_{i+1}$ and $G_k=A_ke_{k-1}B_{k+1}$. $G_k$ is the outer face of the second map, and for all $i$, $G_{i+1}$ is the previous face of $G_i$.\\
%\begin{figure}[!h]
%\centering
%\includegraphics[scale=1]{faces}
%\caption{What happens to the faces during the cut and slide operation. Marked objects are in purple, other discoveries involved are in gold. Blue contour materializes the $A_i$'s and red contour, the $B_i$'s}
%\label{faces}
%\end{figure}\\
%We must now prove that, for all $i<k$, the \textbf{edge} $e_i$ is a discovery that leaves $G_{i+1}$ and discovers $G_i$. We already now that $e_i$ lies in $G_{i+1}$ and $\overline{e_i}$ lies in $G_i$, we just have to prove that the \textbf{edge} $e_i$ is a discovery, i.e $e_i$ is the first side edge $e$ of $G_{i+1}$ such that $\overline{e}$ lies in $G_i$. Assume the contrary. There must be a side edge $f$ in $A_{i+1}$ such that $\overline{f}$ lies in $G_i$. There are two possibilities. Either $\overline{f}$ belongs to $A_i$, but then in the original map, in $F_{i+1}$, $f$ comes before $d_i$ and $\overline{f}$ lies in $F_i$, thus $d_i$ could not be the discovery, contradiction. Or $\overline{f}$ belongs to $B_{i+1}$, but then in the original map, in $F_{i+1}$ we see the side edges $f$, then $d_i$, then $\overline{f}$ in that order. But since we deal with planar maps, an edge which has both sides in the same same is a cut-edge (removing it disconnects the map). But then in that configuration, $d_i$ must be a disconnecting discovery (see Figure \ref{moche}). Indeed, let $M^*$ be the connected component containing $d_i$ that we obtain after removing $e$. Then $d_i$ would be a discovery in the map $M^*$ that leaves the outer face, thus disconnecting (because of Lemma \ref{lem}). This  is a contradiction, because $i<k$. We proved what we wanted. \\ 
%\begin{figure}[!h]
%\centering
%\includegraphics[scale=0.5]{cutedge}
%\caption{The impossibility of a cut-edge "surrounding" a non disconnecting-discovery}
%\label{moche}
%\end{figure}\\
%Knowing exactly what happens to the face and that the discoveries are in some sense "preserved" in enough to convince ourselves that both the cut and slide operation and its inverse work fine and are actually inverse applications of each other.
%
%\section*{The proof of Carell-Chapuy in the planar case}
%\label{sec:proof}
%We are now ready to prove the Carell-Chapuy formula in the planar case. We will prove it by induction on $n$, only knowing that $Q(0,f)=\mathbb{1}_{f=1}$.\\
%Taking the dual of Formula \ref{cut-slide}, we obtain the following formula, which will be helpful for the proof
%\begin{cor}
%\label{dual}
%\[(v-1)Q(n,f)=\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f+1\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)f_2Q(j,f_2).\]
%\end{cor}
%Starting with Formula \ref{cut-slide}, and applying Formula \ref{remy}, then in a second time applying Formula \ref{cut-slide} backwards, we obtain
%\begin{align*}
%(f-1)Q(n,f)=&(2n-1)Q(n-1,f-1)+2\sum_{\substack{i+j=n-2\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2)\\&+\sum_{\substack{i+j+k=n-2\\i,j,k\geq 0}}\sum_{\substack{f_1+f_2+f_3=f\\f_1,f_2,f_3\geq 1}}(2i+1)Q(i,f_1)v_2Q(j,f_2)v_3Q(k,f_3)
%\\&=(2n-1)Q(n-1,f-1)+2\sum_{\substack{i+j=n-2\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2)\\&+\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(f_1-1)Q(i,f_1)v_2Q(j,f_2).
%\end{align*}
%So summing Formula \ref{remy} to this
%\begin{align*}
%(n+1)Q(n,f)=&(2n-1)Q(n-1,f-1)+2\sum_{\substack{i+j=n-2\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2)\\&+\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(i+1)Q(i,f_1)v_2Q(j,f_2).
%\end{align*}
%Let \[S=\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(i+1)Q(i,f_1)v_2Q(j,f_2).\]
%We want to prove 
%\[S=(2n-1)Q(n-1,f-1)+\sum_{\substack{i+j=n-2\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2).\]
% We apply the recursion hypothesis
%\begin{align*}
%S&=\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2(2i-1)Q(i-1,f_1)+2(2i-1)Q(i-1,f_1-1))v_2Q(j,f_2)\\&+3\sum_{\substack{i+j+k=n-3\\k,l\geq 0}}\sum_{\substack{f_1+f_2+f_3=f\\f_1,f_2,f_3\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2)v_3Q(k,f_3)\\&+vQ(n-1,f-1).
%\end{align*}
%but, according to Formula \ref{cut-slide}, \[\sum_{\substack{i+j=n-1\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2(2i-1)Q(i-1,f_1-1))v_2Q(j,f_2)=2(f-2)Q(n-1,f-1),\]
%and 
%\begin{align*}
%&\sum_{\substack{i+j+k=n-3\\k,l\geq 0}}\sum_{\substack{f_1+f_2+f_3=f\\f_1,f_2,f_3\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2)v_3Q(k,f_3)\\&=\sum_{\substack{i+j=n-2\\i,j\geq 0}}\sum_{\substack{f_1+f_2=f\\\sf_1,f_2\geq 1}}(2i+1)Q(i,f_1)(f_2-1)Q(j,f_2).
%\end{align*}
%So
%\begin{align*}
%S=&(2(f-2)+v)Q(n-1,f-1)+\sum_{\substack{i+j=n-2}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)(2j+1)Q(j,f_2)\\&+\sum_{\substack{i+j=n-2}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)f_2Q(j,f_2).
%\end{align*}
%But using Corollary \ref{dual}, we have 
%\[\sum_{\substack{i+j=n-2}}\sum_{\substack{f_1+f_2=f\\f_1,f_2\geq 1}}(2i+1)Q(i,f_1)f_2Q(j,f_2)=(v-1)Q(n-1,f-1),\]
%which finishes the proof.

\end{document}
