\documentclass[finalversion]{FPSAC2020}
\articlenumber{11}
%\addbibresource{fpsac.bib}
\addbibresource{fpsac.bib}
\received{\today}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{color}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{coro}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{rmk}[thm]{Remark}
\crefname{section}{Section}{Sections}
\crefname{prop}{Proposition}{Propositions}


%\newcommand{\tdef}[1]{\textcolor{blue}{\emph{#1}}}
\newcommand{\tdef}[1]{\emph{#1}}

\newcommand{\horiz}{\begin{center}\rule{0.3\textwidth}{0.5pt}\end{center}}

\newcommand{\type}{\mathrm{Type}}

\newcommand{\sdd}{\mathrm{c}_{00}}
\newcommand{\sdu}{\mathrm{c}_{01}}
\newcommand{\suu}{\mathrm{c}_{11}}
\newcommand{\outdeg}{\mathrm{outdeg}}

\newcommand{\black}{\mathrm{black}}
\newcommand{\white}{\mathrm{white}}
\newcommand{\face}{\mathrm{face}}
\newcommand{\rcont}{\mathrm{rcont}}

\newcommand{\lnode}{\mathrm{lnode}}
\newcommand{\znode}{\mathrm{znode}}
\newcommand{\pnode}{\mathrm{pnode}}
\newcommand{\rlabel}{\mathrm{rlabel}}

\newcommand{\maptotree}{\mathbf{T}_\mathcal{M}}
\newcommand{\treetomap}{\mathbf{M}_\mathcal{T}}
\newcommand{\treetoint}{\mathbf{I}_\mathcal{T}}
\newcommand{\inttotree}{\mathbf{T}_\mathcal{I}}
\newcommand{\maptoint}{\mathbf{I}_\mathcal{M}}
\newcommand{\inttomap}{\mathbf{M}_\mathcal{I}}

\newcommand{\degtoedge}{\Lambda}
\newcommand{\id}{\mathrm{id}}

\title{Bijective link between Chapoton's new intervals and bipartite planar maps}

\author{Wenjie Fang\thanks{\href{mailto:wenjie.fang@u-pem.fr}{wenjie.fang@u-pem.fr}.}\addressmark{1}}

\address{\addressmark{1}LIGM, Univ. Gustave Eiffel, CNRS, Marne-la-Vall\'ee, France}

\received{\today}

\abstract{In 2006, Chapoton defined a class of Tamari intervals called ``new intervals'' in his enumeration of Tamari intervals, and he found that these new intervals are equinumerous with bipartite planar maps. We present here a direct bijection between these two classes of objects using a new object called ``degree tree''. Our bijection also gives an intuitive proof of an unpublished equi-distribution result of some statistics on new intervals given by Chapoton and Fusy.}

\resume{En 2006, Chapoton a d\'efini une classe d'intervalles de Tamari nomm\'es ``intervalles nouveaux'' dans son travail de comptage des intervalles de Tamari. Il a d\'ecouvert que ces intervalles nouveaux sont \'equi-\'enum\'er\'es avec les cartes planaires biparties. Nous proposons une bijection directe entre ces deux classes d'objets en utilisant un nouvel objet appel\'e ``arbre des degr\'es''. Notre bijection donne aussi une preuve intuitive d'un r\'esultat non publi\'e de Chapoton et Fusy sur l'\'equi-distribution de certains statistiques sur les intervalles nouveaux.}

\keywords{Bijection, Tamari lattice, new interval, bipartite planar map, degree tree}

\begin{document}

\maketitle

%\section{Introduction}

On classical Catalan objects, such as Dyck paths and binary trees, we can define the famous \emph{Tamari lattice}, first proposed by Tamari \cite{tamari-def}. This partial order was later found woven into the fabric of other more sophisticated objects. A notable example is diagonal coinvariant spaces, which have led to several generalizations of the Tamari lattice \cite{bergeron-preville,PRV}, and also incited the interest in intervals in such Tamari-like lattices. Recently, there is a surge of interest in the enumeration \cite{ch06,chatel-pons,nonsep} and the structure \cite{bernardi-bonichon,trinity} of different families of Tamari-like intervals. In particular, several bijective relations were found between various families of Tamari-like intervals and planar maps \cite{bernardi-bonichon,sticky,nonsep}. The current work is a natural extension of this line of research.

In \cite{ch06}, Chapoton introduced a subclass of Tamari intervals called \emph{new intervals}, which are irreducible elements in a grafting construction of intervals. Definitions of these objects and related statistics are postponed to the next section. The number of new intervals in the Tamari lattice of order $n \geq 2$ was given in \cite{ch06} as
\[
  \frac{3 \cdot 2^{n-2} (2n-2)!}{(n-1)!(n+1)!}.
\]
This is also the number of bipartite planar maps with $n-1$ edges. Furthermore, in a more recent unpublished result of Chapoton and Fusy (see \cite{fusy-talk}), a symmetry in three statistics on new intervals was observed then proven by identifying the corresponding generating function of new intervals with that of bipartite planar maps recording the numbers of faces, of black and of white vertices, and those are well-known to be equi-distributed. These results strongly hint a bijective link between the two classes of objects.

\begin{figure}
  \centering
  \includegraphics[page=1,width=\textwidth]{fig.pdf}
  \caption{Our bijections between bipartite planar maps, degree trees and new intervals}
  \label{fig:main-bij}
\end{figure}

In this article, we give a direct bijection between new intervals and bipartite planar maps (see \cref{fig:main-bij}) explaining the results above. Our bijection also generalizes a bijection on trees given in \cite{tree-bij} in the study of random maps. We have the following theorem.

\begin{thm} \label{thm:bij}
  There is a bijection $\maptoint$, with $\inttomap$ its inverse, such that, for a bipartite planar map $M$ with $n$ edges and $I = \maptoint(M)$, which is a new interval of size $n+1$, we have
  \[
    \white(M) = \sdd(I), \quad \black(M) = \sdu(I), \quad \face(M) = 1 + \suu(I).
  \]
  Here, $\black(M)$, $\white(M)$ and $\face(M)$ are the number of black vertices, white vertices and faces of $M$ respectively, while $\sdd(I)$, $\sdu(I)$ and $\suu(I)$ are some natural statistics on new intervals that we will define in \cref{sec:prelim}.
\end{thm}

These bijections use a new family of objects called \emph{degree trees}, and are in the same line as some previous work of the author \cite{sticky,nonsep}. While the symmetry in statistics of new intervals is known to Chapoton and Fusy \cite{fusy-talk}, our bijection intuitively captures this symmetry. Due to space limit, some proofs are omitted.  %It is particularly interesting to see how our bijections transform natural involutions on bipartite maps to new intervals.

\section{Preliminaries} \label{sec:prelim}

A \tdef{Dyck path} $P$ is a lattice path of up steps $u = (1,1)$ and down steps $d = (1, -1)$, starting from $(0,0)$, ending on the $x$-axis without falling below. The \tdef{size} (also called the \tdef{semilength}) of $P$ is half of its length. We denote by $\mathcal{D}_n$ the set of Dyck paths of size $n$. A \tdef{rising contact} of $P$ is an up step on the $x$-axis. We can also see $P$ as a word in $\{u,d\}$ whose prefixes all have at least as many up steps than down steps.

We now define the Tamari lattice as a partial order on $\mathcal{D}_n$ in the spirit of \cite{huang-tamari}. Given a Dyck path $P$ seen as a word, its $i$-th up step $u_i$ \tdef{matches} with a down step $d_j$ if the factor $P_i$ of $P$ strictly between $u_i$ and $d_j$ is a Dyck path. Clearly, there is a unique match for every $u_i$. We define the \tdef{bracket vector} $V_P$ of $P$ by taking $V_P(i)$ to be the size of $P_i$. The \tdef{Tamari lattice} of order $n$ is the partial order $\preceq$ on $\mathcal{D}_n$ where $P \preceq Q$ if and only if $V_P(i) \leq V_Q(i)$ for all $i$. See \cref{fig:def-int} for an example. A \tdef{Tamari interval} of size $n$ can be viewed as a pair of Dyck paths $[P, Q]$ of size $n$ with $P \preceq Q$.

\begin{figure}
  \centering
  \includegraphics[page=2,width=0.7\textwidth]{fig.pdf}
  \caption{An example of Chapoton's new interval with bracket vectors for both paths and related statistics.}
  \label{fig:def-int}
\end{figure}

In \cite{ch06}, Chapoton defined a subclass of Tamari intervals called ``new intervals''. Originally defined on pairs of binary trees, this notion can also be defined on pairs of Dyck paths (see \cite{fusy-talk}). The example in \cref{fig:def-int} is also a new interval. Given a Tamari interval $[P,Q]$, it is a \tdef{new interval} if and only if the following conditions hold:
\begin{itemize}
\item[(i)] $V_Q(1) = n - 1$;
\item[(ii)] For all $1 \leq i \leq n$, if $V_Q(i) > 0$, then $V_P(i) \leq V_Q(i+1)$.
\end{itemize}
We denote by $\mathcal{I}_n$ the set of new intervals of size $n \geq 1$.

We now define some statistics on new intervals. Given a Dyck path $P$ of size $n$, its \tdef{type} $\type(P)$ is a word $w$ such that, if the $i^{\rm th}$ up step $u_i$ is followed by an up step in $P$, then $w_i = 1$, otherwise $w_i = 0$. Since the last up step is always followed by a down step, we have $w_n = 0$. Note that our definition here is slightly different from that in, \textit{e.g.}, \cite{nonsep}, where the last letter is not taken into account. Given a new interval $I = [P,Q] \in \mathcal{I}_n$, if $\type(P)_i=1$ and $\type(Q)_i=0$, then we have $V_P(i) > 0 = V_Q(i)$, violating the condition for Tamari interval. Hence, we have only three possibilities for $(\type(P)_i, \type(Q)_i)$. We define $\sdd(I)$ (resp. $\sdu(I)$ and $\suu(I)$) to be the number of indices $i$ such that $(\type(P)_i, \type(Q)_i) = (0, 0)$ (resp. $(0,1)$ and $(1,1)$). \cref{fig:def-int} also shows such statistics in the example. We define the generating function $F_{\mathcal{I}} \equiv F_{\mathcal{I}}(t;u,v,w)$ of new intervals as
\begin{equation}
  \label{eq:int-gf}
  F_{\mathcal{I}}(t;u,v,w) = \sum_{n \geq 1} t^n \sum_{I \in \mathcal{I}_n} u^{\sdd(I)} v^{\sdu(I)} w^{\suu(I)}.
\end{equation}

For the other side of the bijection, a \tdef{bipartite planar map} $M$ is a drawing of a bipartite graph on a plane (in which all edges link a black vertex to a white one), defined up to continuous deformation, such that edges intersect only at their ends. Edges in $M$ cut the plane into \tdef{faces}, and the \tdef{outer face} is the infinite one. The \tdef{size} of $M$ is its number of edges; a map of size zero consists of only one black vertex. In the following, we only consider \emph{rooted} bipartite planar maps, which have a distinguished corner $c$ called the \tdef{root corner} of the outer face on a black vertex, called the \tdef{root vertex}. See the left part of \cref{fig:def-bip-tree} for an example. We denote by $\mathcal{M}_n$ the set of (rooted) bipartite planar maps of size $n$. %We allow the bipartite planar map of size $0$, which consists of only one black vertex.

\begin{figure}
  \centering
  \includegraphics[page=3,width=\textwidth]{fig.pdf}
  \caption{Left: an example of bipartite map. Right: an example of degree trees and the corresponding edge labels (zeros are omitted). Both with related statistics.}
  \label{fig:def-bip-tree}
\end{figure}

We now define the generating function $F_{\mathcal{M}} \equiv F_{\mathcal{M}}(t;u,v,w) $ of bipartite planar maps recording these statistics by
\begin{equation}
  \label{eq:bip-gf}
  F_{\mathcal{M}} \equiv F_{\mathcal{M}}(t;u,v,w) = \sum_{n \geq 0} t^n \sum_{M \in \mathcal{M}_n} u^{\black(M)} v^{\white(M)} w^{\face(M)}.
\end{equation}
It is well-known that $\black(M), \white(M), \face(M)$ are jointly equi-distributed in $\mathcal{M}_n$, meaning that $F_{\mathcal{M}}$ is symmetric in $u, v, w$. This can be seen with the bijection between bipartite maps and bicubic maps by Tutte \cite{tutte-census}.

To describe our bijection, we propose an intermediate class of objects called ``degree tree''. An example is given in the right part of \cref{fig:def-bip-tree}. %The meaning of this name will become clear under our bijection. 
We can also see degree trees as a variant of description trees (see \cite{desc-tree-tutte}). A \tdef{degree tree} is a pair $(T,\ell)$, where $T$ is a plane tree, and $\ell$ is a labeling function defined on nodes of $T$ such that
\begin{itemize}
\item If $v$ is a leaf, then $\ell(v)=0$;
\item If $v$ is an internal node with $k$ children $v_1, v_2, \ldots, v_k$, then $\ell(v) = k - a + \ell(v_1) + \ell(v_2) + \cdots + \ell(v_k)$, where $0 \leq a \leq \ell(v_1)$.
\end{itemize}
We observe that the leftmost child of a node $v$ is special when computing $\ell(v)$. This is different from the case of description trees. The size of a degree tree $(T,\ell)$ is the number of edges. We denote by $\mathcal{T}_n$ the set of degree trees $(T,\ell)$ of size $n$.

Given a degree tree $(T,\ell)$, we can replace $\ell$ by a labeling function on \emph{edges}. More precisely, for an internal node $v$, we label its leftmost descending edge (\textit{i.e.}, the edge to its leftmost child) by the value $a$ used in the computation of $\ell(v)$, and all other edges by $0$. We denote this edge labeling function by $\degtoedge(\ell)$. It is clear that $\degtoedge$ is an injection. Given $\lambda = \degtoedge(\ell)$, the vertex labeling $\ell$ can be easily recovered.

We also define several natural statistics on degree trees, illustrated in \cref{fig:def-bip-tree}, using its edge labeling. Let $(T,\ell)$ be a degree tree with $\lambda = \degtoedge(\ell)$, and $v$ a node in $T$. If $v$ is a leaf, then it is called a \tdef{leaf node}. Otherwise, let $e$ be the leftmost descending edge of $v$. If $\lambda(e)=0$, then $v$ is a \tdef{zero node}, otherwise it is a \tdef{positive node}. We denote by $\lnode(T,\ell)$, $\znode(T,\ell)$ and $\pnode(T,\ell)$ the number of leaf nodes, zero nodes and positive nodes in $(T,\ell)$ respectively. If $T \in \mathcal{T}_n$, we have $\lnode(T,\ell) + \znode(T,\ell)+\pnode(T,\ell) = n+1$.

\begin{lem} \label{lem:deg-tree}
  Let $(T,\ell)$ be a degree tree, and $\lambda = \degtoedge(\ell)$ the related edge labeling. We have
  \begin{enumerate}
  \item If $v$ has $m$ descendants, then $\ell(v) = m - \sum_{e \in T_v} \lambda(e)$, with $T_v$ the subtree induced by $v$;
  \item $\ell(v) \geq 0$, and $\ell(v)=0$ if and only if $v$ has no descendant.
  \end{enumerate}
\end{lem}
\begin{proof}[Proof sketch]
  We proceed by induction on the size of induced subtrees.
\end{proof}

\section{Degree trees and bipartite maps} \label{sec:tree-map}

Our bijection from bipartite maps to new intervals is relayed by degree trees, in which the related statistics are transferred. We start by the bijection from maps to trees.

\subsection{From bipartite maps to degree trees}

In \cite{tree-bij}, Janson and Stef\'ansson described a bijection between plane trees with $n$ nodes and $k$ leaves and plane trees with $n$ nodes in which $k$ of them are of even depth, giving another interpretation of Narayana numbers. We now introduce a bijection between $\mathcal{M}_n$ and $\mathcal{T}_n$, which can be seen as a generalization of the bijection in \cite{tree-bij}.

We first define a transformation $\maptotree$ from $\mathcal{M}_n$ to $\mathcal{T}_n$ for all $n$. Let $M \in \mathcal{M}_n$. If $n=0$, we define $\maptotree(M)$ to be the tree with one node. Otherwise, we perform the following exploration procedure to obtain a tree $T$ with a labeling $\lambda$ on its edges. In this procedure, we distinguish edges in $M$, which will be deleted one by one, and edges in $T$ that we add. We start from the root vertex, with the edge next to the root corner in clockwise order as the pending edge. Suppose that the current vertex is $u$ and the pending edge is $e_M$, which is always in $M$. We repeat two steps, \tdef{advance} and \tdef{prepare}, until termination. The advance step comes in the following cases illustrated in \cref{fig:map-bij}:
\begin{itemize}
\item[\textbf{(A1)}] If $e_M$ is a bridge to a vertex $v$ of degree $1$, then we delete $e_M$ in $M$ and add $e_T = e_M$ in $T$. The new current vertex is $u' = u$, and we define $\lambda(e_T) = 0$.
\item[\textbf{(A2)}] If $e_M$ is a bridge to a vertex $v$ of degree at least $2$, let $e_1$ be the edge adjacent to $v$ next to $e_M$ in clockwise order, and $w$ the other end of $e_1$. We draw a new edge $e_T$ in $T$ from $u$ to $w$ such that $e_M, e_1, e_T$ form a face with $u,v,w$ in counter-clockwise order. The next current vertex is $u' = w$. We delete $e_M$, and define $\lambda(e_T)=0$.
\item[\textbf{(A3)}] If $e_M$ is not a bridge, we split $u$ into $u_M$ and $u_T$, with $u_T$ taking all edges in $T$ and $u_M$ taking the rest. We add a new edge $e_T$ in $T$ from $u_M$ to $u_T$. Since $e_M$ is not a bridge, by planarity, it is between the outer face and a face of degree $2m$ with $m>0$. We define $\lambda(e_T) = m$ and delete $e_M$. The next current vertex is $u' = u_T$.
\end{itemize}
In the prepare step, let $u'$ be the new current vertex, which is adjacent to the new edge $e_T$. The next pending edge is the next remaining edge in $M$ starting from $e_T$ in the clockwise order around $u'$. If no such edge exists, we backtrack in the tree $T$ until finding a vertex $u''$ with such an edge $e_M''$, and we set $u''$ as the current vertex, and $e_M''$ the pending edge. If no such vertex exists, the procedure terminates, and we shall obtain a tree $T$ with an edge label function $\lambda$. We define $\maptotree(M)$ as the degree tree $(T, \degtoedge^{-1}(\lambda))$. See \cref{fig:map-bij} for an example of $\maptotree$. The bijection in \cite{tree-bij} is simply $\maptotree$ applied to a plane tree, where Case~(A3) never applies, and the degree tree $(T,\ell)$ obtained has $\lambda=0$ for all edges.

\begin{figure}
  \centering
  \includegraphics[page=4,width=0.9\textwidth]{fig.pdf}
  \caption{Cases in the advance step of $\maptotree$ and an example of the bijection $\maptotree$. Nodes in the same shaded pack come from the same vertex in the map.}
  \label{fig:map-bij}
\end{figure}

We now prove that $\maptotree(M)$ is well-defined. We start by describing the structure of the map in intermediate steps. The \tdef{leftmost branch} of a tree is the path starting from the root node and taking the leftmost descending edge at each node till a leaf.

\begin{lem} \label{lem:map2tree-struct}
  Let $M \in \mathcal{M}_n$ and $T = \maptotree(M)$. Let $M^+_i$ be the map after the $i$-th prepare step, with $u_i$ the current vertex and $e_i$ the pending edge. We denote by $T_i$ the partially constructed $T$ in $M^+_i$ , and by $M_i$ the remaining of $M$. Clearly $T_i$ and $M_i$ form a partition of edges in $M^+_i$.

  For every $i$, $T_i$ is a tree, and $M^+_i$ is $T_i$ with connected components of $M_i$ attached to the left of nodes on the leftmost branch of $T_i$, one component to only one vertex, with $u_i$ the deepest such vertex and $e_i$ its first edge in $M_i$ in clockwise order from the leftmost branch of $T_i$.
\end{lem}
\begin{proof}[Sketch of proof]
  We proceed by induction on $i$. It clearly holds when $i=0$, and we check that the properties are kept for each case of each step in the procedure of $\maptotree$.
\end{proof}

We now prove that trees obtained in $\maptotree$ are degree trees.

\begin{prop} \label{prop:map2tree}
  Given $M \in \mathcal{M}_n$, then $(T,\ell) = \maptotree(M)$ is a degree tree of size $n$.
\end{prop}
\begin{proof}[Proof sketch]
  By \cref{lem:map2tree-struct}, $T$ is a tree of size $n$, and the first time a node $u$ is explored, there is a component $M_u$ of remaining edges in $M$ attached to $u$. We prove by induction and case checking that the outer face of $M_u$ is of degree $2\ell(u)$, hence $(T,\ell) \in \mathcal{T}_n$.
\end{proof}

The transformation $\maptotree$ transfers some statistics from $\mathcal{M}_n$ to $\mathcal{T}_n$ as follows.

\begin{prop} \label{prop:map-bij-stat}
  Given $M \in \mathcal{M}_n$, let $(T,\ell) = \maptotree(M)$. We have
  \[
    \white(M) = \lnode(T,\ell), \quad \black(M) = \znode(T,\ell), \quad \face(M) = 1 + \pnode(T,\ell). 
  \]
\end{prop}
\begin{proof}
  By the definition of $\maptotree$, all leaves in $T$ are from white vertices, which are never split. Hence $\white(M) = \lnode(T,\ell)$. Then at each occurrence of Case~(A3), we lost a face but gain a positive node in $T$, thus $\face(M) = 1 + \pnode(T,\ell)$, with $1$ for the outer face. Now for $\black(M) = \znode(T,\ell)$, we note that a new black vertex in $M$ is reached only in Case~(A2), which leads to a zero edge.
\end{proof}

\subsection{From degree trees to bipartite maps}

We now define a transformation $\treetomap$ from $\mathcal{T}_n$ to $\mathcal{M}_n$. Let $(T,\ell) \in \mathcal{T}_n$ and $\lambda = \degtoedge(\ell)$. We now perform a procedure that deals with nodes in $T$ in postorder (\textit{i.e.}, first visit the subtrees induced by children from left to right, then the parent). For each node $u$, let $u^*$ be its parent and $e_u$ the edge between $u$ and $u^*$. By construction, when we deal with $u$, its induced subtree has already been dealt with and transformed into a bipartite planar map $M_u$ attached to $u$. We have three cases, illustrated in \cref{fig:map-bij-inv}.
\begin{itemize}
\item \textbf{Case~(A1')}: If $u$ is a leaf, then we delete $e_u$ from $T$ and add it to $M$.
\item \textbf{Case~(A2')}: If $u$ is not a leaf but $\lambda(e_u) = 0$, let $e'$ be the edge next to $e_u$ around $u$ in counterclockwise order, and $v$ the other end of $e'$. As $M_u$ is bipartite, $v \neq u$. We add a new edge $e_M$ from $u^*$ to $v$ such that the triangle formed by $e_u, e', e_M$ has vertices $u^*, u, v$ in clockwise order, without any edge inside. We then delete $e_u$.
\item \textbf{Case~(A3')}: If $\lambda(e_u) > 0$, let $d$ be the degree of the outer face of $M_u$. If $2 \lambda(e_u) \geq d$, then the procedure fails. Otherwise, we start from the corner of $M_u$ to the right of $e_u$ and walk clockwise along edges for $2 \lambda(e_u) - 1$ times to another corner, and we connect the two corners by a new edge $e_M$ in $M$, making a new face of degree $2\lambda(e_u)$. The component remains planar and bipartite. We finish by contracting $e_u$.
\end{itemize}
In the end, we obtain a planar bipartite map $M$ with the same root corner as $T$. We define $\treetomap(T,\ell) = M$. We see that (A1'), (A2') and (A3') are exactly the opposite of (A1), (A2), (A3) in the definition of $\maptotree$.

\begin{figure}
  \centering
  \includegraphics[page=5,width=0.9\textwidth]{fig.pdf}
  \caption{Cases in the procedure of $\treetomap$, and an example of $\treetomap$}
  \label{fig:map-bij-inv}
\end{figure}

\begin{prop} \label{prop:tree2map-defined}
  Given $(T,\ell)$ a degree tree, for a node $u \in T$, let $M_u$ be the map obtained in the procedure of $\treetomap(T,\ell)$ from the subtree $T_u$ induced by $u$. Then the degree of the outer face of $M_u$ is $2\ell(u)$, and the procedure never fails.
\end{prop}
\begin{proof}[Proof sketch]
  We proceed by induction on $u$ in reverse postorder with case checking.
\end{proof}

\begin{prop} \label{prop:tree2map-valid}
  For $(T,\ell)$ a degree tree, $M = \treetomap(T,\ell)$ is a bipartite planar map.
\end{prop}
\begin{proof}
  Planarity is easily checked through the definition of $\treetomap$. Faces in $M$ are only created in Case~(A3'), thus all even. Along with planarity, $M$ is bipartite.
\end{proof}

It is also clear that $\treetomap$ is the inverse of $\maptotree$.

\begin{prop} \label{prop:map-tree-bij}
  The transformation $\maptotree$ is a bijection from $\mathcal{M}_n$ to $\mathcal{T}_n$, with $\treetomap$ its inverse.  
\end{prop}
\begin{proof}[Proof sketch]
  By \cref{prop:map2tree,prop:tree2map-valid}, we only need to prove that $\treetomap$ is the inverse of $\maptotree$. It is clear from definitions that $\maptotree \circ \treetomap = \id_{\mathcal{T}}$. To show that $\treetomap \circ \maptotree = \id_{\mathcal{M}}$, the only case to check is Case~(A2) of $\maptotree$. However, by planarity, there is only one way to revert Case~(A2) by creating a face, which is exactly Case~(A2') in $\treetomap$.
\end{proof}

\section{Degree trees and new intervals} \label{sec:tree-int}

We now relate degree trees to new intervals, which also explains the conditions of new intervals in terms of trees.

\subsection{From degree trees to new intervals} \label{sec:tree-int-1}

Given $(T,\ell) \in \mathcal{T}_n$, let $\lambda = \degtoedge(\ell)$. We define a transformation $\treetoint$ from degree trees to new intervals by constructing a new interval $[P,Q]$ from $(T,\ell)$. We first introduce a classical bijection between plane trees and Dyck paths. Given the plane tree $T$, to get a Dyck path $Q'$, we perform a \emph{preorder traversal} (parent first, then subtrees from left to right) of $T$, and append $u$ (resp. $d$) to $Q'$ each time we move away from (resp. closer to) the root. This is a bijection. We then take $Q = uQ'd$. For $P$, we first assign to every node a \tdef{certificate}. We process nodes in $T$, initially all colored black, in the \emph{reverse order} of the preorder of $T$. At the step for a node $v$, if $v$ is a leaf, then its certificate is itself. Otherwise, we visit nodes after $v$ in preorder, and color each visited black node by red, stopping at some node $w$ just before the $(\lambda(e)+1)$-st black node, where $e$ is the leftmost descending edge of $v$. We take $w$ as the certificate of $v$. When $\lambda(e)=0$, we take $w=v$. We now define a \tdef{certificate function} $c$ on vertices of $T$ similar to those in \cite{sticky,nonsep}, with $c(w)$ the number of nodes with $w$ as certificate. The path $P$ is given by concatenation of $ud^{c(v)}$ for all nodes $v$ in preorder. We then define $\treetoint(T,\ell) = [P,Q]$. See an example of $\treetoint$ in \cref{fig:int-bij}.

\begin{figure}
  \centering
  \includegraphics[page=6,width=\textwidth]{fig.pdf}
  \caption{Example of the bijection $\treetoint$ on a degree tree represented by its edge labeling. The middle shows the certificate of each node.}
  \label{fig:int-bij}
\end{figure}

To prove that $\treetoint(T,\ell)$ is a new interval, we start by some properties of certificates.

\begin{lem} \label{lem:tree-cert}
  Let $(T,\ell)$ be a degree tree of size $n$. For a node $v \in T$, let $w$ be the certificate of $v$. Then either $w = v$, or $w$ is a descendant of $v$ in the leftmost subtree $T_*$ of $v$. In the latter case, $w$ is not the last node of $T_*$ in preorder.
\end{lem}
\begin{proof}[Proof sketch]
  We proceed by induction on nodes in the reverse preorder. The base case is a leaf, thus trivial. For the induction step, \cref{lem:deg-tree} ensures that, at the process step of each node, there are enough black vertices in the leftmost subtree to color.
\end{proof}

\begin{lem} \label{lem:cert-parenthesis}
  Let $(T,\ell)$ be a degree tree, and $v, v'$ two distinct nodes in $T$ with $w, w'$ their certificates respectively. Suppose that $v$ precedes $v'$ in the preorder. Then $w$ cannot be strictly between $v'$ and $w'$ in the preorder. Furthermore, if $v' \neq w'$, then $w \neq v'$.
\end{lem}
\begin{proof}
  We only need to consider the case $v \neq w$ and $v' \neq w'$, as other cases are trivial. In the coloring process, since $v$ precedes $v'$ in the preorder, $v'$ is treated before $v$. By construction, in the coloring process, after the step for $v'$, the nodes between $v'$ to $w'$ (excluding $v'$ but including $w'$) are all colored red. Therefore, in the process step for $v$, the visit will not stop strictly between $v'$ and $w'$, nor at $v'$, as such a stop requires a succeeding black node. Hence, $w$ is not strictly between $v'$ and $w'$, and $w \neq v'$.
\end{proof}

Note that in the lemma above, we can have $w = v'$ when $v' = w'$.

\begin{prop} \label{prop:tree2int}
  Let $(T,\ell) \in \mathcal{T}_n$. Then $[P,Q] = \treetoint(T,\ell)$ is a new interval in $\mathcal{I}_{n+1}$.
\end{prop}
\begin{proof}[Proof sketch]
  $Q$ is clearly a Dyck path. $P$ is a Dyck path since a node never comes after its certificate in preorder by \cref{lem:tree-cert}. Let $v_i$ be the $i$-th node in preorder in $T$. $V_Q(i)$ is the size of the subtree $T_i$ induced by $v_i$. The case $V_Q(i)=0$ is trivial. Suppose that $V_Q(i) > 0$. By \cref{lem:cert-parenthesis}, steps in $V_P(i)$ are generated by nodes from after $v_i$ till its certificate, which is in the subtree induced by the first child of $v_i$ if $V_Q(i) > 0$, and this child is the $(i+1)$-st node in preorder. We thus have $V_P(i) \leq V_Q(i+1) < V_Q(i)$.
\end{proof}

We also have the following property of a new interval obtained via $\treetoint$.

\begin{prop} \label{prop:tree-edge-contact}
  For a degree tree $(T,\ell)$ with $\lambda = \degtoedge(\ell)$, let $I = [P,Q] = \treetoint(T,\ell)$. For an internal node $v \in T$, let $e$ be the edge linking $v$ to its leftmost child $v'$. Let $P_v$ be the subpath of $P$ strictly between the up step contributed by $v$ in $P$ and its matching down step. Then the number of rising contacts in $P_v$ as a Dyck path is $\lambda(e)$.
\end{prop}

\subsection{From new intervals to degree trees}

We now define a transformation $\inttotree$ for the reverse direction. Let $I = [P,Q] \in \mathcal{I}_{n+1}$ be a new interval. Since $V_Q(1) = n$, we can write $Q = uQ'd$. We first construct a plane tree $T$ of size $n$ from $Q'$ with the classic bijection described at the beginning of \cref{sec:tree-int-1}. Now, let $v_1, \ldots, v_{n+1}$ be the nodes of $T$ in preorder. $V_Q(i)$ is the size of the subtree induced by $v_i$. We now define an edge labeling $\lambda$ of $T$. If $e$ is the left-most descending edge of $v_i$, then we take $\lambda(e)$ the number of rising contacts in $P_i$, with $P_i$ the subpath of $P$ strictly between the $i$-th up step and its matching down step. Otherwise, we take $\lambda(e) = 0$. Let $\ell = \degtoedge^{-1}(\lambda)$. We define $\inttotree(I) = (T, \ell)$. An example of $\inttotree$ is given in \cref{fig:int-bij-inv}. 

\begin{figure}
  \centering
  \includegraphics[page=7,width=\textwidth]{fig.pdf}
  \caption{Example of the bijection $\inttotree$ on a new interval $I = [P,Q]$}
  \label{fig:int-bij-inv}
\end{figure}

\begin{prop} \label{prop:int2tree}
  Let $I = [P,Q] \in \mathcal{I}_{n+1}$, then $(T,\ell) = \inttotree(I)$ is a degree tree of size $n$.
\end{prop}
\begin{proof}[Proof sketch]
  Let $\lambda = \degtoedge(\ell)$. Suppose that the $j$-th node $v_j$ of $T$ in preorder is not a leaf. By the conditions of new intervals, the steps counted in $V_P(j)$ are all in the leftmost subtree of $v_j$. We thus check that $(T,\ell)$ satisfies the conditions of degree trees.
\end{proof}

%Some natural statistics are transferred from new intervals to degree trees via $\inttotree$.

\begin{prop} \label{prop:int-bij-stat}
  Given $I = [P,Q] \in \mathcal{I}_{n+1}$, let $(T,\ell) = \inttotree(I)$. We have
  \[
    \sdd(I) = \lnode(T,\ell), \quad \sdu(I) = \znode(T,\ell), \quad \suu(I) = \pnode(T,\ell).
  \]
\end{prop}
\begin{proof}
  Let $v_i$ be the $i$-th node of $T$ in preorder. By the definition of $\inttotree$, the node $v_i$ is a leaf if and only if $\type(Q)_i=0$. Hence, $\sdd(I) = \lnode(T,\ell)$. Moreover, if $v_i$ is an internal node, then $\type(P)_i=0$ if and only if $\lambda(e_i) = 0$, where $e_i$ is the leftmost descending edge of $v_i$, and $\lambda=\degtoedge(\ell)$. We thus conclude for the other equalities.
\end{proof}

Using \cref{prop:tree-edge-contact}, we check that $\treetoint$ and $\inttotree$ are bijections.

\begin{prop} \label{lem:int-tree-bij}
  $\treetoint$ is a bijection from $\mathcal{T}_n$ to $\mathcal{I}_{n+1}$ for any $n \geq 0$, with $\inttotree$ its inverse.
\end{prop}

\section{Symmetries and structure} \label{sec:sym}

With the bijections in \cref{sec:tree-map,sec:tree-int}, we construct the bijections in our main result.

\begin{proof}[Proof of \cref{thm:bij}]
  We take $\maptoint = \treetoint \circ \maptotree$ and $\inttomap = \treetomap \circ \inttotree$, valid by \cref{prop:map-tree-bij,lem:int-tree-bij}. The equalities of statistics come from \cref{prop:map-bij-stat,prop:int-bij-stat}.
\end{proof}

\begin{coro} \label{coro:stats-sym}
  The generating functions $F_\mathcal{I}$ and $F_\mathcal{M}$ are related by $t F_\mathcal{M} = w F_\mathcal{I}$. In particular, the series $w F_\mathcal{I}$ is symmetric in $u, v, w$.
\end{coro}
\begin{proof}
  The equality is a direct translation of \cref{thm:bij} in generating functions. The symmetry of $w F_\mathcal{I}$ comes from that of $F_\mathcal{M}$.
\end{proof}

As mentioned before, the symmetry in $\sdd, \sdu, \suu$ was already known to Chapoton and Fusy, and a proof was outlined in \cite{fusy-talk}, using recursive decompositions of new intervals \cite[Lemma~7.1]{ch06} and bipartite planar maps. Our bijective proof can be seen as a direct version of that proof, as degree trees are canonical descriptions of both decompositions. 

\acknowledgements{The author thanks \'Eric Fusy for many inspiring discussions. The author also thanks the anonymous referees for their precious comments. Part of the present work was done at TU Graz supported by the Austrian Science Fund (FWF) grants P27290 and I2309-N35.}

\printbibliography


\end{document}
