%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{amsart}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[colorlinks,citecolor=blue]{hyperref}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric,calc}
\usepackage[all]{xy}
%\usepackage[english]{babel}

%\usepackage{amsfonts}
%\usepackage{amscd}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% theoremes

\newtheorem{theorem}{Theorem}[section] 
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{lemma}[theorem]{Lemma} 


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark} 
\newtheorem{example}[theorem]{Example} 
\newtheorem{problem}[theorem]{Problem} 
\newtheorem{algorithm}[theorem]{Algorithm}
 
%\newenvironment{proof}{\begin{trivlist}\item{\bf{Proof.}}}
%  {\hfill\rule{2mm}{2mm}\end{trivlist}}

% commandes
\newenvironment{psmallmatrix}
  {\left(\begin{smallmatrix}}
  {\end{smallmatrix}\right)}
  
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}

\newcommand{\TA}{\mathbb{A}}
\newcommand{\TB}{\mathbb{B}}
\newcommand{\TC}{\mathbb{C}}
\newcommand{\TD}{\mathbb{D}}
\newcommand{\TE}{\mathbb{E}}
\newcommand{\TyH}{\mathbb{H}}
\newcommand{\TI}{\mathbb{I}}
\newcommand{\ir}{\mathrm{ir}}
\newcommand{\id}{\mathrm{dr}}

\newcommand\bleu[1]{%
  \tikz[baseline=(X.base)] 
    \node (X) [draw, shape=circle, color=blue, inner sep=0] {\strut $#1$};}

\newcommand\rouge[1]{%
  \tikz[baseline=(X.base)] 
    \node (X) [draw, shape=circle, color=red, inner sep=0] {\strut $#1$};}

\newcommand\bleuA[2]{%
\tikz[baseline=(X.base), grow=up, level distance=6mm]
    \node[circle, draw, color=blue, inner sep=0] (X) {\strut $#1$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#2$}};
}

\newcommand\rougeA[2]{%
\tikz[baseline=(X.base), grow=up, level distance=6mm]
    \node[circle, draw, color=red, inner sep=0] (X) {\strut $#1$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#2$}};
}

\newcommand\bleuB[3]{%
\tikz[baseline=(X.base), grow=up, level distance=6mm]
    \node[circle, draw, color=blue, inner sep=0] (X) {\strut $#1$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#2$}}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#3$}};
}

\newcommand\rougeB[3]{%
\tikz[baseline=(X.base), grow=up, level distance=6mm]
    \node[circle, draw, color=red, inner sep=0] (X) {\strut $#1$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#2$}}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#3$}};
}

\newcommand\bleuC[3]{%
\tikz[baseline=(X.base), grow=up, level distance=6mm]
    \node[circle, draw, color=blue, inner sep=0] (X) {\strut $#1$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#2$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#3$}}};
}

\newcommand\rougeC[3]{%
\tikz[baseline=(X.base), grow=up, level distance=6mm]
    \node[circle, draw, color=red, inner sep=0] (X) {\strut $#1$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#2$}
    child {node[circle, draw, color=red, inner sep=0] {\strut $#3$}}};
}

\newcommand{\x}{{\color{blue} x}}
\newcommand{\y}{{\color{blue} y}}
\newcommand{\z}{{\color{blue} z}}

\newcommand{\el}{{\color{red} \ell}}
\newcommand{\m}{{\color{red} m}}
\newcommand{\n}{{\color{red} n}}


\newcommand{\kk}{\mathbf{k}}
\newcommand{\FYk}{\mathcal{F}_{Y_n,k}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cam}{\operatorname{Cambrian}}
\newcommand{\nest}{\operatorname{NonNesting}}
\newcommand{\Tam}{\operatorname{Tam}}
\newcommand{\Ri}{\operatorname{Ra}}
\newcommand{\Fa}{\operatorname{Low}}
\newcommand{\NC}{\operatorname{NC}}

\title{Exceptional and modern intervals of the Tamari lattice}
\author{Baptiste Rognerud}

\thanks{The author has been supported by the IDEX BMM/PN/AM/N\textsuperscript{o} 2016-096c.}
%\date{\today}
\date{}

\setlength{\textwidth}{15.6cm}
\addtolength{\textheight}{2cm}

%%%%%%%%%%%%%%%% pour centrer dans des tableaux. 
\usepackage{array}
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}

\begin{document}

%%%%%%%%%%%%%%

\begin{abstract}
In this article we use the theory of interval-posets recently introduced by Ch\^atel and Pons in order to describe some interesting families of intervals in the Tamari lattices. These families are defined as interval-posets avoiding specific configurations. At first, we consider \emph{exceptional} interval-posets and we show that they correspond to the intervals which are obtained as images of \emph{non-crossing trees} in the Dendriform operad. We also show that the exceptional intervals are exactly the intervals of the Tamari lattices induced by intervals in the posets of \emph{non-crossing partitions}. In the second part, we introduce the notion of \emph{modern} and \emph{infinitely modern} interval-posets. We show that the modern intervals are in bijection with the \emph{new} intervals of the Tamari lattices in the sense of Chapoton. Finally, we consider the family of \emph{infinitely modern} intervals and we prove that there are as many infinitely modern interval-posets of size $n$ as there are \emph{ternary trees} with $n$ inner vertices. 
 \end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 79 \rms (2020), Article~B79d\hfill}
\def\thepage{}


\section{Introduction}

The family of the Tamari lattices is extremely rich from the point of view of combinatorial algebra. It has two main interpretations as posets of type $A$.  First, the Tamari lattice on the set of binary trees with $n$ inner vertices, denoted by $\Tam_n$, is isomorphic to the poset of tilting modules over a linearly oriented quiver of type $A_n$ (see \cite{buan_krause} and \cite{happel_tilting} for more details. A bijection between tilting modules and binary trees was already defined by Gabriel \cite{gabriel}). On the other hand, it is part of the Cambrian lattices of type $A_{n-1}$ (see \cite{reading} for more details). Finally, let $\mathrm{DW}_{n}$ be the distributive lattice of upper ideals in the poset of positive roots of the root system of type $A_{n-1}$. Then the Tamari lattice $\Tam_n$ is conjecturally deeply related to $\mathrm{DW}_{n}$ (see  
\cite[Conjecture~$5.3$]{chapoton_modules} for more details). 

As another intriguing feature of this lattice, we have its poset of intervals. It was proved by Chapoton that there is a beautiful formula for the number of intervals in the Tamari lattice:
\[
\hbox{number of intervals in $\Tam_n = $} \frac{2(4n+1)!}{(n+1)!(3n+2)!}. 
\] 
It is remarkable that this formula has such a simple factorized form. More recently, in \cite{chapoton_interval}, Chapoton associated to any finite poset $P$ a polynomial in $4$ variables that enumerates the intervals of $P$ and he proved that the polynomial of the Tamari lattice has a very particular behavior (this particular behavior is not shared with generic posets). 

In this article, we continue to investigate the set of intervals of the Tamari lattices. We use the theory of interval-posets introduced by Ch\^atel and Pons in \cite{pons_chatel} in order to study two families of intervals. As intervals of the Tamari lattice, they seem to have a rather complicated and unnatural description. However,  they have a very simple description in terms of interval-posets \emph{avoiding specific configurations}.

In the first part of the article, we consider the family appearing as images of \emph{non-crossing} trees in the dendriform operad. These objects were introduced by Chapoton in \cite{chapoton_mould}, and it was proved in \cite{chapoton_etal_mould} that they are intervals in the Tamari lattice. In Theorem~\ref{image_noncrossing}, we complete this result by giving a precise description of these intervals in terms of interval-posets. This description is used in another article, providing a proof of Conjecture~$3.1$ of \cite{chapoton_modules} (see \cite{rognerud_cyf} for more details). By construction, these intervals are in bijection with the non-crossing trees. In particular, in the Tamari lattice of size $n$, there are $\frac{1}{2n+1} {\binom{3n}{n}}$ such intervals. We call them \emph{exceptional} because they are also in bijection with the set of exceptional sequences (up to an equivalence relation) in the bounded derived category of a linearly oriented quiver of type $A$ (see \cite{araya} and \cite[Section~$3$]{chapoton_stokes} for more information). We would need to introduce too many algebraic objects to really explain what we have in mind here, but we expect this relation with the exceptional sequences to be much more than a bijection. 

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL BAPTISTE ROGNERUD}{\SMALL EXCEPTIONAL AND MODERN INTERVALS
OF THE TAMARI LATTICE}


At an elementary level, the exceptional intervals turn out to have another nice description in terms of \emph{non-crossing partitions}. It is well-known that the Tamari lattice is a refinement of the poset of non-crossing partitions. More precisely, if $\mathrm{NC}_n$ denotes the poset of non-crossing partitions of size $n$, then there is an increasing bijection $\phi : \mathrm{NC}_n \to \Tam_n$ (a bijective homomorphism of posets). In Theorem~\ref{theo_nc}, we prove that an interval of $\Tam_n$ is of the form $[\phi(\pi_1),\phi(\pi_2)]$ for an interval $[\pi_1,\pi_2]$ of non-crossing partitions if and only if it is exceptional. 

In the second part of the article, we consider the family of \emph{new intervals} of the Tamari lattices. It was shown by Chapoton that there is a structure of operad on the set of intervals of the Tamari lattice (see \cite{chapoton_interval} for more details). The new intervals are exactly the intervals that cannot be obtained as compositions of smaller intervals. There is also a nice formula for the number of such intervals:

\[ \hbox{number of new intervals in $\Tam_n$ }= 3 \cdot \frac{2^{n-2}(2n-2) !}{(n-1) ! (n+1) !}.\]

In Section~$4$, we find the description of the interval-poset corresponding to a new interval and we deduce an intrinsic characterization of these intervals. Our main tool is what we call the \emph{raise} of an interval-poset. This operation increases the size of an interval-poset by $1$, and shifts by $1$ all the increasing relations of the poset. After shifting the increasing relations by $1$, the result is not necessarily a poset since the new increasing relations may contradict the decreasing ones. In order to avoid this problem, we introduce the family of \emph{modern interval-posets} and show that they are exactly the interval-posets for which the raise is also an interval-poset. Then we prove that an interval is \emph{new} if and only if its interval-poset is \emph{the raise} of a \emph{modern interval-poset}. In terms of binary trees, the raise sends an interval $[S_1,T_1]$ to the interval $[S,T]$ where $S$ (respectively $T$) is obtained by grafting the root of $S_1$ (respectively $T_1$) on the first (respectively second) leaf of the unique binary tree of size $1$ denoted by $Y$. 


In the last section, we consider the interval-posets for which all the successive raises are interval-posets. We call them \emph{infinitely modern}. It seems that this family of intervals has not been considered before. Using a double statistic on the set of interval-posets, we recover the triangular decomposition of the Fuss--Catalan number $\frac{1}{2n+1} {\binom{3n}{n}}$ introduced by Aval in \cite{aval}. As corollary, we prove in Theorem~\ref{theo_inf} that there are as many infinitely modern interval-posets of size $n$ as there are ternary trees with $n$ inner vertices.

\paragraph{Acknowledgement}
This work was done when I was a postdoc at the University of Strasbourg and I am grateful to Fr\'ed\'eric Chapoton for introducing me to this subject, for his support, his comments and the many things he taught me. I am also grateful to Camille Combe for the many discussions about the last part of this article. I am very grateful to the referee for the careful reading of this paper. 

\section{Interval-posets, intervals of the Tamari lattices and conventions}\label{section1}

In this section, we recall the construction of \emph{interval-posets} of Ch\^atel and Pons introduced in \cite{pons_chatel} and we recall that they are in bijection with the intervals of the Tamari lattice. One should note that this bijection is not canonical. More precisely, it depends on the various choices that one has to make in order to define the Tamari lattices as partial orders on sets of binary trees. This is why we start by carefully stating our conventions. 


Let $n\in \mathbb{N}$. A (planar) binary tree of size $n$ is a graph embedded in the plane which is a tree, has $n$ vertices with valence $3$, $n+ 2$ vertices with valence $1$ and a distinguished univalent vertex called the \emph{root}. The other vertices of valence $1$ are called the \emph{leaves} of the tree. For the rest of the paper, when we speak about vertices of the tree, we have in mind the trivalent vertices. The planar binary trees are pictured with their root at the bottom and their leaves at the top. 


With this fixed convention, we can speak about \emph{left} and \emph{right} children of a vertex of a binary tree $T$. For us the child of a vertex is connected to his parent by a single edge. A \emph{descendant} is a child, grandchild, great-grandchild, and so on. If $v$ is a vertex of $T$, we let $T_1$ (respectively $T_2$) be the subtree with root the left child (respectively right child) of $v$. We say that $T_1$ (respectively $T_2$) is the left subtree (respectively right subtree) of $v$. 

Let $\Tam_n$ be the set of all binary trees with $n$ vertices. It is well-known that the cardinality of this set is the Catalan number $c_n = \frac{ 1 }{n+1} {\binom{2n}{n}}$. 

There is a partial order relation on $\Tam_n$ which was introduced by Tamari in \cite{tamari}. It is defined as the transitive closure of the following covering relations. A tree $T$ is covered by a tree $S$ if they only differ in some neighborhood of an edge by replacing the configuration $\begin{tikzpicture}[scale = 0.1]
        \draw (0,0)--(2,2); \draw (0,0)--(-2,2); \draw (-1,1)--(0,2);
\end{tikzpicture}$ in $T$ by the configuration  $\begin{tikzpicture}[scale = 0.1]
        \draw (0,0)--(2,2); \draw (0,0)--(-2,2); \draw (1,1)--(0,2);
\end{tikzpicture}$ in $S$. The poset $\Tam_n$ is known to be a lattice. 

A binary \emph{search tree} is a binary tree labeled by integers such that, if a vertex $x$ is labeled by $k$, then the vertices of the left subtree (respectively right subtree) of $x$ are labeled by integers  less than or equal (respectively superior) to $k$. 

If $T$ is a binary tree with $n$ vertices, there is a unique labeling of the vertices by each of the integers $1,2,\dots, n$ that makes it a binary search tree. This procedure is sometimes called the \emph{in-order traversal} of the tree or simply as the in-order algorithm (recursively visit left subtree, root and right subtree). The first vertex visited by the algorithm is labeled by $1$, the second by $2$ and so on. See figure~\ref{fig_inorder} for an example. Since this labeling is canonical, we will allow ourself to identify vertices with their label. 


Using this labeling, a binary tree $T$ with $n$ vertices induces a partial order relation $\lhd$ on the set $\{1,2,\dots, n\}$ by setting $i \lhd j$ if and only if the vertex labeled by $i$ is in the subtree with root $j$. 

When $(P,\lhd)$ is a partial order on the set $\{1,2,\dots, n\}$, one can use the natural total ordering of the integers $1,2,\dots, n$, which we denote by $<$, to split the relations $\lhd$ in two families. Let $a,b$ be two integers with $1 \leqslant a < b \leqslant n$. If $a \lhd b$ we say that the relation is \emph{increasing}.  On the other hand, if $b\lhd a$, we say that the relation is \emph{decreasing}. We denote the sets of decreasing and increasing relations of $P$ by $\mathrm{Dec}(P)$ and $\mathrm{Inc}(P)$, respectively. 

There is a particularly nice way to draw such a poset $(P,\lhd)$. If a relation $i \lhd j$ is increasing, draw a (red) arrow from $i$ to $j$ under the integers $i,i+1,\dots, j$. If there is a decreasing relation $j \lhd i$ draw a (blue) arrow from $j$ to $i$ over the integers $j,j-1,\dots, i$. See Figure~\ref{fig_inorder} for an example. 



\begin{figure}[h]
\centering
\begin{tikzpicture}[scale =1]
\node (a) at (0,0) {5};
\node (c) at (-1.5,2.5) {3};
\node (b) at (-2,2) {1};
\node (d) at (-2.5,3.5) {2};
\node (e) at (-0.5, 3.5) {4};
\node (f) at (2.5, 2.5) {8};
\node (g) at (2,3) {6} ; 
\node (h) at (2.5,3.5) {7};
\node (1) at (-4,4) {}; \node (2) at (-3,4) {}; \node (3) at (-2,4) {}; \node (4) at (-1,4) {}; \node (5) at (0,4) {}; \node (6) at (1,4) {}; \node (7) at (2,4) {}; \node (8) at (3,4) {}; \node (9) at (4,4) {}; 
\draw (a)--(b)--(1)
	  (b)--(c)--(e) -- (5)
	  (e)--(4)
	  (c)--(d)--(2)
	  (d)--(3)
	 (a)--(f)--(9)
	 (f)--(g)--(6)
	 (g)--(h)--(7)
	 (h)--(8);
\end{tikzpicture}
\begin{tikzpicture}
\node (1) at (-4,4) {1}; \node (2) at (-3,4) {2}; \node (3) at (-2,4) {3}; \node (4) at (-1,4) {4}; \node (5) at (0,4) {5}; \node (6) at (1,4) {6}; \node (7) at (2,4) {7}; \node (8) at (3,4) {8};
\draw[red,->,below,thick] (2.south) to [out=-45,in=225] (3.south);
\draw[red,->,below,thick] (1.south) to  [out=-90,in=-90] (5.south);
\draw[red,->,below,thick] (6.south) to  [out=-50,in=230] (8.south);
\draw[blue,thick,->] (3.north) to  [out=140,in=50] (1.north);
\draw[blue,thick,->] (4.north) to  [out=135,in=30] (3.north);
\draw[blue,thick,->] (7.north) to  [out=135,in=45] (6.north);
\draw[blue,thick,->] (8.north) to  [out=100,in=80] (5.north);
\end{tikzpicture}
\caption{On the left, an example of the labeling of the vertices of a binary tree by calling the `in-order' algorithm. On the right, the poset induced by the tree.}\label{fig_inorder}
\end{figure}
We have a useful characterization due to Ch\^atel, Pilaud and Pons \cite{chatel_pilaud_pons} of the partial order of the Tamari lattice in terms of increasing or decreasing relations.
\begin{proposition}\label{char_tamari}
Let $T_1$ and $T_2$ be two binary trees. The following are equivalent.
\begin{enumerate}
\item $T_1 \leqslant T_2$ in the Tamari lattice.
\item $\mathrm{Dec}(T_1) \subseteq \mathrm{Dec}(T_2)$.
\item $\mathrm{Inc}(T_2) \subseteq \mathrm{Inc}(T_1)$.
\end{enumerate} 
\end{proposition}
\begin{proof}
See \cite[Proposition~$40$ and Remark~52]{chatel_pilaud_pons}.
\end{proof}
\begin{definition}
An interval-poset $(P, \lhd) $ is a poset over the integers $1,2,\dots, n$ such that 
\begin{enumerate}
\item If $a\lhd c$ and $a<c$, then, for all integers $b$ such that $a<b<c$, we have $b\lhd c$.
\item If $c\lhd a$ and $a<c$, then, for all integers $b$ such that $a<b<c$, we have $b\lhd a$. 
\end{enumerate}
\end{definition}
The conditions $(1)$ and $(2)$ of this definition will be referred to as the \emph{interval-poset condition}. The integer $n$ in the definition is called the \emph{size} of the interval-poset. 
\begin{remark}
Let $(P,\lhd)$ be an interval-poset. If $x\lhd y$ is an increasing relation (respectively a decreasing relation), then by the interval-poset condition there is a relation $y-1\lhd y$ (respectively $x+1\lhd x$). The existence of such `small' relations will be crucial in most of our proofs on \emph{modern interval-posets}. 
\end{remark}
\begin{theorem}[\sc Ch\^atel, Pons]\label{bij}
Let $n \in \mathbb{N}$. There is a bijection between the set of intervals in $\Tam_n$ and the set of interval-posets of size $n$. 
\end{theorem}
\begin{proof}
This is Theorem~$2.8$ of \cite{pons_chatel}.

Since we need to use the explicit version of the theorem, let us recall the two inverse bijections. if $[S,T]$ is an interval in $\Tam_n$, we construct an interval-poset as follows. The trees $S$ and $T$ can be seen as binary search trees and they induce two partial order relations $\lhd_S$ and $\lhd_T$. Let $P = \{1,2,\dots, n\}$. There is a binary relation $\lhd$ on $P$ given by the disjoint union of the decreasing relations of $S$ and the increasing relations of $T$.  Then it is proved in \cite{pons_chatel} that $(P,\lhd)$ is an interval-poset. 

Conversely, we assume that $(P,\lhd)$ is an interval-poset of size $n$. Let $D$ be the poset obtained by only keeping the decreasing relations of $P$. Similarly, let $I$ be the poset obtained by only keeping the increasing relations. By  \cite[Lemma~$2.5$]{pons_chatel}, the Hasse diagrams of these two posets are two forests. By adding a common root to the trees of each of these forests, we obtained two planar trees. Now, we produce binary trees starting from these planar trees.

For $I$ we recursively produce a binary tree $T$ by using the rule: right sibling becomes right child and child becomes left child.

For $D$ we recursively produce a binary tree $S$ by using the rule: left sibling becomes left child and child becomes right child.

The tree $S$ is smaller than $T$ for the order of the Tamari lattice, so we have an interval $[S,T]$.

These two correspondences are sometimes called the \emph{Knuth correspondences} or the \emph{natural correspondences} (see \cite{bruijn_morselt} or \cite{HPGT} for more details). 

It was proved in \cite[Theorem~$2.8$]{pons_chatel} that these two constructions give two bijections inverse of each other. 
\end{proof}
Finally, we need a useful translation in the world of interval-posets of the usual left/right symmetry of trees.
\begin{lemma}\label{symmetry}
Let $[S,T]$ be an interval in  $\Tam_n$ and $P$ be its corresponding interval-poset. The interval-poset corresponding to the interval obtained by taking the left/right symmetry of $S$ and $T$ is the interval-poset $Q$ of size $n$ defined by $a \lhd_Q b \Leftrightarrow n+1 - a \lhd_{P} n+1 - b$. 
\end{lemma}
\section{Exceptional intervals of the Tamari lattice}

In \cite{chapoton_mould}, Chapoton introduced an operad $\mathbf{NCP}$ of \emph{non-crossing plants}. A non-crossing plant is a generalization of a \emph{non-crossing tree}. Since we will not work with them, we refer the reader to the original article for a precise definition. We will only use the fact that non-crossing trees are particular examples of non-crossing plants. It was proved that this operad (in the category of sets) is a sub-operad of $\mathbf{Dend}$, the Dendriform operad. Then it was proved in \cite{chapoton_etal_mould} that the image of a non-crossing tree in $\mathbf{Dend}$ is of the form $\sum_{t\in I} t$ where $I$ is \emph{an interval in the Tamari lattice}. An interval that appears as such an image of a non-crossing tree is called \emph{exceptional}. In this section, we reprove and make precise this result by giving an explicit description of the exceptional intervals in terms of the interval-posets. Since they are in bijection with the non-crossing trees, the number of exceptional intervals in the Tamari lattice of size $n$ is $\frac{1}{2n+1}{\binom{3n}{n}}$. 

There is another well known family of intervals of the Tamari lattice counted by these numbers: it is classical that the Tamari order is a refinement of the usual partial ordering of the non-crossing partitions (see \cite[Section~$2$]{bernardi_bonichon} for more details). This implies that an interval in the poset of non-crossing partitions can naturally be seen as an interval in the Tamari lattice. By a result of Kreweras \cite{kreweras} or a bijection of Edelman \cite{edelman}, the number of intervals of non-crossing partitions of size $n$ is $\frac{1}{2n+1}{\binom{3n}{n}}$. At the end of this section, we show that this family coincides with the family of exceptional intervals. 

\subsection{Exceptional intervals and non-crossing trees}


A \emph{non-crossing tree} in the regular $n+1$-gon is a set of edges between the vertices of the polygon with the following properties 
\begin{itemize}
\item edges do not cross pairwise,
\item any two vertices are connected by a sequence of edges,
\item There is no loop made of edges.
\end{itemize}
The boundary edges are allowed in the set. It is classical that the number of non-crossing trees in the regular $n+1$-gon is $\frac{1}{2n+1}{\binom{3n}{n}}$ (see e.g.\ \cite[Theorem~3.10]{dulucq}).


Given two non-crossing trees $f$ and $g$ in regular polygons and a side $i$ of the regular polygon containing $f$, one can define the composition $f\circ_{i} g$ in the grafting of the polygons containing $f$ and $g$. This is defined as the union of the two trees, with some modifications along the grafting diagonal. If the diagonal is present in both $f$ and $g$, then it is kept in $f\circ_i g$. If it is present in exactly one of the two trees, then it is not kept in $f\circ_i g$. Otherwise, the result is not a non-crossing tree. One `denominator' diagonal is added and the result is a non-crossing plant. We refer to \cite[Section~$5.2$]{chapoton_mould} for more details. 


It was shown in \cite[Section~$5.1$]{chapoton_etal_mould} that one can construct a poset from a non-crossing tree. Let us recall this construction.

Let $T$ be a non-crossing tree in a \emph{based} regular $n+1$-gon. Here by based, we mean that we choose one side of the polygon and call it the base. We can label the edges of the $n+1$-gon by assigning the number $0$ to the base, and then successively assigning the numbers $1$ to $n$ to the edges in clockwise order. If an edge of $T$ is a boundary edge we assign to it the number of the boundary edge. Otherwise, the label of the edge of the non-crossing tree is the number of the unique open boundary edge that it separates from the base. Then we set $i \lhd_{T} j$ if the edge $i$ is separated from the base by the edge $j$. An example is given in Figure~\ref{fig1}.  
\begin{figure}
\begin{tikzpicture}[scale=1.3]
\node [draw, minimum size=5cm,regular polygon,regular polygon sides=12,rotate=180] (a) {};
\foreach \n in {2,3,11,12}{
   \pgfmathsetmacro\result{12 - (\n -1)}
    \node[below] at (a.side \n) {\pgfmathprintnumber{\result}};
}
\foreach \n in {5,6,...,9}{
   \pgfmathsetmacro\result{12 - (\n -1)}
    \node[above] at (a.side \n) {\pgfmathprintnumber{\result}};
}
\node[left] at (a.side 10) {3};
\node[right] at (a.side 4) {9};
\node[below] at (a.side 1) {0};
\draw[red,very thick] (a.corner 10) -- (a.corner 7);
\draw[red,very thick] (a.corner 10) -- (a.corner 9);
\draw[red,very thick] (a.corner 10) -- (a.corner 8);
\draw[red,very thick] (a.corner 11) -- (a.corner 10);
\draw[red,very thick] (a.corner 11) --(a.corner 12);
\draw[red,very thick] (a.corner 11) -- (a.corner 3);
\draw[red,very thick] (a.corner 3) -- (a.corner 2);
\draw[red,very thick] (a.corner 3) -- (a.corner 1);
\draw[red,very thick] (a.corner 7) -- (a.corner 4);
\draw[red,very thick] (a.corner 4) -- (a.corner 5);
\draw[red,very thick] (a.corner 7)-- (a.corner 6);
\end{tikzpicture}
\begin{tikzpicture}[scale=1.3]
\node [draw=none, minimum size=5cm,regular polygon,regular polygon sides=12,rotate=180] (a) {};
\node[left] at (a.side 10) {3};
\node[right] at (a.side 4) {9};
\draw[very thick] (a.corner 10) -- node[below] {6} (a.corner 7);
\draw[very thick] (a.corner 10) -- node[left] {4} (a.corner 9);
\draw[very thick] (a.corner 10) -- node[above] {5} (a.corner 8);
\draw[very thick] (a.corner 11) -- (a.corner 10);
\draw[very thick] (a.corner 11) -- node[below] {2} (a.corner 12);
\draw[very thick] (a.corner 11) --  node[above] {10} (a.corner 3);
\draw[very thick] (a.corner 3) --  node[below] {11} (a.corner 2);
\draw[very thick] (a.corner 3) -- node[above] {1} (a.corner 1);
\draw[very thick] (a.corner 7) --  node[below] {8} (a.corner 4);
\draw[very thick] (a.corner 4) --  (a.corner 5);
\draw[very thick] (a.corner 7)--  node[above] {7} (a.corner 6);
\end{tikzpicture}
\begin{tikzpicture}[scale=1.5]
 \node (a) at (0,0) {$1$};
 \node (b) at (-1,0.75) {$3$};
 \node (c) at (0,0.5) {$10$};
 \node (d) at (1,0.5) {$2$};
  \node (e) at (-0.5,1) {$6$};
  \node (f) at (0.5,1) {$8$};
  \node (g) at (-0.5,1.5) {$5$};
   \node (h) at (0.25,1.5) {$7$};
  \node (i) at (0.75,1.5) {$9$};
  \node (j) at (-0.5,2) {$4$};
  \node (k) at (1.5,0) {$11$};
  \draw (c) -- (b)
  	   (a) -- (c) -- (e) -- (g) -- (j)
	   (c)--(f)--(h)
	   (f)--(i)
	   (a)--(d);
 \end{tikzpicture}

\caption{On the left, an example of a non-crossing tree in a $12$-gon and in the center the induced labeling of the non-crossing tree. On the right, the Hasse diagram of the corresponding poset where the maximal elements are $1$ and $11$. }\label{fig1}
\end{figure}

\begin{lemma}\label{lem1}
Let $T$ be a non-crossing tree in a based regular $n+1$-gon. Then the poset $([1,n],\lhd_{T})$ is an interval-poset that we denote by $P_T$.
\end{lemma}
\begin{proof}
We label the boundary edges of a based regular $n+1$-gon as above. We use the notation $[i_1,i_2]$ where $i_1 \leqslant i_2$ for the edge that goes from the left side of the boundary edge $i_1$ to the right side of the boundary edge $i_2$. For example, in Figure~\ref{fig1}, the edge with label $6$ corresponds to $[4,6]$ and the edge labeled by $4$ corresponds to $[4,4]$. Note that, by construction of our labeling, the edge $[i_1,i_2]$ labeled by $i$ separates the boundary edge $i$ of the regular $n+1$-gon from the base. In particular this implies that $1\leqslant i_1 \leqslant i$ and $i\leqslant i_2 \leqslant n$.   

Let us check that the poset $P_T = ([1,n],\lhd_T)$ is an interval-poset. Let $0<i < j < k \leqslant n$ be such that $i\lhd k$. This means that the edge $[i_1,i_2]$ labeled by $i$ is separated from the base by the edge $[k_1,k_2]$ labeled by $k$. Since, $k$ separates $i$ from the base and $T$ is a non-crossing tree, we see that the only possibility is to have: 
 $$ k_1 \leqslant i_1 \leqslant i \leqslant i_2 \leqslant k \leqslant k_2. $$ 
 The boundary edge $j$ is between $i$ and $k$, so either it is before $i_2$ or after. Since $T$ is a non-crossing tree the edge $j$ cannot cross the edges $i$ and $k$. So, in the first case $k$ and $i$ separate $j$ from the base, and in the second case $k$ separates $j$ from the base. In particular, we have $j \lhd k$. See Figure~\ref{fig2} for an illustration where the letter $j$ is used for the first case and the letter $J$ for the second. The case where $k\lhd i$ is similar and is illustrated in the right part of Figure~\ref{fig2}.
\end{proof}
\begin{figure}
\centering \begin{tikzpicture}[scale=2]
\node [draw, minimum size=5cm,regular polygon,regular polygon sides=18] (a) {};
\node[below] at (a.side 10) {$0$};
\node[below] at (a.side 8) {$k_1$};
\node[left] at (a.side 5) {$i$};
\node[left] at (a.side 6) {$i_1$};
\node[above] at (a.side 18) {$i_2$};
\draw[very thick] (a.corner 7) -- node[above] {i} (a.corner 18);
\node[right] at (a.side 14) {$k$};
\node[below] at (a.side 13) {$k_2$};
\draw[very thick] (a.corner 9) -- node[above] {k} (a.corner 13);
\node[above] at (a.side 3) {$j$};
\draw[thick, red] (a.corner 1) -- node[above]{j} (a.corner 5);
\node[right] at (a.side 16) {$J$};
\draw[thick, dashed, blue] (a.corner 18) -- node[left]{J} (a.corner 14); 
\end{tikzpicture}
\begin{tikzpicture}[scale=2]
\node [draw, minimum size=5cm,regular polygon,regular polygon sides=18] (a) {};
\node[below] at (a.side 10) {$0$};
\node[left] at (a.side 5) {$i$};
\node[left] at (a.side 6) {$i_1$};
\node[right] at (a.side 14) {$k$};
\node[below] at (a.side 11) {$i_2$};
\draw[very thick] (a.corner 7) -- node[above] {i} (a.corner 11);
\node[right] at (a.side 13) {$k_2$};
\node[above] at (a.side 18) {$k_1$};
\draw[very thick] (a.corner 1) -- node[left] {k} (a.corner 13);
\node[right] at (a.side 16) {$J$};
\draw[thick, dashed, blue] (a.corner 18) -- node[left]{J} (a.corner 14); 
\node[above] at (a.side 3) {$j$};
\draw[thick, red] (a.corner 2) -- node[above]{j} (a.corner 6);
\end{tikzpicture}
\caption{On the left the case $i<j<k$ and $i\lhd k$. On the right $i<j<k$  and $k \lhd i$.}\label{fig2}
  \end{figure}

\begin{lemma}
Let $T$ be a non-crossing tree in a based regular $n+1$-gon. Then the Hasse diagram\footnote{We use the symbol $y\to z$ to indicate the presence of an arrow from $y$ to $z$ in the Hasse quiver of the poset $P_T$. This means that $y\lhd_T z$ is a cover relation. } of the interval-poset $P_T = ([1,n],\lhd_{T})$ does not contain any configuration of the form $y\to z$ and $y\to x$ where $x<y<z$.    
\end{lemma}
\begin{proof}
Let us assume that we have integers $x < y < z$ such that $y\lhd x$ and $y \lhd z$. This means that the edge $x = [x_1,x_2]$ separates $y = [y_1,y_2]$ from the base. As in the proof of Lemma~\ref{lem1}, this implies that 
$$ x_1 \leqslant y_1 \leqslant y_2 \leqslant x_2.$$ 
Similarly, the edge $z = [z_1,z_2]$ separates $y$ from the base, so we have
$$ z_1 \leqslant y_1 \leqslant y_2 \leqslant z_2.$$
Since $T$ is a non-crossing tree, if $x_1 \leqslant z_1$, then necessarily $x_2 \geqslant z_2$. In this case the edge $x$ separates the edge $z$ from the base and we have $z \lhd x$. If $z_1 \leqslant x_1$, then $x_2 \leqslant z_2$ and we have $x\lhd z$. In both cases, we see that one of two relations $y \lhd x$ and $y\lhd z$ is not a cover relation. In particular the configuration $y\to z$ and $y\to x$ does not appear in the Hasse diagram of the poset. 
\end{proof}
\begin{definition}\label{exc}
An interval-poset whose Hasse diagram does not contain any configuration of the form $y\to z$ and $y\to x$ where $x<y<z$ is called an \emph{exceptional} interval-poset.
\end{definition}
If $(P,\lhd)$ is an interval-poset over the integers $[1,n]$, we can construct a graph $G_P$ in a \emph{based} regular $n+1$-gon by using the following procedure which is nothing but a reformulation in terms of interval-posets of the construction explained in \cite[Section~$5.1$]{chapoton_etal_mould}. Let us start by labeling the boundary edges of the polygon as above. Then, for an integer $v$, consider the poset $\{ x\in [1,n]\ :\ x\lhd v\}$. It has a minimal element (for the usual order relation $<$) $v_1$ and a maximal element $v_2$. We associate to $v$ the edge in the polygon from the left side of $v_1$ to the right side of $v_2$.
\begin{lemma}\label{lem2}
If $(P,\lhd)$ is an exceptional interval-poset of size $n$, then the graph $G_P$ is a non-crossing tree. 
\end{lemma}
\begin{proof}
Let $(P,\lhd)$ be an exceptional interval-poset. If $k$ is a maximal element of $P$ (for the relation $\lhd$), then the set $I_k := \{ i \in P\ :\ i\lhd k\}$ is an interval because $P$ is an interval-poset. Moreover, if $k$ and $k'$ are two maximal elements of $P$, then the intervals $I_k$ and $I_{k'}$ are disjoint. Indeed, let $z\in P$ such that $z\lhd k$ and $z\lhd k'$. We can assume that $k\leqslant k'$. If $z \leqslant k \leqslant k'$, then the interval-poset condition implies that $k\lhd k'$ and by maximality $k=k'$. Similarly, if $k\leqslant k' \leqslant z$, the interval-poset condition implies that $k' \lhd k$ and by maximality, we have $k=k'$. Now, if $k < z <k'$, by maximality of $k$ and $k'$, we have a configuration of the form $z \to k$ and $z\to k'$ in the Hasse diagram. This is not possible since the interval-poset $P$ is exceptional. In other words, the exceptional interval-posets are nothing but the \emph{non-interleaving forests} introduced in \cite[Section~$5.1$]{chapoton_etal_mould}. In particular, the result is a direct consequence of \cite[Lemma~$5.2$]{chapoton_etal_mould}. We sketch it for the convenience of the reader. 

It is easy to see that the poset $P$ has a unique maximal element if and only if the base of the polygon is in the graph $G_P$. In this case, we say that $G_P$ is based. 

The interval-poset $P$ is a disjoint union of $s$ interval-posets $I_{k_1},\dots, I_{k_n}$ where $k_i$ runs through the maximal elements of $P$. If there is more than one maximal element, by induction on the size of the poset we see that the graph $G_{I_{k_i}}$ is a based non-crossing tree. Now, it is easy to see that the graph $G_P$ is obtained by gluing the base of all the non-crossing trees $G_{I_{k_i}}$ on the boundary of a regular $s+1$-gon. More formally, in terms of NCP-operads, we have $G_p = S \circ_{1} G_{I_{k_1}} \circ_{2} \cdots \circ_{s} G_{I_{k_s}}$, where $S$ is the non-crossing tree with $s$ edges consisting of all boundary edges of the regular $s+1$-gon, except for the base. 

If there is only one maximal element $m$ in $P$, then $G_P$ is based. The case where $P$ has only two elements is elementary and can be checked by listing all the possible cases. If $|P|\geqslant 3$, let $P_{1} = \{ i \in P\ :\ i < m \}$ and $P_{2} = \{ i \in P\ :\ m < i\}$. Clearly $P_1$ and $P_2$ are two disjoint interval-posets of size smaller than $|P|$. By induction, the graphs $I_{P_1}$ and $I_{P_2}$ are non-crossing trees. Let $U$ be the non-crossing tree in a based square consisting of the base and the two adjacent boundary edges. It is now easy to see that $G_P = (U\circ_1 I_{P_1}) \circ_3 I_{P_2}$. In particular, $G_P$ is a non-crossing tree. 
\end{proof}
\begin{proposition}
The map sending a non-crossing tree $T$ to the interval-poset $P_T$ and the map sending an exceptional interval-poset $P$ to the non-crossing tree $T_P$ are two bijections inverse of each other between the set of non-crossing trees in a based regular $n+1$-gon and the set of exceptional interval-posets of size $n$.
\end{proposition}
\begin{proof}
The result is proved by induction. The cases $n=0,1$ and $2$ can be easily checked by hand. Let $n\geqslant 3$. If $T$ is a non-crossing tree, we denote the exceptional interval-poset obtained in Lemma~\ref{lem1} by $P_T$. If $P$ is an exceptional interval-poset, we denote the non-crossing tree obtained in Lemma~\ref{lem2} by $T_P$. Let $S$ be the non-crossing tree with $s$ edges consisting of all boundary edges of the regular $s+1$-gon, except for the base. Let $T_1,\cdots, T_s$ be $s$ based non-crossing trees. Let $T = S \circ_1 T_1\circ_2 \cdots \circ_s T_s$. The edges of $T_i$ (viewed as edges in $T$) are separated from the base by the base of $T_i$, and the edges of $T_i$ are not separated from the base by any edge of $T_j$ for $i\neq j$. This implies that $P_T$ is the disjoint union of the posets $P_{T_i}$ and all these posets have a unique maximal element. 

If the poset $P$ has more than one maximal element, we have $P = P_1 \sqcup \cdots \sqcup P_s$ where $P_i$ is the set of elements smaller than the $i$-th maximal element. By the proof of Lemma~\ref{lem2}, the corresponding non-crossing tree $T_P$ is of the form $S\circ_{1} I_{P_1}\circ_{2} \cdots \circ_{s} I_{P_s}$. By the remark above, the poset corresponding to the tree $T_P$ is $P_{I_{P_1}} \sqcup \cdots \sqcup P_{I_{P_s}}$. Now, by induction we have that $P_{T_{P}} = P$. 

Similarly, if the tree $T$ is not based, it can be written as $S \circ_1 T_1\circ_2 \cdots \circ_s T_s$ where $T_i$ are based non-crossing trees. So, we have $P_{T} = P_{T_1} \sqcup \cdots \sqcup P_{T_s}$, and $T_{P_{T}} = S \circ_1 T_{P_{T_1}} \circ_2 \cdots \circ_s T_{P_{T_s}}$. One more time, an induction gives the result. 

Let $U$ be the non-crossing tree in a based square consisting of the base and the two adjacent boundary edges. If $T$ is a based non-crossing tree, there are two non-crossing trees $T_1$ and $T_2$ such that $T = U\circ_1 T_1 \circ_3 T_2$. It is easy to see that the poset $P_T$ is of the form $P_1 \sqcup \{m\} \sqcup P_2$, where $m$ is the labeling of the base of $T$, $P_1$ is the subset consisting of the elements smaller (for $<$) than $m$ and $P_2$ is the set of elements larger than $m$. Since $m$ is the label of the basis it is the unique maximal element of $P_T$. Using this decomposition of based non-crossing trees, and exceptional interval-posets with a unique maximal element, it is easy to prove by induction that $T_{P_T} = T$ and $P_{T_{P}} = P$. 
\end{proof}

By \cite[Theorem~$5.3$]{chapoton_mould}, there is an injective morphism of operads (in the category of sets) $\Theta$ from the operad of non-crossing plants $\mathbf{NCP}$ and the dendriform operad $\mathbf{Dend}$. Using exceptional interval-posets we describe the image of a non-crossing tree by $\Theta$. 

\begin{theorem}\label{image_noncrossing}
Let $T$ be a non-crossing tree. Let the image of $T$ in $\mathbf{Dend}$ be $\sum_{t\in I} t$. Then the set of trees $I$ is the interval of the Tamari lattice corresponding to the exceptional interval-poset $P_T$. 
\end{theorem}
\begin{proof}
Since exceptional interval-posets are the same as non-interleaving forests, the result follows from a reformulation of \cite[Section~$5.1$]{chapoton_etal_mould} and a description of interval-posets in terms of linear extensions due to Ch\^atel and Pons. We sketch the arguments. 

Let $\phi : \mathbf{NCP} \to \mathbf{Mould}$ be the injection defined in \cite[Section~$5.2$]{chapoton_mould} or in \cite[Section~$5.2$]{chapoton_etal_mould}. Let $\psi : \mathbf{Dend} \to \mathbf{Mould}$ be the injection defined in \cite[Theorem~$3.1$]{chapoton_mould}. Since the maps $\Theta$, $\phi$ and $\psi$ are morphisms of operads and since the diagram is commutative on the elements of $\mathbf{NCP}(2)$, the following diagram is commutative:

\[
\xymatrix{
\mathbf{NCP}\ar[rd]^{\phi}\ar[rr]^{\Theta} & & \mathbf{Dend} \ar[dl]_{\psi} \\
& \mathbf{Mould}
}
\]
Moreover, all the morphisms are injective.


Let $T$ be a non-crossing tree. By \cite[Lemma~$5.3$]{chapoton_etal_mould}, we have $\phi(T) = \sum_{\sigma \in L(P_T)} f_{\sigma}$ where $P_T$ is the exceptional interval-poset that corresponds to $P$ and $L(P_T)$ is the set of all linear extensions of $P_T$ and if $\sigma \in S_n$, then $f_{\sigma}$ is the fraction defined by
\[
f_{\sigma}(u_1,\dots, u_n) = \frac{1}{u_{\sigma(1)} \cdot (u_{\sigma(1)} + u_{\sigma(2)} ) \cdot \cdots \cdot (u_{\sigma(1)} + \cdots + u_{\sigma(n)})}. 
\]
For $\sigma,\sigma' \in S_n$ the multi-residue $\oint_{\sigma}$ (see \cite[Proposition~$3.3$]{chapoton_mould}) has the property that $\oint_{\sigma} f_{\sigma'} \neq 0$ if and only if $\sigma = \sigma'$. So, for $\sigma \in S_{n}$, we have $\oint_{\sigma} \phi(P_T) \neq 0$ if and only if $\sigma$ is a linear extension of $P_T$. 

On the other hand, by \cite[Proposition~$3.3$]{chapoton_mould}, if $T$ is a binary tree, we have $\oint_{\sigma} \psi(T) \neq 0$ if and only if $\sigma$ is a linear extension of the poset induced by the tree $T$. As a consequence, $I$ is the set of trees whose linear extensions are exactly the linear extensions of $P_T$. Now, by \cite[Theorem~$2.8$]{pons_chatel}, this implies that $I$ is an interval of the Tamari lattice, and that $P_T$ is the interval-poset corresponding to $I$. 
\end{proof}
\subsection{Non-crossing partitions}
A partition $(b_1,\dots,b_m)$ of $\{1,2,\dots, n\}$ is \emph{non-crossing} if there do not exist $1\leqslant i < j < k < l \leqslant n$ such that $i,k \in b_s$ and $j,l \in b_t$ for $s\neq t$. Let $\NC_n$ be the set of all \emph{non-crossing partitions} of $\{1,2,\dots, n\}$. It is well-known that the cardinality of this set is the Catalan number $c_n$. The refinement of partitions induces a structure of partial order on $\NC_n$ which is known to be a lattice (see \cite{kreweras} for more details). 

It is also classical that the Tamari lattice is a refinement of the poset of non-crossing partitions. In general, it is convenient to realize these posets on the set of Dyck paths via well chosen bijections in order to compare them (see \cite[Section~$2$]{bernardi_bonichon} for more details). Here, in order to simplify the proofs, we realize the poset of non-crossing partitions on the Tamari lattice, using a bijection similar to a bijection introduced by Edelman \cite{edelman}.

If $T$ is a (planar) binary tree, we can view it as a binary search tree using the in-order algorithm (this is why our bijection is not the same as Edelman's bijection: he labeled the trees with pre-order traversal).  Then the partition $\pi_T$ associated to the tree $T$ is the \emph{finest partition} of $\{1,2,\dots, n\}$ such that, if $j$ is right child of $i$, then $i$ and $j$ are in the same block. For example, the partition corresponding to the binary tree of Figure~\ref{fig_inorder} is $\{1,3,4\}, \{2\}, \{5,8\}, \{6,7\}$. 
\begin{lemma}
Let $T$ be a binary tree and $\pi_T$ its corresponding partition. Then $\pi_T$ is a non-crossing partition.
\end{lemma}
\begin{proof}
Let $i< j < k < l$ such that $i,k$ are in a block $b_1$ and $j,l$ are in a block $b_2$. The vertex of $T$ labeled by $k$ is a right descendant of the vertex labeled by $i$. 

Since the in-order algorithm goes first through left subtrees, then it visits the root and finally goes through right subtrees, the vertex $j$ is in the right subtree of $i$. Since $l$ and $i$ are in the same block, the vertex $l$ is a right-descendant of $i$. Since $k<l$, the vertex $k$ is in the right subtree of $j$. The only possibility is to have that $j,k$ and $l$ are right descendants of $i$. So, they are in the same block.
\end{proof}
Conversely, if $\pi = (b_1,\dots, b_m)$ is a non-crossing partition of $\{1,2,\dots, n\}$ we will construct a binary search tree associated to this partition. We assume that the blocks of the partition are totally ordered in such a way that $\min(b_1) < \min(b_2) <\cdots < \min(b_n)$ and the elements of the blocks are ordered by the natural ordering of the integers. The tree $T_\pi$ is constructed in two steps:
\begin{enumerate}
\item To each block $b_i$ is associated a binary tree $T_i$ with root $\min(b_i)$ and if $y$ is the successor of $x$ in the block $b_i$, then $y$ is the right child of $x$. 

\item If $T_i$ is a tree constructed in the first step, let $m_i$ be the vertex with maximal labeling in the tree. We construct inductively a tree $T_\pi$ by grafting the root of $T_i$ as the left child of the vertex labeled by $m_i + 1$. For an example see Figure~\ref{bij_ncp}.
\end{enumerate}
\begin{figure}[h]
\centering
    \begin{tikzpicture}[scale =0.5]
\node (1) at (-4,4) {1}; \node (2) at (-3,4) {2}; \node (3) at (-2,4) {3}; \node (4) at (-1,4) {4}; \node (5) at (0,4) {5}; \node (6) at (1,4) {6}; \node (7) at (2,4) {7}; \node (8) at (3,4) {8};
\draw[blue,thick] (2.north) to  [out=140,in=50] (1.north);
\draw[blue,thick] (4.north) to  [out=100,in=80] (3.north);
\draw[blue,thick] (7.north) to  [out=135,in=45] (2.north);
\draw[blue,thick] (6.north) to  [out=100,in=80] (5.north);
\end{tikzpicture}
\begin{tikzpicture}
\node (1) at (2,0) {1}; \node (2) at (2.5,0.5) {2} ; \node (7) at (3,1) {7}; \node (3) at (0,1) {3}; \node (4) at (0.5,1.5) {4}; \node (5) at (1,0.5) {5}; \node (6) at (1.5,1) {6}; \node (8) at (3.5,-1) {8};
\draw (1)--(2)--(7)
	 (3)--(4)
	 (5)--(6);
\draw[red,->] (1.south) to [out=-45,in=135] (8.west);
\draw[red,->] (3.south) to [out = -45, in= 135] (5.west);
\draw[red, ->] (5.south) to [out = -45, in = 135] (7.west);
\end{tikzpicture}
\begin{tikzpicture}[scale =0.8]
\node (a) at (0,0) {8};
\node (c) at (-1,3) {3};
\node (b) at (-0.5,0.5) {1};
\node (d) at (0,1) {2};
\node (e) at (-0.5, 3.5) {4};
\node (f) at (0, 2) {5};
\node (g) at (1.5,3.5) {6} ; 
\node (h) at (0.5,1.5) {7};
\node (1) at (-4,4) {}; \node (2) at (-3,4) {}; \node (3) at (-2,4) {}; \node (4) at (-1,4) {}; \node (5) at (0,4) {}; \node (6) at (1,4) {}; \node (7) at (2,4) {}; \node (8) at (3,4) {}; \node (9) at (4,4) {}; 
\draw (a)--(b)--(1)
	  (b)--(d)--(h)--(8)
	  (a)--(9)
	  (d)--(2)
	  (h)--(f)--(c)--(3)
	  (f)--(g)--(7)
	  (g)--(6)
	  (c)--(e)--(5)
	  (e)--(4);
\end{tikzpicture}
\caption{An example of the two steps of the construction of a binary tree associated to a non-crossing partition.}\label{bij_ncp}
\end{figure}

\begin{lemma}
Let $\pi$ be a non-crossing partition of $\{1,2,\dots,n\}$ and $T_\pi$ the corresponding binary tree. Then $T_\pi$ is a binary search tree. 
\end{lemma}
\begin{proof}
Let $s$ be the label of a vertex. If $x$ is a right descendant of $s$, then by construction $s$ and $x$ are in the same block and we have $s < x$. If $y$ is the left child of $x$, then the maximal element of the block of $y$ is $x-1$. If $z$ is in the block of $y$, then we have $s<z<x$ because $s$ and $x$ are in the same block, $y$ and $x-1$ are in the same block, and the partitions are non-crossing. Using these remarks, it is easy to check that, if $z$ is in the right subtree of $s$, then $s < z$. Similarly, it is easy to check that the elements of the left subtree of $s$ are labeled by integers strictly smaller than $s$. 
\end{proof}
\begin{proposition}
The map sending a binary tree $T$ to the non-crossing partition $\pi_T$ and the map sending a partition $\pi$ to the binary tree $T_\pi$ are two bijections inverse of each other. 
\end{proposition}
\begin{proof}
By construction of the tree $T$, the minimal elements of the blocks are the vertices  that are a left child of another vertex (i.e. they have a right parent) and their left descendants are the elements of their block. So, the partition $\pi_{T_\pi}$is equal to $\pi$. Since there is a unique way to turn a binary tree into a binary search tree of size $n$ using exactly once each of the integers $1,2,\dots, n$, we have $T_{\pi_T} = T$.  
\end{proof}
%We need the following technical Lemma which explain what is the vertex visited before a vertex $x$ by the in-order algorithm in terms of noncrossing partitions. 
%\begin{lemma}\label{re_nct}
%Let $\pi$ be a noncrossing partition of $\{1,2,\cdots, n\}$ and $T_\pi$ be the corresponding binary search tree.  Let $x$ be a vertex of $T_\pi$. Let $r_x$ be the maximal element $r_x < x$ such that there is $y$ in the block of $r_x$ with the property $r_x < x \leqslant y$. If there is no such $r_x$ we set $r_x = 0$. Then, the left subtree of $x$ has vertices labeled by $]r_x ; x[$. 
%\end{lemma}
%\begin{proof}
%Since $T_\pi$ is a binary search tree, the left subtree of $x$ has vertices labeled by the interval $]r_x,x[$ where $r_x$ is the last vertex assigned by the in-order algorithm before entering in this left subtree. So, we just need to understand $r_x$ in terms of noncrossing partitions. 
%
%If $x$ is the right son of a vertex $r$, then $r=r_x$. In terms of noncrossing partitions,  this means that $r_x$ is the predecessor of $x$ in its block.
%
%If $x$ is the smallest element in its block, let $m_1$ be the maximal element of its block. Then, by construction $x$ is the left son of $y_2:=m_1 + 1$. Let $x_2$ be the minimal element of the block of $y_2$ and $m_2$ be its maximal element. By induction we let $y_{n} := m_{n-1}+1$, $x_n$ be the minimal element of the block of $y_n$ and $m_{n+1}$ be the maximal element.
%
%If $y_n$ is the minimal element of its block for every $n$, then the element $x$ is on the left side of the tree $T_{\pi}$. There is no $r$ such that $r < x$ and the successor $y$ of $r$ in its block is such that $r<x\leqslant y$. Indeed, since $x_{i+1} = m_{i} +1$ and the partitions are non crossing, the element $y$ is necessarily one of the $x_i$, this contradicts the fact that $x_i$ is the minimal element of its block.   
%
%Otherwise, let $k$ be the smallest integer such that $y_k$ is not the minimal element in its block, its predecessor $r$ is the last vertex visited by the in-order algorithm. The element $r$ is not in the blocks containing $x_i$ for $i<k$.  Since $x_{i+1} = m_{i} + 1$ for $i<k$, and the partitions are noncrossing, the predecessor of $y_k$ is the largest element $r < x$ such that the there is $y$ in its block with $x < y$. 
%\end{proof}
%


We can now be more precise about the fact that the Tamari lattice is a refinement of the lattice of non-crossing partitions.
\begin{lemma}\label{refinement}
Let $\pi_1$ and $\pi_2$ be two non-crossing partitions of $\{1,2,\dots, n\}$. If $\pi_1 \leqslant \pi_2$ in the poset of non-crossing partitions, then $T_{\pi_{1}} \leqslant T_{\pi_{2}}$ in the Tamari lattice. 
\end{lemma}
\begin{proof}
Using Proposition~\ref{char_tamari}, it is enough to show that the decreasing relations of $T_{\pi_1}$ are decreasing relations of $T_{\pi_2}$.

Let $i < j$ such that $j\lhd _{T_{\pi_1}} i$. In other words, the vertex $j$ is in the subtree with root $i$. Since $i<j$, this implies that $j$ is in the right subtree of $i$. Let $x$ be the right descendant of $i$ such that $j$ is in its left subtree (if $j$ is a right descendant of $i$, we have $x=j$). Since the tree $T_{\pi_1}$ is a binary search tree, this implies that $i< j < x$. Moreover, by construction of $T_{\pi_1}$, the elements $i$ and $x$ are in the same block. Since the partial order relation for non-crossing partitions is given by merging blocks, in the partition $\pi_2$ the elements $i$ and $x$ are also in the same block. In other words, the element $x$ is in the right subtree of $i$ in $T_{\pi_2}$. Since $i < j < x$, this implies that $j$ is also in the right subtree of $i$, so we have $j \lhd_{T_{\pi_2}} i$.
%Let $i<j$ such that $i\lhd_{T_{\pi_2}} j$. That is $i$ is in the left subtree of $j$ in $T_{\pi_2}$. Let $r_{j}^{1}$ (respectively $r_{j}^{2}$) the element $r_j$ of Lemma \ref{re_nct} for the partition $\pi_1$ (respectively $\pi_2$). We just need to check that $r_{j}^{1} \leqslant r_{j}^{2}$, the result will follow from the description of the left subtree of $j$ given in Lemma \ref{re_nct}. By transitivity it is enough to check it when $\pi_1 < \pi_2$ is a cover relation. That is  $\pi_2$ is obtained from $\pi_1$ by merging two blocks. If $r_{j}^{1} = 0$ there is nothing to check. Otherwise, let $y$ be the successor of $r_{j}^{1}$ in its block. We have $r_{j}^{1} < j \leqslant y$. If $r_{j}^{1}$ is the predecessor of $j$ in its block, then after the merging of blocks $r_{j}^{1}$ is still in the block of $j$ and it is still smaller than $j$. So we have $r_{j}^{1} \leqslant r_{j}^{2}$. Let us assume that $r_{j}^{1}$ is not in the block of $j$ in $\pi_1$. If the block of $r_j^1$ and the block of $j$ merge, then $r_j^2 = r_j^1$. If a block containing $j$ merges with another block, by the noncrossing condition, the elements of the second blocks are in $]r_j^{1} , y[$. If $j$ is still minimal in his new block, then $r_j^1 = r_j^2$, otherwise, $r_j^2$ is an element of the new block. So we have $r_j^1 < r_j^2$. Finally, if the merging does not involve the block containing $j$ we have $r_j^1 = r_j^2$. 
\end{proof}
We can now characterize the intervals of the Tamari lattice that come from intervals in the lattice of non-crossing partitions.
\begin{theorem}\label{theo_nc}
Let $n \in \mathbb{N}$. Let $I$ be an interval of the Tamari lattice $\Tam_n$. Then there is an interval of non-crossing partitions $[\pi_1,\pi_2]$ such that $I = [T_{\pi_1},T_{\pi_2}]$ if and only if the interval-poset corresponding to $I$ is exceptional. 
\end{theorem}
\begin{proof}
Let $\pi_1 \leqslant \pi_2$ in $\operatorname{NC}_n$. Let $I = [T_{\pi_1},T_{\pi_2}]$ be the corresponding interval in $\Tam_n$ and $P$ be the corresponding interval-poset. Let $x < y < z$ such that we have a relation $y \lhd x$ and $y\lhd z$. 

First assume that $y \lhd x$ is a cover relation. We will show that this implies the existence of a relation $x\lhd z$. This last relation implies that $y\lhd z$ is not a cover relation. We can assume that $y$ is the maximal element such that $y\lhd x$ is a cover relation and $y \lhd z$. Let $t \lhd x$ be a cover relation. If $z \leqslant t$, then by the interval-poset condition we have a relation $z\lhd x$ and the relation $y\lhd x$ becomes the composite of $y \lhd z$ and $z\lhd x$ contradicting the hypothesis. So, the maximal element $t$ with a cover relation $t\lhd x$ is an element of $[y,z[$. By the interval-poset condition, we have $t\lhd x$, so by maximality we have $t = y$. 

In other terms, in the decreasing forest of $P$, the element $y$ is the right-most child of $x$. So, using the bijection of Theorem~\ref{bij} we see that $y$ is the right child of $x$ in the tree $T_{\pi_1}$. In terms of non-crossing partitions, this means that $y$ is the successor of $x$ in its block. Since the partial order relation for the non-crossing partitions is given by merging of blocks, we see that $y$ is still in the block of $x$ in $\pi_2$. This implies that $y$ is also in the right subtree of $x$ in $T_{\pi_2}$.

In the increasing forest of $P$ we have the relation $y \lhd z$ which means that $y$ is in the left subtree of $z$. Since $y$ is a right descendant of $x$, this implies that $x$ is in the right subtree of $z$. Using one more time the bijection of Theorem~\ref{bij}, we have an increasing relation $x\lhd z$. 

We only sketch the proof when $y\lhd z$ is a cover relation. We can assume $y$ to be minimal for this property. This implies that $y$ is the left-most child of $z$ in the increasing forest of $P$. So $y$ is the left child of $z$ in $T_{\pi_2}$. By the argument of Lemma~\ref{refinement}, an increasing relation of $T_{\pi_2}$ is also an increasing relation of $T_{\pi_1}$. In particular, $y$ is in the left subtree of $z$ in $T_{\pi_1}$. The relation $y \lhd x$ in $P$ implies that $y$ is in the right subtree of $x$. Since it is also in the left subtree of $z$, this implies that $z$ is in the right subtree of $x$. So we have the relation $z \lhd x$ in $P$. 

We have proved that the interval-posets of the intervals of the Tamari lattice coming from intervals of non-crossing partitions are exceptional. The result follows from the fact that the number of exceptional interval-posets is the number of intervals in the poset of non-crossing partitions. 
\end{proof}
\section{New intervals and modern interval-posets}
In this section, we introduce the notion of \emph{modern} interval-posets and we show that the modern interval-posets of size $n$ are in bijection with the new intervals of $\Tam_{n+1}$. Note that there is a shift of the size by $1$. 
\subsection{New intervals of the Tamari lattice}
From now on, we will always assume that the leaves of the binary trees of $\Tam_n$ are labeled from left to right by the integers $1,2,\dots, n+1$. Let $T \in \Tam_n$ and $S\in \Tam_k$. Let $1\leqslant i \leqslant n+1$. The binary tree $T\circ_i S$ is the tree of size $k+n$ obtained by grafting the root of $S$ on the $i$-th leaf of $T$. If $[S_1,T_1]$ is an interval of $\Tam_n$ and $[S_2,T_2]$ is an interval of $\Tam_k$, and $1\leqslant i \leqslant n+1$, then the tree $S_1\circ_i S_2$ is smaller than $T_1\circ_i T_2$. We say that the interval $[S_1 \circ_i S_2,T_1\circ_i T_2]$ is the $i$-th grafting of $[S_2,T_2]$ on $[S_1,T_1]$, and we denote it by $[S_1,T_1] \circ_i [S_2,T_2]$.

\begin{definition}
An interval of $\Tam_n$ is called \emph{new} if it cannot be obtained as the grafting of two intervals. 
\end{definition}
The new intervals were introduced by Chapoton in \cite{chapoton_interval}.

\begin{lemma}[Chapoton]\label{not_new}
An interval $[S,T]$ of $\Tam_n$ is new if and only if there is no pair of subtrees $(A,B)$ of $S$ and $T$ whose leaves are labeled by the same interval $[i,j]\neq [1,n+1]$. 
\end{lemma}
\begin{proof}
If there is a subtree $A$ of $S$ whose leaves are labeled by $[i,j]$ and a subtree $B$ of $T$ whose leaves are also labeled by $[i,j]$, then $S$ is of the form $S_1 \circ_i A$ and $T$ is of the form $T_1 \circ_i B$, so the interval is not new. Conversely, if the interval is not new, then $[S,T] = [S_1,T_1] \circ_i [A,B]$. So there is a pair of subtrees $(A,B)$ of $S$ and $T$ whose leaves are labeled by the same interval $[i,i+\mathrm{size}(S)]$. 
\end{proof}
With this criterion, it is easy to see that the new intervals of $\Tam_n$ have a \emph{nice shape}.
\begin{lemma}\label{new_shape}
Let $n\in \mathbb{N}^*$. Let $[S,T]$ be a new interval of $\Tam_n$. Then there are two binary trees $S_1$ and $T_1$ in $\Tam_{n-1}$ such that $S = Y\circ_1 S_1$ and $T = Y\circ_2 T_1$ where $Y$ is the unique binary tree of size $1$. 
\end{lemma}
\begin{proof}
The covering relation for the Tamari lattice is the left rotation. So, if there is a vertex on the right side of $S$, it will be fixed by any left rotation, so it will also appear at the same place in the tree $T$. Similarly, if there is a vertex on the left side of $T$ it must also be at the same place in $S$. So the subtrees with root $s$ have the same interval of leaves. Using Lemma~\ref{not_new}, we see that the interval $[S,T]$ is not new in both cases.
\end{proof}
However, it is easy to find intervals with this nice shape but which are not new. We will characterize the new intervals in this family in Theorem~\ref{new_chara}.
\subsection{Raising and lowering of interval-posets}
\begin{definition}\label{def_modern}
Let $n \in \mathbb{N}$. An interval-poset of size $n$ is \emph{modern} if it does not contain any configuration of the form $x\lhd y$ and $z\lhd y$ with $x < y < z$. 
\end{definition}
Let us remark that, unlike Definition~\ref{exc}, the forbidden configuration here involves \emph{all the relations} and not only the relations in the Hasse diagram of the poset. 


Let us introduce the \emph{raise} of a set with a reflexive binary relation\footnote{The raise of an interval-poset needs not to be an interval-poset, so in order to be able to take successive raises we need a more general setting.}. If $P = \{1,2,\dots, n\}$ is a set with a reflexive binary relation $\lhd$, then $(\Ri(P),\lhd_R)$ is the set $\{1,2,\dots, n+1\}$ with the binary relation $\lhd_R$ defined by keeping all decreasing relations of $P$ and shifting all the increasing relations of $P$ by $1$. More precisely, the relation $\lhd_R$ is reflexive and for $x<y \leqslant n$, we have $ y \lhd_R x $ if and only if $y\lhd x$. For $1 < x < y \leqslant n+1$ we have $x\lhd_R y$ if and only if $x-1 \lhd y-1$. For an example, see Figure~\ref{ex_rise}. 

\begin{figure}[h]
\begin{tabular}{ccc}

\begin{tikzpicture}
\node (1) at (0,0) {1}; \node (2) at (1,0) {2}; \node (3) at (2,0) {3};
\draw[blue,thick,->] (2.north) to  [out=140,in=50] (1.north);
\draw[red,->,below, thick] (2.south) to [out=-45,in=225] (3.south);
\end{tikzpicture}
&
\begin{tikzpicture}
\node (1) at (-1,1) {} ; \node (2) at (0,1) {}; \node (3) at (1,1) {} ; \node (4) at (2,1) {}; \node (5) at (0.5,-0.5) {$\bullet$}; \node (6) at (0,0) {$\bullet$}; \node (7) at (0.5,0.5) {$\bullet$};
\draw (-1,1)--(0,0)--(0.5,-0.5)--(2,1) 
	 (0,0)--(0.5,0.5)--(0,1)
	 (0.5,0.5)--(3);
\end{tikzpicture}
&
\begin{tikzpicture}
\node (1) at (-1,1) {} ; \node (2) at (0,1) {}; \node (3) at (1,1) {} ; \node (4) at (2,1) {}; \node (5) at (0.5,-0.5) {$\bullet$}; \node (6) at (1,0) {$\bullet$}; \node (7) at (0.5,0.5) {$\bullet$}; 
\draw (-1,1)--(0.5,-0.5)--(1,0)--(2,1)
	  (1,0)--(0.5,0.5)--(0,1)
	  (0.5,0.5)--(1,1); 	 
\end{tikzpicture}
\\
\begin{tikzpicture}
\node (1) at (0,0) {1}; \node (2) at (1,0) {2}; \node (3) at (2,0) {3}; \node (4) at (3,0) {4};
\draw[blue,thick,->] (2.north) to  [out=140,in=50] (1.north);
\draw[red,->,below, thick] (3.south) to [out=-45,in=225] (4.south);
\end{tikzpicture}
&
\begin{tikzpicture}
\node (1) at (-2,1) {} ; \node (2) at (-1,1) {}; \node (3) at (0,1) {} ; \node (4) at (1,1) {}; \node (5) at (2,1) {}; \node (r) at (0,-1) {$\bullet$}; \node (a) at (-0.5,-0.5) {$\bullet$}; \node (b) at (-1,0) {$\bullet$}; \node (c) at (-0.5,0.5) {$\bullet$};
\draw (1)--(-1,0)--(-0.5,-0.5)--(0,-1)--(5)
	   (-1,0)--(-0.5,0.5)--(3)
	   (-0.5,0.5)--(2)
	  (-0.5,-0.5)--(4);
\end{tikzpicture}
&
\begin{tikzpicture}
\node (1) at (-2,1) {} ; \node (2) at (-1,1) {}; \node (3) at (0,1) {} ; \node (4) at (1,1) {}; \node (5) at (2,1) {}; \node (r) at (0,-1) {$\bullet$}; \node (a) at (0.5,-0.5) {$\bullet$}; \node (b) at (1,0) {$\bullet$}; \node (c) at (0.5,0.5) {$\bullet$};
\draw (-2,1)--(0,-1)--(0.5,-0.5)--(1,0)--(5)
	   (1,0)--(0.5,0.5)--(4)
	   (0.5,0.5)--(3)
	  (0.5,-0.5)--(2);
\end{tikzpicture}
\end{tabular}
\caption{On the top an interval-poset of size $3$ and its corresponding interval of $\Tam_3$. On the bottom, its raise and the corresponding interval of $\Tam_4$.}\label{ex_rise}
\end{figure}
\begin{lemma}\label{montee}
Let $(P,\lhd)$ be an interval-poset of size $n$. Then the raise of $P$ is an interval-poset if and only if $P$ is modern. 
\end{lemma}
\begin{proof}
Since the raise only shifts the increasing relations of $P$, it is clear that the relation $\lhd_R$ satisfies the two conditions of interval-poset.

If the interval-poset $P$ is not modern, there is a configuration of the form $x\lhd y$ and $z\lhd y$ with $x < y < z$. The condition of interval-poset implies the existence of the two relations $y-1 \lhd y$ and $y+1\lhd y$. It is clear that the raise of $P$ is not a poset since we have $y\lhd_R y+1$ and $y+1 \lhd_R y$. 

If the interval-poset $P$ is modern, we need to see that $\Ri(P)$ is a poset. If we have in $\Ri(P)$ two elements $x<y$ such that $x\lhd_R y$ and $y\lhd_R x$, then in $P$ we have $y\lhd x$ and $x-1 \lhd y-1$. Since $x-1 < x \leqslant y-1$, the condition of interval-poset of $P$ implies that we have a relation $x \lhd y-1$. Similarly, since $x\leqslant y-1 < y$, the interval-poset condition implies that we have a relation $y-1 \lhd x$. Since $P$ is a poset, we have $x = y-1$, and we see that the relations $x\lhd_R y$ and $y\lhd_R x$ come from the relations $y-2 \lhd y-1$ and $y \lhd y-1$ in $P$. In other words, the interval-poset $P$ is not modern.

Let us assume that $\Ri(P)$ contains two relations $x\lhd_R y$ and $y\lhd_R z$ but does not contain the relation $x \lhd_R z$. Since increasing relations and decreasing relations come from $P$, it is clear that such a situation implies that one of the two relations is increasing, and the second one is decreasing. If the relation $x \lhd_R y$ is increasing, there are two possibilities: either $z$ is before $x$, or $z$ is between $x$ and $y$. If $z$ is before $x$ the relation $y\lhd_R z$ and the interval-poset condition imply the existence of a relation $x\lhd_R z$. Otherwise, the interval-poset condition implies the existence of a relation $z \lhd_R y$, which by the argument above implies that $P$ is not modern. The case where $x\lhd_R y$ is decreasing is similar. 
\end{proof}
\begin{definition}\label{new_ip}
An interval-poset $P$ of size $n$ is called \emph{new} if it has no increasing relation starting at $1$, no decreasing relation starting at $n$, and no relations of the form $i+1 \lhd_P j+1$ and $j\lhd_P i$ for $i < j$.
\end{definition}
Let us define the \emph{lowering}  of an interval-poset $(P,\lhd)$ of size $n$ with no increasing relation starting at $1$ and no decreasing relation starting at $n$. This is the poset $(\Fa(P),\lhd_L)$ where $\Fa(P)$ is the set $\{1,2,\dots, n-1\}$ and the relation $\lhd_L$ is the relation obtained by keeping the decreasing relations and shifting the increasing relations by $-1$. More precisely, $\lhd_L$ is reflexive and for $x<y$, we have $y\lhd_L x$ if and only if $y\lhd x$ and $x \lhd_L y$ if and only if $x+1 \lhd y+1$. 

\begin{lemma}
Let $P$ be an interval-poset of size $n$ with no increasing relation starting at $1$ and no decreasing relation starting at $n$. Then the lowering of $P$ is an interval-poset if and only if $P$ is new. 
\end{lemma}
\begin{proof}
This is a straightforward checking. 
%Since the relations in $\Fa(P)$ are only shifts of the relations of $P$, it is clear that the interval-poset condition holds for $\Fa(P)$.
%
%If $P$ is not new, then we have $i < j$ and two relations $i \lhd j$ and $i+1 \lhd j+1$. They become $i \lhd_F j$ and $j\lhd_F i$ in $\Fa(P)$ which is not a poset.
%
%If we have two relations $i \lhd_F j$ and $j\lhd_F i$ for $i<j$ in $\Fa(P)$, then by construction, we have a relation $i \lhd j$ and $i+1 \lhd j+1$ in $P$, so $P$ is not new.
%
%Similarly to the proof of Lemma \ref{montee}, it is easy to check that the failure of the transitivity of $\lhd_F$ implies the existence of two incompatible relations $i \lhd_F j$ and $j\lhd_F i$ in $\Fa(P)$, so $P$ is not new. 
\end{proof}
\begin{lemma}\label{r/f}
The raising/lowering operations induce two inverse bijections between the set of modern interval-posets of size $n$ and the set of new interval-posets of size $n+1$. 
\end{lemma}
\begin{proof}
The only way to have two relations $i+1 \lhd_R j+1$ and $j\lhd_R i$ for $i < j$ in $\Ri(P)$ is to have $i \lhd j$ and $j\lhd i$ in $P$, so the raise of a modern interval-poset is new. Similarly, the lowering of a new interval-poset $P$ is modern since the forbidden pattern leads to the existence of relations $y-1 \lhd_L y$ and $y+1 \lhd_L y$ that must come from $y+1 \lhd y$ and $y \lhd y+1$ in $P$. 
 
Moreover, it is obvious that the raising and lowering operations are inverse of each other. 
\end{proof}

\begin{proposition}\label{falling}
Let $[S,T]$ be an interval of $\Tam_{n+1}$. Let $P$ be its corresponding interval-poset. Then $P$ is new if and only if there is an interval $[S_1,T_1]$ of $\Tam_{n}$ such that $S = Y\circ_{1} S_1$ and $T=Y \circ_{2} T_1$.
\end{proposition}
\begin{proof}
First we show that there is no increasing relation starting at $1$ in $P$ if and only if there is a tree $T_1$ such that $T=Y \circ_{2} T_1$. Using the left/right symmetry and Lemma~\ref{symmetry} we can deduce that there is no decreasing relation starting at $n+1$ in $P$ if and only if there is a tree $S_1$ such that $S = Y\circ_{1} S_1$. If there is an increasing relation starting at $1$, let $x$ be the maximal element such that we have $1\lhd x$. Then in the forest of increasing relations the first tree has root $x$ and $1$ is in this tree. So it is sent by the bijection of Theorem~\ref{bij} to the binary tree $T$ which has a root $x$ and $1$ is in its left subtree. This implies that the root of $T$ has a left child and $T$ is not of the form $Y \circ_{2} T_1$. Conversely, if the root of $T$ has a left child, then the vertex labeled by $1$ is in the left subtree of $T$. Let $x$ be the label of the root of $T$. Then we have an increasing relation $1\lhd x$ in $P$. 

If $P$ is new, then by the previous argument $S = Y\circ_{1} S_1$ and $T=Y \circ_{2} T_1$. Since $P$ is new, the lowering of $P$ is defined. We will show that the interval corresponding to $\Fa(P)$ is $[S_1,T_1]$. Using the left/right symmetry and Lemma~\ref{symmetry}, it is enough to show that the binary tree corresponding to the decreasing relations of $\Fa(P)$ is $S_1$. If $F$ denotes the forest of decreasing relations of $\Fa(P)$, then the decreasing forest of $P$ is $F\sqcup \{n+1\}$ where $n+1$ is the tree with only one vertex $n+1$. So, the tree corresponding to the decreasing relations of $\Fa(P)$ is the left subtree of the tree of $P$. In other words, it is the tree $S_1$.  

Since $\Fa(P)$ is an interval-poset, the trees $S_1$ and $T_1$ obtained by considering the decreasing relations and the increasing relations satisfy $S_1\leqslant T_1$ in $\Tam_n$. 

Conversely, we assume that $[S_1,T_1]$ is an interval of $\Tam_{n}$ such that $[S,T]$ is an interval of $\Tam_{n+1}$ for $S = Y\circ_{1} S_1$ and $T=Y \circ_{2} T_1$. If we turn $T$ into a binary search tree by using the in-order algorithm, it is easy to see that the root of $T$ is labeled by $1$ and, if $x$ is the label of a vertex of $T_1$, then this vertex is labeled by $1+x$ in $T$. In other words, the increasing relations of $T$ are the increasing relations of $T_1$ shifted by $1$. By symmetry, the interval-poset corresponding to $[S,T]$ is the raise of the interval-poset corresponding to $[S_1,T_1]$. By Lemma~\ref{r/f}, the interval-poset corresponding to $[S,T]$ is new.  
\end{proof}
\subsection{Characterization of the new intervals}
This section is devoted to the proof of the following theorem.
\begin{theorem}\label{not_new_theo}
An interval of the Tamari lattice is new if and only if the corresponding interval-poset is new. 
\end{theorem}
We are going to prove that the intervals that are not new are exactly the intervals whose interval-poset is not new. As first easy case, we consider intervals that do not have the nice shape of Lemma~\ref{new_shape}.
\begin{lemma}\label{red1}
Let $n\in \mathbb{N}^{*}$. Let $[T,S]$ be an interval of $\Tam_n$ that is not of the form $[Y\circ_1 S_1, Y\circ_2 T_1]$ for two trees $S_1$ and $T_1$ of $\Tam_{n-1}$. Then the corresponding interval-poset is not new.
\end{lemma}
\begin{proof}
Assume that the root of the tree $S$ has a right child. Let $x$ be the right-most vertex of $S$. This is the last right descendant of the root of $S$. This vertex is the last vertex visited by the in-order algorithm described in Section~\ref{section1}. So it is labeled by $n$. Let $r$ be the label of the root of $S$. Then in $P$ we have a relation $n\lhd r$ and the poset is not new. Similarly, if the root of $T$ has a left child, there is an increasing relation in $P$ starting at $1$, so the poset is not new. 
\end{proof}
Conversely, we have the following assertion.
\begin{lemma}\label{red2}
Let $P$ be an interval-poset. If there is an increasing relation starting at $1$ or a decreasing relation starting at $n$, then the corresponding interval is not new. 
\end{lemma}
\begin{proof}
If there is a decreasing relation starting at $n$ in $P$, then, in the decreasing forest of $P$, the integer $n$ is not the root of its tree. Using the bijection of Theorem~\ref{bij}, this implies that there is a vertex on the right side of the tree $S$. Similarly, if there is an increasing relation starting by $1$ in $P$, there is a vertex on the left side of the tree $T$. By Lemma~\ref{new_shape}, this implies that the interval $[S,T]$ is not new. 
\end{proof}

With the in-order algorithm, there is a simple relation between the labeling of the vertices and the labeling of the leaves.

\begin{lemma}\label{label_subtree}
Let $S$ be a binary search tree. Let $T$ be a subtree of $S$. Then the vertices of $T$ are labeled by the interval $[i,j-1]$ if and only if the leaves of $T$ are labeled by $[i,j]$.
\end{lemma}

\begin{proof}
The result follows from an easy induction. 
%The proof is obvious for the trees of size $0$ and $1$. Now if $S$ is a binary tree of size $k$. If $T = S$, it is also clear. 
%
%Since the root of $S$ is not the root of $T$, the tree $T$ is either a subtree of the left subtree $L$ of $S$ or of the right subtree $R$ of $S$. We write $T = Y\circ_1 L \circ_2 R$ where $Y$ is the unique binary tree of size $1$. Since the in-order algorithm will run through the left part of $T$ before the right part, a vertex of $L$ has the same label in $L$ and in $T$. The root of $T$ is the first vertex visited by the algorithm after $L$, so it has label $\mathrm{size}(L)+1$ and the label of a vertex of $R$ is shifted by $\mathrm{size}(L)+1$ in $T$. Now a leaf of $L$ has the same label in $T$ and in $L$ and a leaf of $R$ has its label shifted by $\mathrm{size}(L)+1$. The result follows by induction. 
\end{proof}

We can deduce the following lemma.
\begin{lemma}\label{imp1}
Let $[S,T]$ be an interval of $\Tam_n$ such that $S = Y\circ_1 S_1$ and $T = Y\circ_2 T_1$ for two trees $S_1$ and $T_1$ of $\Tam_{n-1}$. If $[S,T]$ is not new, the corresponding interval-poset is not new. 
\end{lemma}
\begin{proof}
By Lemma~\ref{not_new}, there are integers $1<i<j<n+1$, a subtree $A$ of $S$ whose leaves are labeled by $[i,j]$ and a subtree $B$ of $T$ whose leaves are also labeled by $[i,j]$. This implies that the root of $A$ and $B$ are not on the left or right sides of $S$ and $T$. 

By Lemma~\ref{label_subtree}, the vertices of the two subtrees are labeled by $[i,j-1]$. Let $x$ be the label of the root $B$. The left-most vertex of $B$ is labeled by $i$. So, in the poset of increasing relations of $T$ we have $i\lhd x$. The vertex labeled by $j$ (there is such a vertex since $j<n+1$) is the vertex visited by the in-order traversal after $j-1$. Since $j-1$ is the right-most vertex of the tree $B$, the vertex $x$ is in the subtree with root $j$. So, we have $x\lhd j$ and, by transitivity, we have $i\lhd j$.

Similarly, if $y$ is the label of the root of $A$, then we have a decreasing relation $j-1\lhd y$. The vertex labeled by $i-1$ (there is such a vertex since $1<i$) is the vertex visited by the in-order algorithm before the vertex labeled by $i$ which is nothing but the left-most vertex of the tree $S_1$. In particular, $y$ is in the subtree with root $i-1$. So, we have $y\lhd i-1$ and by transitivity $j-1\lhd i-1$. 

In conclusion, the interval-poset corresponding to $[S,T]$ is not new. 
\end{proof}

Conversely, we need to understand how the forbidden configuration of Definition~\ref{new_ip} leads to the existence of a grafting decomposition of the corresponding interval. For this we need to carefully follow the bijection of Ch\^atel and Pons. 

Let $P$ be an interval-poset with no increasing relation starting at $1$ and no decreasing relation starting at $n$. If $P$ is not new, then it has a configuration of the form $i+1 \lhd_R j+1$ and $j\lhd_R i$ for $i < j$. Let $x$ be the maximal element in $[i+1,j]$ such that $i+1 \lhd x$. Note that the interval-poset condition implies that there is a decreasing relation $x\lhd i$. Similarly, let $y$ be the minimal element such that $i< y \leqslant j$ and such that $j \lhd y$. 

\begin{lemma}\label{croissante}
Let $T$ be the upper bound of the interval of $\Tam_n$ corresponding to $P$ by the bijection of Theorem~\ref{bij}. Then the subtree of $T$ with root the vertex labeled by $x$ has leaves labeled by the interval $[i+1,j+1]$. 
\end{lemma}
\begin{proof}
Let $h \leqslant i$. If there is a relation $h \lhd x$, by the interval-poset condition we have a relation $i \lhd x$. This contradicts the decreasing relation $x\lhd i$. 

Moreover, the maximality of $x$ implies that the relation $x\lhd j+1$ is a cover relation in the increasing forest of $P$. Together with the previous argument, this shows that $x$ is the left-most child of $j+1$ in the increasing forest of $P$. 

The relation $i+1 \lhd j+1$ and the interval-poset condition imply the existence of the relation $j \lhd j+1$. Clearly, $j$ is the right-most child of $j+1$ in the increasing forest of $P$. 

So, in the tree $T$, the vertex $j$ is the right-most descendant of $x$ and $x$ is the left child of $j+1$. In other words, $j$ is the largest vertex of the subtree with root $x$. Since we have $i+1 \lhd x$, there is a vertex labeled by $i+1$ in the subtree with root $x$. The first argument of the proof implies that this is the smallest vertex of this subtree. So it has its vertices labeled by the interval $[i+1,j]$. Finally, by Lemma~\ref{label_subtree} its leaves are labeled by $[i+1,j+1]$. 
%In the increasing forest of $P$, the subtree with root $j+1$ has vertices in $[i+1,j]$. Indeed, if there is $h \leqslant i < k \leqslant j$ with a relation $h\lhd k$. Then, by the interval-poset condition we have $i\lhd k$. Moreover, using the decreasing relation $j \lhd i$ and the interval-poset condition, we have a decreasing relation $k \lhd i$. 
%
%The interval-poset condition implies that there is a relation $x\lhd j+1$. Moreover, the maximality of $x$ implies that $x \lhd j+1$ is a cover relation. With the previous argument, we have that $x$ is the left-most son of $j+1$ in the increasing forest of $P$. 
%
%If there is $h \lhd k$ for $h < i$ and $i\leqslant k <j$. 
%Since $i < x < j$, and $i\lhd j$, the interval-poset condition implies the existence of the relation $x\lhd j$. Moreover, if  there is $y$ such that $x\lhd y \lhd j$, then by transitivity we have $i\lhd y$ so by maximality of $x$ we have $y=x$ or $y=j$. In other terms, $x\lhd j$ is a \emph{cover relation}. Moreover, $x$ is the smallest integer $y$ of $[i,j-1]$ such that $y\lhd n$ is a cover relation. Indeed, if $i<y < x < j$ such that $y\lhd j$, since we have a relation $i\lhd x$, the interval-poset condition implies that $y \lhd x$ and so, the relation $y \lhd j$ is not a cover relation. In other terms, $x$ is the left most child of $j$ in the increasing forest of $P$. 
%
%Let $A_x$ be the subtree of $T$ with root $x$. Since $i+1 \lhd x$, then the vertex labeled by $i+1$ is in the tree $A_x$. Moreover, since we don't have any relation of the form $h \lhd x$ for $h \leqslant i$, this implies that there is no vertex labeled by elements of $[1,i]$ in the tree $A_x$. And that $i+1$ is the smallest vertex of $A_x$.
%
%The interval-poset condition implies that $j \lhd j+1$. Moreover, this is obviously the largest (in the sense of integers) cover relation since we look at increasing relations here. So $j$ is the right most child of $j+1$ in the increasing forest of $P$. Since $x$ is the left most child, this implies that $j$ the right most brother of $x$. Since the bijection of Theorem \ref{bij}, sends right brother to right son, we have that $j$ is the right-most vertex of $A_x$. 
%
%The set of integers labeling the vertices of a subtree is an interval, so the tree $A_x$ has its vertices labeled by the interval $[i+1,j]$. So by, Lemma \ref{label_subtree} its leaves are labeled by $[i+1,j+1]$. 
%
%Let us first assume that we have the poset $P = \{1,\cdots,n\}$ with the relation $1\lhd n$ and let $x$ be the maximal element strictly smaller than $n$ such that $1 \lhd x$. By the interval-poset condition, we also have the relation $x\lhd n$ and this relation is a \emph{cover relation}. Indeed, if $x\lhd y \lhd n$, then by transitivity we have $1\lhd y$ and by maximality of $x$, $y=x$ or $y=n$. Moreover, $x$ is the smallest element $y$ such that $y\lhd n$ is a cover relation. Indeed, if $y < x < n$ such that $y\lhd n$, since we have a relation $1\lhd x$, the interval-poset condition implies that $y \lhd x$ and so, the relation $y \lhd n$ is not a cover relation. In other words, in the forest of the increasing relations of the poset $P$ we have a unique tree with root $n$ and $x$ is the first son of $x$ in the left to right order. Using the bijection detailed in Theorem \ref{bij} this means that $x$ labeled the left son of the root of the binary tree $T$. Since $n$ has no brother in the forest, the root of $T$ has no right son. So the left subtree of $T$ with root $x$ has leaves labeled by the integers from $1$ to $n$. 
%
%By induction on the size of the poset we show that it is enough to consider this case. The result of the Lemma is trivial for posets of size $0$ and $1$. For the poset of size $2$ the only case that we have to consider is $1\lhd 2$ and it has been treated by the argument above.  
%
%If there is more than one connected components in the poset $P$, then the forest of increasing relations is a union of trees $A_1,\cdots A_k$. An integer $x$ is the tree $A_i$ if and only if $x \lhd r_i$ where $r_i$ is the root of the tree. Let $x < y < r_i$. Then, the interval-poset condition implies that $y\lhd r_i$. So, the integers in a tree $A_i$ form an interval $[n_i,m_{i}]$. The trees are organized in such a way that if $i < j$, then the integers of the interval of $A_i$ are smaller than the integers of the tree $A_j$. By the bijection, the forest is sent to a binary tree $T$ where the root is the root $r_1$ of the first tree $A_1$. The roots $r_2$ of the tree $A_2$ is the right son of the root of $T$, and more generally the root $r_{i+1}$ of $A_{i+1}$ is the left son of the root $r_i$ of $A_i$. The left subtree of the $r_1$ has leaves labeled by the interval $[1,m_1]$, and more generally the left subtree of the root $r_i$ has leaves labeled by the interval $[n_i,m_i]$. In terms of operads, the tree $T$ is obtained by successively grafting the tree $T_{i+1}$ on the right-most leaf of $T_{i}$. 
%
%The configuration $i \lhd x \lhd j$ is in a subtree $A_k$. By subtracted $n_k -1$ to every element, we obtain an interval poset on the set $\{1,\cdots, m_k-n_k+1\}$. Let $T_k$ be the binary tree corresponding to this interval-poset. By induction, its subtree with root $x-n_k+1$ has leaves labeled by $[i-n_k +1,j-n_k+1]$. By shifting back the integers by $n_k-1$ we have that the subtree with root $x$ has leaves labeled by the interval $[i,j]$.  
%
%Now if the poset $P$ has only one tree in its forest. This implies that there is a unique connected components and in particular a unique maximal element, which has to be $n$ since we only consider increasing relations. Then, if the element $j$ in the configuration is not $n$, the forest has the following shape. There is a unique root $n$ and this root has several sons $s_1,\cdots,s_k$. By the bijection the forest is sent to a binary tree $T$ with root labeled by $n$. Since there is only one tree in the forest, the root of $T$ does not have any right son. In particular, we see that the tree $T$ is the grafting of the tree $T_1$ obtained by the sub-poset $\{1,2,\cdots, n-1\}$ on the tree of size $1$. By induction, the subtree with root $x$ of $T_1$ has leaves labeled by $[i,j]$. The result follows since the labels of $T_1$ and its grafting in $T$ are the same. So, we can assume that $j=n$.
%
%If $i$ is not $1$, by the assumption of the Lemma, there is no relation $h\lhd y$ for $h < i$ and $i \leqslant y <n$. This implies that the elements of $[1,h-1]$ are not smaller, for $\lhd$, than $x$. So the poset $P$ has the shape $P_1 \sqcup P_2$, where $P_1 = \{1,2,\cdots i-1\}$ and $P_2 = \{i,\cdots, n\}$. $P_1$ and $P_2$ are two posets and every element of $P_1$ is smaller than $n$ for the relation $\lhd$. Let $T_1$ the binary tree corresponding to the poset $P_1\sqcup \{n\}$ and $P_2$ the binary tree corresponding to $P_2$. 
%
%The forest of $P$ has the following shape: one root $n$, and several sons. One of them is $x$, and on the left of $x$ there are some elements $r_1,\cdots, r_k$ of $[1,i-1]$. So, this forest is sent to a binary tree $T$ is the tree obtained by the following procedure: let $T_2'$ be the subtree of $T_2$ with root $x$. Then, $T$ is the tree obtained by grafting the tree $T_2'$ on the leaf on the right of the left most leaf of $T_1$. The tree $T_1$ has $i$ vertices, so it has $i+1$ leaves. The tree $T_2$ has leaves indexed from $i$ to $n+1$ and by the first argument of the proof, the subtree with root $x$ has leaf labeled by $[i,n]$. Since it is grafted on the $i$-th leaf of $T_1$ we have the result. 
\end{proof}
Dually, we have a similar result for the decreasing relations.
\begin{lemma}\label{decroissante}
Let $S$ be the lower bound of the interval of $\Tam_n$ corresponding to $P$ by the bijection of Theorem~\ref{bij}. 
Then the subtree of $S$ with root the vertex labeled by $y$ has leaves labeled by the interval $[i+1,j+1]$. 
\end{lemma}
\begin{proof}
This is a straightforward application of Lemma~\ref{symmetry} to Lemma~\ref{croissante}. 
\end{proof}
%If we apply the symmetry of Lemma \ref{symmetry}, the interval $P$ is sent to an interval poset with increasing relations of the form $n-j+1 \lhd n-x+1 \lhd n-i+1$. This poset satisfies the conditions of Lemma \ref{croissante}. So the subtree with root $n-x+1$ has leaves indexed by $[n-j+1,n-i+1]$. Now this tree is the left/right symmetry of the tree of $P$. Applying this symmetry, we see that the tree with root $x$ has leaf labeled by $[i+1,j+1]$, since the leaf $k$ of the tree is sent to the leaf $n+1-(k-1)$ under this symmetry.  


%\begin{theorem}\label{new_new}
%An interval of the Tamari lattice is new if and only if the corresponding interval poset is new. 
%\end{theorem}
%\begin{proof}[Proof of Theorem \ref{not_new}] 
%We denote by $P$ the interval-poset corresponding to $[S,T]$. Let us recall that the increasing relations of $P$ come from the tree $T$ and the decreasing relations come from $S$. 
%
%If the root of the tree $S$ has a right son. Let $x$ be the right-most vertex of $S$. This is the last right descendant of the root of $S$. This vertex is the last vertex visited by the in-order algorithm describe in Section \ref{section1}. So it is labeled by $n$. Let $r$ be the label of the root of $S$. Then, in $P$ we have a relation $n\lhd r$. So the poset is not new. Similarly, if the root of $T$ has a left son, there is an increasing relation in $P$ starting at $1$, so the poset is not new. 
%
%If $[S,T]$ is an interval as in Lemma \ref{new_shape} but is not new. There are integers $1<i\leqslant j<n+1$, a subtree $S_1$ of $S$ whose leaves are labeled by $[i,j]$ and a subtree $T_1$ of $T$ whose leaves are also labeled by $[i,j]$. By Lemma \ref{label_subtree}, the vertices of the two subtrees are labeled by $[i,j-1]$. Let $x$ be the label of the root $T_1$. By Lemma \ref{label_subtree}, the left-most vertex of $T_1$ is labeled by $i$. So, in the poset of increasing relations of $T$ we have $i\lhd x$. The vertex labeled by $j$ (there is such a vertex since $j<n+1$) is the vertex visited by the in-order traversal after $j-1$. Since $j-1$ is the most-right vertex of the tree $T_1$, the vertex $x$ is in the subtree with root $j$. So we have $x\lhd j$ and by transitivity, we have $i\lhd j$.
%
%Similarly if $y$ is the label of the root of $S_1$, then we have a decreasing relation $j-1\lhd y$. The vertex labeled by $i-1$ (there is such a vertex since $1<i$) is the vertex visited by the in-order algorithm before the vertex labeled by $i$ which is nothing but the left most vertex of the tree $S_1$. In particular, $y$ is in the subtree with root $i-1$. So we have $y\lhd i-1$ and by transitivity $j-1\lhd i-1$. 
%
%In conclusion, the interval-poset corresponding to $[S,T]$ is not new. 
%
%Conversely, if there is a decreasing relation starting by $n$ in $P$, it means that in the decreasing forest of $P$, the integer $n$ is not the root of its tree. Using the bijection of Theorem \ref{bij}, we see that this implies that there is a vertex on the right side of the tree $S$. Similarly, if there is an increasing relation starting by $1$ in $P$, there is a vertex on the left side of the tree $T$. By Lemma \ref{new_shape}, this implies that the interval $[S,T]$ is not new. 
%
%
%Now let us assume that $P$ has no increasing relation starting at $1$ and no decreasing relation starting at $n$. If it is not new, it has a configuration of the form $i+1 \lhd_R j+1$ and $j\lhd_R i$ for $i < j$. We need to check that the poset of increasing relations satisfies the conditions of Lemma \ref{croissante} and the poset of decreasing relations satisfies the conditions of Lemma \ref{decroissantes}. 
%
%Let $x\in [i+1,j]$ and $h\in [1,i]$. If $h\lhd x$, then the interval-poset condition implies that $i\lhd x$. But, using the decreasing relation $j\lhd i$, the interval-poset condition implies $x\lhd i$ which is not possible. Similarly the condition for the decreasing relations is satisfied. So, the tree $T$ has a subtree whose leaves are labeled by $[i+1,j+1]$ and the tree $S$ has a subtree whose leaves are labeled by $[i+1,j+1]$. By Lemma \ref{not_new}, the interval $[S,T]$ is not new. 
%\end{proof}
\begin{proof}[Proof of Theorem \ref{not_new_theo}] 
By Lemmas~\ref{red1} and~\ref{imp1}, if an interval is not new, then its corresponding interval-poset is not new. Conversely, using Lemma~\ref{red2}, we may assume that $P$ does not have an increasing relation starting at $1$ nor a decreasing relation starting at $n$. Let $[S,T]$ be the corresponding interval. Then, by Lemmas~\ref{croissante} and~\ref{decroissante} and the discussion before them, in $S$ and $T$ there are two subtrees whose leaves are labeled by the same interval. Lemma~\ref{not_new} implies that $[S,T]$ is not new. 
\end{proof}
As a corollary, we also have a characterization in terms of modern interval-posets. 
\begin{corollary}\label{coro_modern}
Let $n\in \mathbb{N}$. There is a bijection between the set of new intervals of $\Tam_{n+1}$ and the set of modern interval-posets of size $n$.
\end{corollary}
\begin{proof}
By Theorem~\ref{not_new_theo}, an interval of $\Tam_{n+1}$ is new if and only if its corresponding interval-poset is new. By Lemma~\ref{r/f}, these interval-posets are in bijection with the modern interval-posets of size $n$. 
\end{proof}
As explained in Lemma~\ref{new_shape}, it is easy to see that, if an interval $[S,T]$ is new, then $S = Y\circ_{1} S_1$ and $T=Y \circ_{2} T_1$ where $Y$ is the unique binary tree of size $1$. However, this is not a sufficient condition. Using our characterization of new intervals in terms of interval-posets, we can find a characterization of the new intervals of the Tamari lattice.
\begin{theorem}\label{new_chara}
Let $[S,T]$ be an interval of $\Tam_{n+1}$. Then $[S,T]$ is a new interval if and only if there is an interval $[S_1,T_1]$ in $\Tam_n$ such that $S = Y\circ_{1} S_1$ and $T = T\circ_2 T_1$. 
\end{theorem}
\begin{proof}
By Theorem~\ref{not_new_theo}, the new intervals of $\Tam_{n+1}$ are exactly the intervals such that the corresponding interval-poset is new. The result follows from Proposition~\ref{falling}. 
\end{proof}

\section{Infinitely modern interval-posets}
For an integer $k$ and an interval-poset $P$ of size $n$, we let $\Ri^{k}(P)$ the $k$-th raise of $P$. 
\begin{definition}
An interval-poset is infinitely modern if $\Ri^{k}(P)$ is an interval-poset for every $k\geqslant 1$. 
\end{definition}
\begin{lemma}\label{inf}
An interval-poset $P$ is infinitely modern if and only if it does not contain any configuration of the form $w\lhd x$ and $z\lhd y$ for $w < x < y < z$. 
\end{lemma}
\begin{proof}
If we have such a configuration in $P$, then the interval-poset condition implies the existence of relations $x-1\lhd x$ and $y+1\lhd y$. After raising our poset sufficiently many times, we will have two contradictory relations $y\lhd_{R^k} y+1$ and $y+1\lhd_{R^k} y$.

Conversely, let $k+1$ be the smallest integer such that $\Ri^{k+1}(P)$ is not a poset. Then $\Ri^{k}(P)$ is not modern and by Definition~\ref{def_modern} there is a configuration of the form $x\lhd_{R^{k}} y$ and $z\lhd_{R^k} y$ for $x < y < z$ in $\Ri^{k}(P)$. This leads to the result. 
% Conversely, let $k$ be the smallest integer such that $\Ri^{k}(P)$ is not a poset. If there is a relation $x\lhd y$ and a relation $y\lhd x$ for $y < x$. Then, in $\Ri^{k-1}(P)$ we have $x-1\lhd y-1$ and $x\lhd y$. The interval-poset condition implies that $y-1\lhd x$ and $x\lhd y-1$. Since $\Ri^{k-1}(P)$ is a poset, we have $y-1 = x$. And in $P$ there is a relation $t\lhd t+1$ for $t< t+1 < x < y$. Similarly to the proof of Lemma \ref{montee} the failure of transitivity of $\Ri^{k}(P)$ implies the existence of two non compatible relations $x\lhd y$ and $y\lhd x$. In both cases, we see that if $\Ri^{k}(P)$ is not an interval, then $P$ is not infinitely modern. 
\end{proof}
For an interval-poset $P$ of size $n$, we denote by $\ir(P)$ the smallest integer $k$ such that there is an \underline{i}ncreasing \underline{r}elation $k \lhd k+1$. If there is no increasing relation, we use the convention that $\ir(P)=n$. Similarly, we denote by $\id(P)$ the largest integer $i$ such that there is a \underline{d}ecreasing \underline{r}elation $i\lhd i-1$. If there is no decreasing relation, we use the convention that $\id(P)=1$. We can associate to any interval-poset $P$ of size $n$ the double statistic $\big(\ir(P),\id(P)\big)$ which is a pair of elements of $\{1,2,\dots,n\}$. Using this statistic, we have another description of the infinitely modern interval-posets.
\begin{proposition}\label{stat}
Let $P$ be an interval-poset of size $n$. Then $P$ is infinitely modern if and only if $\id(P) \leqslant \ir(P)$.
\end{proposition}
\begin{proof}
If $\ir(P) < \id(P)$, then the poset is not infinitely-modern because, after some raises, the relation $k\lhd k+1$ will contradict the relation $i\lhd i-1$. Conversely, if the poset is not infinitely modern, by Lemma~\ref{inf}, there are integers $w < x < y < z$ such that $w\lhd x$ and $z\lhd y$. By the interval-poset condition, we have relations $x-1\lhd x$ and $y+1\lhd y$. In particular, we see that $\ir(P) < \id(P)$. 
\end{proof}

We denote by $\operatorname{IM}(n,i,k)$ the set of infinitely modern interval-posets $P$ of size $n$ such that $\ir(P) = k$ and $\id(P)=i$. 

Let $1 \leqslant i \leqslant k \leqslant n+1$ and $P$ be an interval-poset of size $n$. Then we define a relation $f_{i,k}(P)$ on the set with $n+1$ elements by adding a new point to the set of $P$. For the increasing relations, the new point is inserted at $k$ and we add a new increasing relation from $k$ to $k+1$. For the decreasing relations, we may think that the new point is inserted at the position $i$ and we add a new relation $i\lhd i-1$. The old relations of $P$ are modified accordingly to the positions of the new point. 

More formally, $f_{i,k}(P)$ is defined as the set $\{1,2,\dots, n+1\}$ with the relation $\lhd'$: 
\begin{itemize}
\item We have $k \lhd' k+1$ and $i\lhd' i+1$ with the convention that there are no increasing relations when $k=n+1$ and no decreasing relations when $i=1$.
\item Let us assume that we have an increasing relation $x\lhd y$ in $P$. If $x<y<k$, then we have the relation $x\lhd'y$ in $f_{i,k}(P)$. If $x < k \leqslant y$, then we have the relation $x\lhd' y+1$ in $f_{i,k}(P)$.  If $k \leqslant x < y$, then we have the relation $x+1 \lhd' y+1$.
\item Let us assume that we have a decreasing relation $y \lhd x$ in $P$. If $i \leqslant x < y$, then we have the relation $y+1 \lhd'x+1$. If $x< i\leqslant y$, then we have the relation $y+1 \lhd x$. If $x<y <i$, then we have the relation $y\lhd x$. 
\item Take the transitive closure of the relation $\lhd'$. 
\end{itemize}
\begin{figure}
\centering
\begin{tikzpicture}
\node (1) at (0,0) {1}; \node (2) at (1,0) {2}; \node (3) at (2,0) {3}; \node (4) at (3,0) {4}; \node (5) at (4,0) {5};
\draw[red,->,below,thick] (4.south) to [out=-45,in=225] (5.south);
\draw[blue,thick,->] (2.north) to  [out=140,in=50] (1.north);
\draw[red,->,below, thick] (3.south) to [out=-45,in=225] (5.south);
\draw[blue,thick,->] (3.north) to [out =140 ,in =45] (1.north);
\end{tikzpicture}
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\begin{tikzpicture}
\node (1) at (0,0) {1}; \node[fill=blue!20, shape=circle] (2) at (1,0) {2}; \node (3) at (2,0) {3}; \node[fill=red!20, shape=circle] (4) at (3,0) {4}; \node (5) at (4,0) {5}; \node (6) at (5,0) {6};
\draw[thick,blue,->] (2.north) to  [out=140,in=50] (1.north);
\draw[dashed,below, thick] (3.south) to [out=-60,in=-115] (6.south);
\draw[red,->,below,thick] (4.south) to [out=-45,in=-115](5.south);
\draw[red,->,below,thick] (4.south) to [out=-45,in=-115](6.south);
\draw[dashed,below, thick] (5.south) to [out=-60,in=-115] (6.south);
\draw[dashed,above,thick] (4.north) to [out=135,in=65](1.north);
\draw[dashed,above,thick] (3.north) to [out=135,in=65](1.north);
\end{tikzpicture}
\caption{On the left, an interval-poset $P$ of size $5$. On the right, the construction $f_{2,4}(P)$. The vertex in red represents the position of the new point for the increasing relations. The vertex in blue represents the position of the new point for the decreasing relations. The new arrows are displayed in thick red and blue. The black dashed arrows correspond to the old relations of $P$. The long red arrow is obtained by transitivity.}
\end{figure}
\begin{lemma}\label{double}
Let $1\leqslant i \leqslant k \leqslant n+1$. Let $i'\leqslant i$ and $k-1\leqslant k'$. Let $P \in \operatorname{IM}(n,i',k')$. Then $f_{i,k}(P)$ is an interval-poset of size $n+1$ in $\operatorname{IM}(n+1,i,k)$. 
\end{lemma}
\begin{proof}
If we have a decreasing relation $ y \lhd x$ in $P$, by the interval-poset condition, we also have a relation $x+1 \lhd x$. This implies that, in $P$, all the decreasing relations are of the form $y\lhd x$ where $x < y$ and $x < i'$. Since $i'\leqslant i$, in $f_{i,k}(P)$ all the decreasing relations are of the form $y'\lhd x'$ where $x' < i$. Moreover, we have a decreasing relation $i \lhd i-1$ in $f_{i,k}(P)$. In other terms, we have $\id(f_{i,k}(P)) = i$.

Similarly, in $P$ all the increasing relations are of the form $x \lhd y$ with $x < y$ and $k'+1 \leqslant y$. Since $k\leqslant k'+1$, all the increasing relations in $f_{i,k}(P)$ are of the form $x' \lhd y'$ where $k < y'$. By construction in $f_{i,k}(P)$, we have the relation $k\lhd k+1$. So, $\ir(f_{i,k}(P)) = k$.

It remains to check that under the hypothesis $f_{i,k}(P)$ is an interval-poset. Let $x< y$ such that $x\lhd y$ and $y \lhd x$ in $f_{i,k}(P)$. Since the increasing relations land after $k$ and the decreasing before $i$, the only possibility is to have $x < i < k < y$. This means that in $P$, we have a relation $x \lhd y-1$ and $y\lhd y-1$. This is not possible since $P$ is a poset. Since the relation $\lhd'$ is transitive by construction, this shows that $f_{i,k}(P)$ is a poset. 

We need to check the interval-poset condition. It is an easy case by case checking: let $x<y < z$ and $x\lhd z$ in $f_{i,k}(P)$. If $x < k < y$, then in $P$ we have the relation $x \lhd y-1$. If $k\neq z$, since $P$ is an interval-poset, we have the relation $z' \lhd y-1$ for $z'=z$ if $z'<k$ and $z' = z-1$ otherwise. So, in $f_{i,k}(P)$, we have $z\lhd y$. If $z=k$, then in $f_{i,k}(P)$ we have the relation $k\lhd k+1$. By the interval-poset condition of $P$, we have $k\lhd y-1$. It becomes $k+1 \lhd y$ in $f_{i,k}(P)$. By transitivity, we have $k\lhd y$. Similarly, we can check the case where $k \leqslant x \leqslant y$. For the decreasing relations, the proof is similar. 
\end{proof}

On the other hand, if $P$ is an interval-poset in $\operatorname{IM}(n+1,i,k)$ let us construct $\rho(P)$ an interval-poset of size $n$. Informally, for the increasing relations, we remove the vertex $k$ and the relation $k\lhd k+1$. We shift the other relations accordingly to their position. For the decreasing relations, we remove the vertex $i$ and the relation $i\lhd i-1$. Furthermore, we shift the relations accordingly to their position. More formally, $\rho(P)$ is the relation on the set $\{1,2,\dots, n\}$ defined by:
\begin{itemize}
\item Let $x < y$. Then we have a relation $x\lhd y$ in the following two cases: if $x < k < y+1$ and there is a relation $x\lhd y+1$ in $P$, or if $k < x+1 < y+1$ and there is a relation $x+1 \lhd y+1$ in $P$.
\item Let $x < y$. Then we have a relation $y\lhd x$ in the following two cases: if $x  < y  < i$ and there is a relation $y\lhd x$ in $P$ or if $x < i < y+1 $ and there is a relation $ y+1 \lhd x$ in $P$.
\end{itemize}
\begin{lemma}\label{coupe}
Let $P \in \operatorname{IM}(n+1,i,k)$. Then $\rho(P)$ is an infinitely modern interval-poset such that $\id(P) \leqslant i$ and $k-1 \leqslant \ir(P)$. 
\end{lemma}
\begin{proof}

In $P$ the increasing relations are of the form $y \lhd x$ where $ k < x$. If we have the relation $k-1 \lhd k+1$ in $P$, then we have the relation $k-1 \lhd k$ in $\rho(P)$. Otherwise the second increasing relation $x\lhd x+1$ of length $1$ in $P$ (the one after $k\lhd k+1$) appears for $k+1 \leqslant k$. Here we use one more time the convention that there is an increasing relation starting at $n+1$ if there is no such relation. So, in $\rho(P)$ the first increasing relation is $x-1\lhd x$ and we have $k-1 \leqslant \ir(P)$. Moreover, we have $\ir(P) = k-1$ if and only if we have the relation $k-1\lhd k+1$ in $P$.

Similarly, we have $\id(P) \leqslant i$ and $\id(P) = i$ if and only if we have the relation $i-1\lhd i+1$ in $P$. 

Now, we check that $\rho(P)$ is an interval-poset. By the description of $\ir(\rho(P))$ and $\id(\rho(P))$, we deduce that, if $x\lhd y$ is an increasing relation in $\rho(P)$, we have $k\leqslant y$. Similarly, if $y\lhd x$ is a decreasing relation we have $x < i $. 

Let $x < y$ such that $x\lhd y$ and $y \lhd x$ in $\rho(P)$. Then we must have $x < i$ and $k\leqslant y$. So, the relation $x\lhd y$ comes from the relation $x \lhd y+1$ in $P$ and the relation $y\lhd x$ comes from the relation $y+1 \lhd x$ in $P$. Since $P$ is an interval-poset, this is not possible. In $P$ there are no increasing relations of the form $x\lhd k$ and no decreasing relations of the form $y\lhd i$, so removal of the relations $k\lhd k+1$ and $i\lhd i-1$ will not break the transitivity of the relation. Checking the interval-poset condition is straightforward and similar to the proof of Lemma~\ref{double}. 


If $i < k$, as a direct consequence of Proposition~\ref{stat}, the interval-poset $\rho(P)$ is infinitely-modern. If $i = k$, we have to check that it is not possible to have $\ir(\rho(P)) = k-1$ and $\id(\rho(P)) = i$. But this is a direct consequence of the description of these two particular cases obtained above. 
\end{proof}

\begin{proposition}\label{prop_calc}
Let $n \in \mathbb{N}$. Let $1\leqslant i \leqslant k \leqslant n+1$. Then we have a bijection 
\[ f_{i,k} : \bigcup_{\substack{1\leqslant i' \leqslant i \\ k-1\leqslant k' \leqslant n}} \operatorname{IM}(n,i',k') \to \operatorname{IM}(n+1,i,k) .\]
\end{proposition}
\begin{proof}
By Lemma~\ref{double}, $f_{i,k}$ maps the left-hand side to the right-hand side, and by Lemma~\ref{coupe}, the map $\rho$ goes from the right-hand side to the left-hand side. It is clear that $\rho$ and $f_{i,k}$ are two bijections inverse of each other. 
\end{proof}
\begin{theorem}\label{theo_inf}
Let $n\in \mathbb{N}$. Then the number of infinitely modern interval-posets of size $n$ is $\frac{1}{2n+1} {\binom{3n}{n}}$.
\end{theorem}
\begin{proof}
Let $k,l \in \{0,1,\dots,n-1\}$. We set $B(n,k,l) = |\operatorname{IM}(n,k+1,n-l)|$. With the change of variables $x -1 = k$ and $ n-y = l$, this is the number of infinitely modern interval-posets of size $n$ with $\ir = y$ and $\id = x$. It is easy to check that we have $B(1,0,0) = 1$. By Lemma~\ref{stat}, if $P$ is an interval-poset such that $\ir(P) < \id(P)$, then $P$ is not infinitely-modern. So, if $k+l \geqslant n$, we have $B(n,k,l) = 0$. Finally, if $k+ l < n$, then $1\leqslant x \leqslant y \leqslant n$ and Proposition~\ref{prop_calc} implies 
\[B(n,k,l) = \sum_{0\leqslant i \leqslant k, 0\leqslant j \leqslant k}B(n-1,i,j). \]
We recognize the sequence of \cite[Definition~$2.1$]{aval}. The result follows from \cite[Proposition~$2.1$]{aval}. 
\end{proof}

\begin{thebibliography}{CHNT08}

\bibitem[Ara13]{araya}
T.~Araya.
\newblock Exceptional sequences over path algebras of type {$A_n$} and
  non-crossing spanning trees.
\newblock {\em Algebr. Represent. Theory}, 16(1):239--250, 2013.

\bibitem[Ava08]{aval}
J.-C. Aval.
\newblock Multivariate {F}uss--{C}atalan numbers.
\newblock {\em Discrete Math.}, 308(20):4660--4669, 2008.

\bibitem[BB09]{bernardi_bonichon}
O.~Bernardi and N.~Bonichon.
\newblock Intervals in {C}atalan lattices and realizers of triangulations.
\newblock {\em J. Combin. Theory Ser.~A}, 116(1):55--75, 2009.

\bibitem[BK04]{buan_krause}
A.~B. Buan and H. Krause.
\newblock Tilting and cotilting for quivers and type {$\tilde A_n$}.
\newblock {\em J. Pure Appl. Algebra}, 190(1-3):1--21, 2004.

\bibitem[Cha07]{chapoton_mould}
F.~Chapoton.
\newblock The anticyclic operad of moulds.
\newblock {\em Int. Math. Res. Notices}, (20):Art.~ID rnm078, 36, 2007.

\bibitem[Cha12]{chapoton_modules}
F.~Chapoton.
\newblock On the categories of modules over the {T}amari posets.
\newblock In {\em Associahedra, {T}amari lattices and related structures},
  volume 299 of {\em Prog. Math. Phys.}, pages 269--280. Birkh\"auser/Springer,
  Basel, 2012.

\bibitem[Cha16]{chapoton_stokes}
F.~Chapoton.
\newblock Stokes posets and serpent nests.
\newblock {\em Discrete Math. Theor. Comput. Sci.}, 18(3):1365--8050, 2016.

\bibitem[Cha17]{chapoton_interval}
F.~Chapoton.
\newblock Une note sur les intervalles de Tamari.
\newblock {\em Ann. Math. Blaise Pascal}, 25(2):299--314, 2018.

\bibitem[CHNT08]{chapoton_etal_mould}
F.~Chapoton, F.~Hivert, J.-C. Novelli, and J.-Y. Thibon.
\newblock An operational calculus for the mould operad.
\newblock {\em Int. Math. Res. Notices}, (9):Art.~ID rnn018, 22, 2008.

\bibitem[CP15]{pons_chatel}
G.~Ch\^atel and V.~Pons.
\newblock Counting smaller elements in the {T}amari and {$m$}-{T}amari
  lattices.
\newblock {\em J. Combin. Theory Ser.~A}, 134:58--97, 2015.

\bibitem[CPP17]{chatel_pilaud_pons}
G.~Ch\^atel, V.~Pilaud, and V.~Pons.
\newblock The weak order on integer posets.
\newblock {\em Algebr. Combin.}, 2(1):1--48, 2019.

\bibitem[dBM67]{bruijn_morselt}
N. G. de~Bruijn and B. J. M. Morselt.
\newblock A note on plane trees.
\newblock {\em J. Combin. Theory}, 2(1):27--34, 1967.

\bibitem[DP93]{dulucq}
S. Dulucq and J.-G. Penaud.
\newblock Cordes, arbres et permutations.
\newblock {\em Discrete Math.}, 117(1-3):89--105, 1993.

\bibitem[Ede82]{edelman}
P.~H. Edelman.
\newblock Multichains, noncrossing partitions and trees.
\newblock {\em Discrete Math.}, 40(2-3):171--179, 1982.

\bibitem[Gab81]{gabriel}
P.~Gabriel.
\newblock Un jeu? {L}es nombres de {C}atalan.
\newblock {\em Z\"urich uni}, Mitteilungsblatt des Rektorats,
12.~Jahrgang, Heft 6:4--5, 1981.

\bibitem[HPT64]{HPGT}
F.~Harary, G.~Prins, and W.~T. Tutte.
\newblock The number of plane trees.
\newblock {\em Nederl. Akad. Wetensch. Proc. Ser.~A 67=Indag. Math.},
  26:319--329, 1964.

\bibitem[HU05]{happel_tilting}
D.~Happel and L.~Unger.
\newblock On a partial order of tilting modules.
\newblock {\em Algebr. Represent. Theory}, 8(2):147--156, 2005.

\bibitem[Kre72]{kreweras}
G.~Kreweras.
\newblock Sur les partitions non crois\'ees d'un cycle.
\newblock {\em Discrete Math.}, 1(4):333--350, 1972.

\bibitem[Rea06]{reading}
N.~Reading.
\newblock Cambrian lattices.
\newblock {\em Adv. Math.}, 205(2):313--353, 2006.

\bibitem[Rog18]{rognerud_cyf}
B. Rognerud.
\newblock The bounded derived categories of the Tamari lattices are
  fractionally Calabi--Yau.
\newblock preprint; {\tt arXiv:1807.08503}.

\bibitem[Tam62]{tamari}
D.~Tamari.
\newblock The algebra of bracketings and their enumeration.
\newblock {\em Nieuw Arch. Wisk. (3)}, 10:131--146, 1962.

\end{thebibliography}



\end{document}
