\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
\usepackage{mathrsfs}
\usepackage{tikz}
\usetikzlibrary{patterns}
%\usepackage{cleveref}
\usepackage[capitalize]{cleveref} % Can add 'nameinlink' option to have the name included in hyperlink
\crefname{coro}{Corollary}{Corollaries}
\crefname{defi}{Definition}{Definitions}
\crefname{lemm}{Lemma}{Lemmas}
\crefname{prop}{Proposition}{Propositions}
\crefname{rema}{Remark}{Remarks}
\crefname{theo}{Theorem}{Theorems}
%\crefname{equation}{}{}
%\crefname{enumi}{}{}
\newcommand{\creflastconjunction}{, and\nobreakspace} % For Oxford comma
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\ov}[1]{\overline{#1}}
\newcommand{\oeis}[1]{\href{https://oeis.org/#1}{{#1}}}
\newcommand{\defin}[1]{\emph{\color{red}{#1}}}
\newcommand{\level}{\mathscr{L}}
\newcommand{\Dyck}{\mathscr{D}}
\newcommand{\mono}{\overline{\mathbb{M}}_1}
\newcommand{\monod}{\mathbb{M}_1}
\newcommand{\monoi}{\mathbb{M}_2}
\newcommand{\sm}{\leq}
\newcommand{\wmin}{w_{\min}}
\newcommand{\pscolle}{\ast}
\newcommand{\colle}{\,\sharp\,}
\newcommand{\deri}{\mathsf{D}}
\DeclareMathOperator{\up}{Up}
\DeclareMathOperator{\des}{Desc}
\DeclareMathOperator{\rise}{Rise}
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
\author{\firstname{Frédéric} \lastname{Chapoton}}
\address{%
Institut de Recherche Mathématique Avancée\\
UMR 7501, Université de Strasbourg et CNRS\\
7 rue René Descartes\\
67000 Strasbourg, France
}
\email{chapoton@unistra.fr}
%%%%% Sujet
\subjclass{05E, 05A15, 05A19, 06A07, 52B}
\keywords{Dyck path, semilattice, enumerative combinatorics, interval, Hochschild polytope}
%%%%% Gestion
\DOI{10.5802/alco.98}
\datereceived{2018-10-11}
\daterevised{2019-09-20}
\dateaccepted{2019-09-20}
%%%%% Titre et résumé
\title[Some properties of a new partial order on Dyck paths]{Some properties of a new partial order on~Dyck paths}
\begin{abstract}
A new partial order is defined on the set of Dyck paths of a given
length. This partial order is proved to be a meet-semilattice. Its
intervals are enumerated and a specific interval is connected with
an existing polytope coming from algebraic topology.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\section*{Introduction}
This article defines a new partial order on extremely classical
combinatorial objects, namely Dyck paths, and describes some of its
basic or subtle properties.
Let us start by explaining in some detail how this partial order was
discovered. The starting point was the study of the intervals (pairs
of comparable elements) in the Tamari lattices. This was initiated in
\cite{chap_slc}, where these intervals were enumerated. One
interesting point made there was the fact that the number of Tamari
intervals of size $n$ is exactly the number of triangulations of size
$n$, found by Tutte in one of his foundational articles on planar maps
\cite{tutte}. It was only understood much later that the set of Tamari
intervals admits a natural and interesting partial order. Indeed, the
set of intervals in any poset can be ordered by the relation
$[a,b] \leq [c,d]$ if and only if $a \leq c$ and $b \leq d$. When
drawing carefully the Hasse diagrams for these posets of Tamari
intervals, one obtains pictures which apparently has been considered
previously from another point of view. This other context is the study
of homotopy associativity and more precisely the cellular diagonals for
the associahedra that are required to define the tensor product of
$A_{\infty}$ algebras, see~\cite{loday} and the recent article
\cite{MTTV}.
By admitting that this is really the same picture, one can consider
that Tamari intervals can be gathered into higher-dimensional cells,
and that every such cell has unique top and bottom elements (with
respect to the partial order on Tamari intervals). There is a
distinguished cell at the top of the poset, made of all intervals
whose maximum is the unique maximum of the Tamari lattice. Elements in
this top cell are indexed by binary trees. It appears that every
Tamari interval in this top cell is the top element of some unique
cell. Taking the bottom elements of these cells gives another subset
indexed by binary trees. The partial order that we study in the
present article comes from the order induced on this subset of the
poset of all Tamari intervals. Note that this description is just the
original motivation, but instead we will start here from a purely
combinatorial definition and will not prove that it coincides with
this former description.
Admittedly, this origin only provides a weak motivation for the study
of these partial orders. Only time will tell if they are important
objects or not. The aim of the present article is simply to display
clearly that at least they have some nice and intriguing properties.
\smallskip
Let us now present the contents of the article. The first section
contains the definition of the posets $\Dyck_n$ for $n \geq 0$,
starting from a directed graph that turns out to be their Hasse
diagram. Some basic properties are given, including their number of
maximal elements and their relationship to the Tamari lattices.
Then come four sections that prepare the ground for the first main
result, by a careful combinatorial description of the intervals in
$\Dyck_n$.
Sections~\ref{sec2} and~\ref{sec3} present a structure of graded monoid on the disjoint
union of all elements of $\Dyck_n$ for $n \geq 1$, and some
compatibility of the monoid product with the partial orders. This is
then built upon in \Cref{sec4} to define a graded monoid structure
on the disjoint union of all sets of intervals in $\Dyck_n$ for
$n \geq 1$. All these monoids are shown to be free.
In the next \Cref{more_combi}, two other combinatorial constructions
are obtained. \Cref{princi} contains a result to the effect that
some principal upper ideals are products of smaller principal upper
ideals. \Cref{magie} is the last piece of the combinatorial puzzle,
namely the study of a specific subset of core intervals in
$\Dyck_{n+2}$ and the construction of a bijection with intervals in
$\Dyck_{n}$ together with a catalytic data.
All this lengthy combinatorial preparation is then used in
\Cref{section-counting} to prove the first main result: the number of
intervals in $\Dyck_n$ is also given by another formula of Tutte,
namely his formula for the number of rooted bicubic planar
maps. This is achieved by deducing a functional equation from the
combinatorial description, and then solving this catalytic
equation. This enumerative result is yet another instance of the
growing connection between Tamari and related posets and various kinds
of maps, see for example~\cite{fang3,fang2,fangpr}.
\Cref{section-semilattice} proves the second main result: all the posets $\Dyck_n$ are meet-semilattices,
which means that any two elements have a greatest lower bound. This
requires a somewhat technical study of properties in $\Dyck_n$ of
Dyck paths that share a common prefix of some length. The proof also gives
an algorithm for computing the meet.
\Cref{section-hochschild} tells a surprising story, namely an unexpected connection
with another familly of objects called the Hochschild polytopes, maybe
not so well-known, that appeared in the works of Saneblidze in
algebraic topology~\cite{san_arxiv, san_note}. One proves that there
is a bijection between elements in a specific interval $F_n$ of
$\Dyck_{n+2}$ and the vertices of the cell complexes of Saneblidze
that make a cubical version of the Hochschild polytopes. This
bijection is probably also an isomorphism of posets, which would prove
that the order of Saneblidze is a lattice. This question is left open
here, for lack of a strong enough motivation.
\Cref{section-derived} briefly evokes another interesting
representation-theoretic aspect of the posets $\Dyck_n$, namely the
probable existence of many derived equivalences between some of their
intervals. This certainly deserves further investigation.
The final \Cref{misc} contains one result and various remarks. The
result is an unexpected symmetry for some kind of $h$-polynomial that
enumerates vertices according to a coloring of the cover relations in $\Dyck_n$.
\Cref{tamari} recalls some classical properties of Tamari lattices.
\section{Construction and first properties}
In this section, after recalling some notations, the partial order
$\Dyck_n$ is defined through its Hasse diagram. Some properties of
this partial order are proved.
\label{sec1}
A \defin{Dyck path} of size $n \geq 0$ is a lattice path from $(0,0)$ to
$(2 n,0)$ using only north-east and south-east steps and staying weakly above
the horizontal line.
We will also consider Dyck paths of size $n$ as words of length $2 n$
in the alphabet $\{0,1\}$, where $1$ stands for a north-east step and
$0$ for a south-east step.
\begin{figure}[htb]\centering
\begin{tikzpicture}[scale=0.2]
\draw[gray,very thin] (0, 0) grid (48, 8);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 4) -- (5, 3) -- (6, 4) -- (7, 5) -- (8, 4) -- (9, 3) -- (10, 4) -- (11, 5) -- (12, 4) -- (13, 3) -- (14, 2) -- (15, 1) -- (16, 2) -- (17, 1) -- (18, 0) -- (19, 1) -- (20, 2) -- (21, 1) -- (22, 2) -- (23, 3) -- (24, 2) -- (25, 3) -- (26, 4) -- (27, 3) -- (28, 4) -- (29, 5) -- (30, 6) -- (31, 5) -- (32, 6) -- (33, 5) -- (34, 6) -- (35, 7) -- (36, 8) -- (37, 7) -- (38, 6) -- (39, 5) -- (40, 4) -- (41, 5) -- (42, 4) -- (43, 3) -- (44, 2) -- (45, 1) -- (46, 0) -- (47, 1) -- (48, 0);
\end{tikzpicture}
\caption{A typical example}
\label{typique}
\end{figure}
\Cref{typique} displays a typical example.
The \defin{area} under a Dyck path is the surface of the domain between
the horizontal line and the Dyck path.
Every Dyck path can be uniquely written as the concatenation of
several blocks, where in every block the only vertices on the
horizontal line are the first and last ones. If there is only one
block, the Dyck path is said to be \defin{block-indecomposable}. The
example displayed above has $3$ blocks.
Inside a Dyck path, a subsequence of consecutive steps is called a
\defin{subpath} if it starts and ends at the same height and keeps
strictly above that height in between. Here the height is the
vertical coordinate, increased by north-east steps and decreased by
south-east steps.
Let us say that a subpath $x$ of a Dyck path $w$ is \defin{movable} if
it is preceded in $w$ by the letter $0$ and
\begin{itemize}
\item either $x$ ends at the last letter of $w$,
\item or $x$ is followed in $w$ by the letter $1$.
\end{itemize}
\begin{figure}[htb]\centering
\begin{minipage}[b]{0.5\textwidth}\centering
\begin{tikzpicture}[scale=0.35]
\draw[gray,very thin] (0, 0) grid (10, 2);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 0);
\draw[rounded corners=1, pattern=north west lines, pattern color=teal] (5, 1) -- (6, 2)-- (7, 1) ;
\end{tikzpicture}
\caption{A subpath which is not movable.}\end{minipage}\hfill
\begin{minipage}[b]{0.45\textwidth}\centering
\begin{tikzpicture}[scale=0.35]
\draw[gray,very thin] (0, 0) grid (10, 2);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 0);
\draw[rounded corners=1, pattern=north west lines, pattern color=teal] (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);
\end{tikzpicture}\caption{A movable subpath.}\end{minipage}\hfill
\vspace*{5mm}
\begin{minipage}[b]{0.45\textwidth}\centering
\begin{tikzpicture}[scale=0.35]
\draw[gray,very thin] (0, 0) grid (10, 2);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 0);
\draw[rounded corners=1, pattern=north west lines, pattern color=teal] (8, 0) -- (9, 1) -- (10, 0);
\end{tikzpicture}\caption{A movable subpath.}\end{minipage}
\end{figure}
For every Dyck path $w$ and every movable subpath $x$ in $w$, let
$N(w,x)$ be the number of consecutive $0$ letters that appear just
before $x$. For any integer $1 \leq i \leq N(w,x)$ (corresponding to a
choice among the consecutive $0$ letters just before $x$), let us
define another Dyck path $M(w,x,i)$ as the following word:
\begin{itemize}
\item first the initial part of $w$ until the letter before the chosen $0$,
\item then $x$,
\item then the $0$ letters starting at the chosen $0$,
\item then the final part of $w$ after $x$.
\end{itemize}
Graphically, this transformation corresponds to sliding the
subpath $x$ in the north-west direction by one or several steps.
%\smallskip
\begin{figure}[htb]\centering
\begin{tikzpicture}[scale=0.4]
\draw[gray,very thin] (0, 0) grid (12, 3);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 2) -- (11, 1) -- (12, 0);
\draw[rounded corners=1, pattern=north west lines, pattern color=teal]
(8, 0) -- (9, 1) -- (10, 2) -- (11, 1) -- (12, 0);
\end{tikzpicture}\hfill\put(35,15){$\longrightarrow$}\hfill%
\begin{tikzpicture}[scale=0.4]
\draw[gray,very thin] (0, 0) grid (12, 4);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 3) -- (6, 2) -- (7, 3) -- (8, 4) -- (9, 3) -- (10, 2) -- (11, 1) -- (12, 0);
\draw[rounded corners=1, pattern=north west lines, pattern color=teal]
(6, 2) -- (7, 3) -- (8, 4)-- (9, 3) -- (10, 2);
\end{tikzpicture}
\caption{A cover relation $w \to w'$}
\end{figure}
Let $\Dyck_n$ be the set of Dyck paths of size $n$. Let us
introduce a directed graph $\Gamma_n$ with vertex set $\Dyck_n$. It
has edges from every Dyck path $w$ to all Dyck paths $M(w,x,i)$ where
$x$ is a movable subpath of $w$ and $i$ an integer between $1$ and
$N(w,x)$.
Let $\wmin$ be the unique Dyck path made of
alternating $1$ and $0$.
\begin{prop}
The directed graph $\Gamma_n$ is connected and acyclic with $\wmin$ as
unique source element.
\end{prop}
\begin{proof}
First, every edge in $\Gamma_n$ increases strictly the area under
the Dyck path, so there cannot be any oriented cycles.
Let $w$ be any Dyck path not equal to $\wmin$. Then $w$ has at
least one block $x$ of maximal height at least $2$. This block ends by a
sequence of at least two $0$ preceded by a $1$. Let $w'$ be the Dyck
path obtained by exchanging this $1$ and that sequence of $0$ except
the last one. Then there is an edge in $\Gamma_n$ from $w'$ to $w$.
Therefore, $\wmin$ is the unique source element in
$\Gamma_n$. Together with the absence of oriented cycles, this
implies that for every Dyck path $w$, there exists a path in
$\Gamma_n$ from $\wmin$ to $w$.
\end{proof}
\begin{prop}
The directed graph $\Gamma_n$ is the Hasse diagram of a partial order.
\end{prop}
\begin{proof}
This means that $\Gamma_n$ is acyclic and transitively reduced. It
remains only to prove the second property.
So let us consider an edge $w \to M(w,x,i)$ and assume that one can
find a sequence~(S) of edges $w \to M(w,x',i') \to \dots \to M(w,x,i)$.
Every edge in $\Gamma_n$ can be considered as a sequence of several
moves where a subpath is slid by just one step in the north-west
direction. As recalled in \Cref{tamari}, these sliding moves are
exactly the cover relations in the Tamari partial order on the same
set of Dyck paths.
Therefore, one can refine the sequence (S) of edges in $\Gamma_n$
into a sequence of cover relations in the Tamari lattice. By
\Cref{tamari_chain}, the interval in the Tamari lattice between $w$
and $M(w,x,i)$ is just a chain obtained by repeated sliding of the subpath~$x$.
This implies that all the intermediate vertices of the
sequence (S) are obtained by sliding the same subpath $x$.
But in the graph $\Gamma_n$, there cannot be any two consecutive
edges where exactly the same subpath is slid. Indeed, after being
slid once, the subpath is followed by a letter~$0$, hence no
longer movable. It follows that the sequence (S) is reduced to the
single edge $w \to M(w,x,i)$.
\end{proof}
Let us denote by $\sm$ the partial order relation on $\Dyck_n$ thus defined. The edges of $\Gamma_n$ are now understood as the cover relations in the poset $(\Dyck_n, \sm)$.
\medskip
We propose to call this partial order the \defin{dexter order} on Dyck
paths. This choice of terminology is motivated by the fact that the
cover relations are shortcuts (dexterity) and that a symmetry is
broken when compared to the Tamari lattice (dexter in the context of
chirality).
\begin{figure}[htb]
\centering
\begin{tikzpicture}[>=latex,line join=bevel,scale=0.3]
%%
\node (node_2) at (876.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_3) at (1129.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_9) at (370.0bp,367.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_8) at (117.0bp,367.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_7) at (117.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_6) at (370.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_5) at (370.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_4) at (623.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_13) at (623.0bp,367.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 4); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 4) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_12) at (1048.0bp,367.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_1) at (623.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_10) at (876.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_11) at (469.0bp,511.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_0) at (623.0bp,19.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 1); \draw[rounded corners=1, color=black, line width=1.5] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\draw [red,->] (node_1) ..controls (623.0bp,147.89bp) and (623.0bp,156.89bp) .. (node_4);
\draw [blue,->,dashed] (node_5) ..controls (267.78bp,154.06bp) and (229.62bp,171.25bp) .. (node_7);
\draw [blue,->,dashed] (node_2) ..controls (978.22bp,154.06bp) and (1016.4bp,171.25bp) .. (node_3);
\draw [red,->] (node_0) ..controls (703.03bp,47.204bp) and (739.52bp,59.607bp) .. (node_2);
\draw [red,->] (node_3) ..controls (1101.7bp,271.81bp) and (1090.1bp,292.17bp) .. (node_12);
\draw [red,->] (node_4) ..controls (623.0bp,278.31bp) and (623.0bp,287.03bp) .. (node_13);
\draw [red,->] (node_2) ..controls (876.0bp,147.89bp) and (876.0bp,156.89bp) .. (node_10);
\draw [blue,->,dashed] (node_10) ..controls (839.16bp,316.73bp) and (802.66bp,387.26bp) .. (749.0bp,428.0bp) .. controls (704.94bp,461.45bp) and (647.52bp,481.29bp) .. (node_11);
\draw [red,->] (node_8) ..controls (200.14bp,409.12bp) and (222.33bp,419.35bp) .. (243.0bp,428.0bp) .. controls (274.8bp,441.31bp) and (309.61bp,454.56bp) .. (node_11);
\draw [red,->] (node_0) ..controls (542.97bp,47.204bp) and (506.48bp,59.607bp) .. (node_5);
\draw [red,->] (node_5) ..controls (490.21bp,138.84bp) and (493.12bp,139.43bp) .. (496.0bp,140.0bp) .. controls (604.27bp,161.39bp) and (636.96bp,149.25bp) .. (node_10);
\draw [blue,->,dashed] (node_10) ..controls (948.6bp,283.94bp) and (967.11bp,299.22bp) .. (node_12);
\draw [red,->] (node_6) ..controls (449.99bp,268.9bp) and (478.72bp,285.02bp) .. (node_13);
\draw [blue,->,dashed] (node_7) ..controls (117.0bp,275.69bp) and (117.0bp,302.1bp) .. (node_8);
\draw [red,->] (node_10) ..controls (776.3bp,279.96bp) and (757.43bp,290.55bp) .. (node_13);
\draw [red,->] (node_7) ..controls (204.15bp,272.91bp) and (243.42bp,294.95bp) .. (node_9);
\draw [red,->] (node_1) ..controls (520.78bp,154.06bp) and (482.62bp,171.25bp) .. (node_6);
\draw [blue,->,dashed] (node_6) ..controls (370.0bp,271.44bp) and (370.0bp,291.25bp) .. (node_9);
\draw [red,->] (node_0) ..controls (623.0bp,45.551bp) and (623.0bp,54.96bp) .. (node_1);
\draw [red,->] (node_5) ..controls (370.0bp,152.23bp) and (370.0bp,166.73bp) .. (node_6);
\draw [red,->] (node_2) ..controls (783.82bp,149.54bp) and (758.9bp,160.76bp) .. (node_4);
%
\end{tikzpicture}
\caption{Hasse diagram of the poset $(\Dyck_4, \leq)$. Edge colors will be explained and used in \Cref{hpoly}.}
\label{fig_dyck4}
\end{figure}
\subsection{First properties}
\begin{prop}
\looseness1
The maximal elements of $(\Dyck_n, \sm)$ are exactly the
block-indecom\-posable Dyck paths that do not contain any subpath that is
both preceded by $0$ and followed by~$1$.
\end{prop}
\begin{proof}
The property of $w$ being maximal is equivalent to the non-existence
of movable subpaths in $w$.
According to their definition, movable subpaths can exist in two
distinct ways. The first way is when the movable subpath is the last
block of $w$. This happens if and only if $w$ contains at least two
blocks. The second way is the existence of a subpath preceded by
$0$ and followed by $1$.
Therefore being maximal is equivalent to being block-indecomposable and
not having this second kind of subpaths.
\end{proof}
\begin{prop}
The sets of maximal elements are counted by the Motzkin numbers (\oeis{A1006}).
\end{prop}
\begin{proof}
Removing the initial $1$ and the final $0$ defines a bijection from
the set of maximal elements to the set $\mathscr{M}$ of Dyck paths
that do not contain any subpath that is both preceded by $0$ and
followed by $1$. Then the decomposition into blocks of such a path
has at most two blocks and these blocks satisfy the same
condition. One therefore gets
\begin{equation}
M = 1 + t M + t^2 M^2 = 1 + t + 2 t^2 + 4 t^3 + 9 t^4 + \cdots
\end{equation}
for the generating series $M$ of the set $\mathscr{M}$. This is the usual
equation for the generating series of Motzkin numbers.
\end{proof}
\begin{rema}
Despite their simple definition, intervals in the dexter order can
be quite irregular. To illustrate, let us now give examples of
intervals in $\Dyck_n$ where some important properties of the Tamari
lattices do not hold. The interval between $\wmin$ and the Dyck path
$(1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0)$ is not semi-distributive, and
therefore not congruence-uniform; it is also not extremal. For
these notions, see general references on lattice theory such as
~\cite{freese, gratzer}. The interval between $\wmin$ and the Dyck
path
\begin{equation*}
(1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0)
\end{equation*}
has a Coxeter polynomial with some roots not on the unit circle (see
~\cite{chap_cats, lenzing} for the
definition of the Coxeter polynomial and the meaning of this
invariant and its roots in a representation-theoretic context).
\end{rema}
\begin{rema}
There are two simple natural inclusions of posets of $\Dyck_n$ in
$\Dyck_{n+1}$, by concatenation of the Dyck path $(1,0)$ at the
start or at the end.
\end{rema}
\subsection{Relations to other posets}
In this subsection, we prove that the partial order $(\Dyck_n, \leq)$
stands somewhere between the Tamari partial order~\cite{tamari_friedman, tamari_festschrift} and the less
well-known comb partial order introduced by Pallo in~\cite{pallo}.
The Tamari lattice structure on Dyck paths is recalled in \Cref{tamari}.
\begin{prop}
Let $w$ and $w'$ be two Dyck paths in $\Dyck_n$ such that $w \sm w'$.
Then $w$ is smaller than $w'$ in the Tamari order.
\end{prop}
\begin{proof}
By transitivity, it is enough to prove this under the additional
assumption that there is an edge $w \to w'$ in $\Gamma_n$. It is
clear that such an edge can be performed using a sequence of several
cover relations in the Tamari lattice, which are just made by
sliding a subpath by one step in the north-west direction.
\end{proof}
The comb partial order (or left-arm rotation order) was initially
defined in~\cite{pallo} as a partial order on the set of binary
trees. Its cover relations are a subset of the cover relations of the
Tamari lattice, namely left-to-right rotations $(ab)c \to a(bc)$ of
binary trees where the two rotated vertices are on the leftmost branch
of the first binary tree. Using the same bijection $\sigma$ as~\cite{berbon}
and the proof of their Proposition 2.1, one can see that these restricted
rotations correspond precisely to Tamari cover relations in $\Dyck_n$
where the slid subpath is at height $0$.
To summarize, the cover relations in the comb partial order on $\Dyck_n$
are the Tamari cover relations where the slid subpath is at height $0$.
\begin{prop}
Let $w$ and $w'$ be two Dyck paths in $\Dyck_n$ such that $w$ is
smaller than $w'$ in the comb partial order. Then $w \leq w'$.
\end{prop}
\begin{proof}
This holds because every cover relation in the comb poset is also a
cover relation in $(\Dyck_n, \leq)$, as a subpath at height $0$ cannot be followed
by the letter $0$.
\end{proof}
\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=0.35,>=latex,line join=bevel,]
%%
\node (node_4) at (286.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 3); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_3) at (89.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_2) at (89.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_1) at (286.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_0) at (187.0bp,19.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 1); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\draw [black,->] (node_1) ..controls (286.0bp,147.89bp) and (286.0bp,156.89bp) .. (node_4);
\draw [black,->] (node_2) ..controls (89.0bp,152.23bp) and (89.0bp,166.73bp) .. (node_3);
\draw [black,->] (node_0) ..controls (156.85bp,46.456bp) and (144.63bp,57.185bp) .. (node_2);
\draw [black,->] (node_0) ..controls (217.46bp,46.456bp) and (229.81bp,57.185bp) .. (node_1);
%
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35,>=latex,line join=bevel,]
%%
\node (node_4) at (286.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 3); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_3) at (89.0bp,223.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_2) at (89.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_1) at (286.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_0) at (187.0bp,19.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 1); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\draw [red,->] (node_1) ..controls (286.0bp,147.89bp) and (286.0bp,156.89bp) .. (node_4);
\draw [blue,->,dashed] (node_2) ..controls (89.0bp,152.23bp) and (89.0bp,166.73bp) .. (node_3);
\draw [red,->] (node_0) ..controls (156.85bp,46.456bp) and (144.63bp,57.185bp) .. (node_2);
\draw [red,->] (node_0) ..controls (217.46bp,46.456bp) and (229.81bp,57.185bp) .. (node_1);
\draw [red,->] (node_2) ..controls (160.25bp,149.23bp) and (178.98bp,160.07bp) .. (node_4);
%
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35,>=latex,line join=bevel,]
%%
\node (node_4) at (187.0bp,325.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 3); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_3) at (89.0bp,209.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_2) at (109.0bp,107.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_1) at (286.0bp,209.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_0) at (168.0bp,19.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 1); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 0) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\draw [black,->] (node_1) ..controls (250.75bp,250.59bp) and (242.19bp,260.44bp) .. (node_4);
\draw [black,->] (node_2) ..controls (100.98bp,148.12bp) and (99.116bp,157.42bp) .. (node_3);
\draw [black,->] (node_0) ..controls (150.19bp,45.962bp) and (143.33bp,55.966bp) .. (node_2);
\draw [black,->] (node_0) ..controls (189.15bp,48.111bp) and (198.9bp,61.611bp) .. (207.0bp,74.0bp) .. controls (227.12bp,104.77bp) and (248.17bp,140.7bp) .. (node_1);
\draw [black,->] (node_3) ..controls (123.9bp,250.59bp) and (132.36bp,260.44bp) .. (node_4);
%
\end{tikzpicture}
\caption{Comparison of three partial orders: comb, dexter and Tamari}
\end{figure}
\section{A monoid on pseudo-Dyck paths}
This section and the next three ones contain a precise combinatorial
study (\emph{dévissage}) of the posets $\Dyck_n$ and their
intervals, the final aim being the enumeration of the intervals in
\Cref{section-counting}.
The current section mainly describes a monoid structure on pseudo-Dyck paths,
that will be transferred to Dyck paths in the next section.
\label{sec2}
Let us first introduce another kind of decomposition for
block-indecomposable Dyck paths.
\begin{prop}
\label{level_decomposition}
Let $k\geq 0$ be an integer. Every block-indecomposable Dyck path ending
with exactly $k + 1$ letters $0$ can be uniquely written as
\begin{equation}
\label{pieces}
(1, w_1, 1, w_2, 1, w_3, \dots, 1, w_{k}, 1, 0^{k+1})
\end{equation}
for some (possibly empty) Dyck paths $w_1, w_2, \dots, w_{k}$. This defines a
bijection between block-indecomposable Dyck paths ending with exactly
$k + 1$ letters $0$ and sequences of $k$ Dyck paths.
\end{prop}
\begin{proof}
Clearly, every Dyck path of the given shape~\eqref{pieces} is
block-indecomposable and ends with exactly $k+1$ letters $0$.
Conversely, let us start with a block-indecomposable Dyck path $w$ ending
with exactly $k + 1$ letters $0$. The aim is to recover all the
$w_i$. Consider the word $v_k$ obtained from $w$ by removing the
final $(1, 0^{k+1})$ part. The final height of $v_k$ is $k$. Let
$w_{k}$ be the largest suffix of $v_k$ in which the height is greater
than or equal to $k$. The letter before $w_{k}$ in $w$ must be
$1$. Then one can define $v_{k-1}$ by removing $(1,w_k)$ at the end of
$v_k$. Iterating this process of removing the largest suffix of
height staying above the final height, one defines $w_1,\dots,w_k$
that are all Dyck paths. This yields the desired decomposition,
which is clearly unique.
\end{proof}
Let us call this decomposition the \defin{level-decomposition} of
$w$. We will write
\begin{equation*}
w = \level(w_1, w_2, \dots, w_{k})
\end{equation*}
to denote this situation.
In fact, both the decomposition into blocks and the
level-decomposition are special cases of products inside a monoid
structure. Let us describe this monoid.
%\smallskip
It turns out to be more convenient to work (for a moment) with Dyck
paths minus their initial and final letters. Let us therefore define a
\defin{pseudo-Dyck path} to be a path obtained in this way from a
non-empty Dyck path. For a Dyck path $w$, let $\ov{w}$ denote the
pseudo-Dyck path obtained by removing the initial and final letters of
$w$.
Note that the height in a pseudo-Dyck path can reach the value $-1$,
taking $0$ as initial height.
%\smallskip
Let us introduce a product $\pscolle$ on the set of pseudo-Dyck
paths. Let $u$ and $v$ be two such paths. Write $u = (u', 0^k)$ where
$u'$ is either empty (if $u$ itself is empty) or ends with the letter
$1$. Note that $0^k$ is the largest suffix of $u$ made only of
$0$. Write $v = v' v''$ where $v'$ is the largest prefix where the
height is positive or zero. The product is
\begin{equation}
u \pscolle v = (u', v', 0^k, v'').
\end{equation}
This is again a pseudo-Dyck path, as it lies above the concatenation
$u v$, which is itself clearly a pseudo-Dyck path.
For example, one gets
\begin{equation*}
(1,0) \pscolle (0,1) = (1, 0, 0, 1)
\end{equation*}
and
\begin{equation*}
(\underbrace{0,1,1}_{u'},0) \pscolle (\underbrace{1,0,1,0}_{v'}) = (0, 1, 1, 1, 0, 1, 0, 0).
\end{equation*}
Note that the empty pseudo-Dyck path is easily seen to be a two-sided
unit for $\pscolle$.
\begin{lemma}
The product $\pscolle$ is an associative product on the set of
pseudo-Dyck paths.
\end{lemma}
\begin{proof}
Consider three pseudo-Dyck paths $u$, $v$, $w$. One can assume that
none of them is empty, since the associativity is otherwise clear.
Write $u = (u', 0^k)$, $w= w' w''$ and decompose also $v$
in both ways. One has to distinguish two cases, depending on whether
$(1,v,0)$ is block-indecomposable or not. If it is, then
$v = (v', 0^\ell)$ where $v'$ ends by the letter $1$. The largest
prefix of positive height is $v$ itself. In this case, the two ways
to compute the product of $u,v,w$ give
$(u', v', w', 0^{\ell+k}, w'')$.
If $(1,v,0)$ is not block-indecomposable, then $v = (v', v'', 0^\ell)$,
where $v''$ ends with $1$ and $v'$ is the largest prefix of positive height.
In this case, the two ways to compute the product of $u,v,w$
give $(u', v', 0^k, v'', w', 0^{\ell}, w'')$.
\end{proof}
This defines a monoid $\mono$ on the set of pseudo-Dyck paths. This
monoid is graded by size, which is the number of letters $1$. As said
before, the empty pseudo-Dyck path is the unit of this monoid.
\begin{lemma}
\label{concat_colle}
Let $u$ and $v$ be two Dyck paths. Then the product
$\ov{u} \pscolle (0,1) \pscolle \ov{v}$ is the pseudo-Dyck path
$\ov{u v}$ associated to the concatenation of $u$ and $v$.
\end{lemma}
\begin{proof}
Using the definition of $\pscolle$, one can check that the pseudo-Dyck path
$\ov{u} \pscolle (0,1) \pscolle \ov{v}$ is just the concatenation
$(\ov{u},0,1,\ov{v})$. Hence the associated Dyck path is $(1,\ov{u},0,1,\ov{v},0)$, which is $u v$.
\end{proof}
\begin{lemma}
\label{level_colle}
Let $w$ be a block-indecomposable Dyck path with level-decomposition
$w=\level(w_1,\dots,w_k)$. Then the pseudo-Dyck path $\ov{w}$ is
\begin{equation}
\ov{w} = (w_1,1,0) \pscolle \dots \pscolle (w_k,1,0).
\end{equation}
\end{lemma}
\begin{proof}
By induction on $k$. This is true if $k=0$ for the empty
level-decomposition of $(1,0)$ and the empty product. If $k=1$, the
product has only one factor and the statement is also
true. Otherwise, let $w'$ be the block-indecomposable Dyck path with
level-decomposition $w'=\level(w_1,\dots,w_{k-1})$. Then one knows
that $\ov{w'} = (w_1,1,0) \pscolle \dots \pscolle
(w_{k-1},1,0)$. Computing the $\pscolle$ product of this with
$(w_k,1,0)$, one gets exactly $\ov{w}$ on the left hand side and the
expected product on the right hand side.
\end{proof}
This lemma also implies that the product $\ov{u} \pscolle \ov{v}$ for
two block-indecomposable Dyck paths $u$ and $v$ is $\ov{w}$, where $w$
is the block-indecomposable Dyck path whose level-decomposition is the
concatenation of the level-decompositions of $u$ and $v$.
\begin{lemma}
\label{gen_M1}
The monoid $\mono$ is generated by the elements $(w,1,0)$ where $w$
runs over the set of Dyck paths, plus the element $(0,1)$.
\end{lemma}
\begin{proof}
By the previous two lemmas, one can first write any pseudo-Dyck path as
a $\pscolle$ product of some $\ov{w}$ for block-indecomposable Dyck
paths $w$, with intermediate factors $(0,1)$. Then using the
level-decomposition of each $w$, one can write $\ov{w}$ as a
$\pscolle$ product of pseudo-Dyck paths of the shape $(w_i,1,0)$.
\end{proof}
\begin{prop}
\label{free_M1}
The monoid $\mono$ is free on the
generators $(w,1,0)$ where $w$ runs over the set of Dyck paths, plus
the element $(0,1)$.
\end{prop}
\begin{proof}
Because the monoid is generated by these elements, it is enough to
compare its generating series with the generating series of the free
monoid on the same generators. This is a simple computation with the
usual generating series of Catalan numbers.
\end{proof}
\section{The same monoid seen on Dyck paths}
\label{sec3}
In this section, the previous monoid on pseudo-Dyck paths is
transferred to Dyck paths. Some compatibility between the product
and the dexter partial orders are proved, that will be used in the next
section to obtain a monoid on the set of intervals in dexter posets.
Let us now go back to Dyck paths. Using the simple bijection
$w \to \ov{w}$ between non-empty Dyck paths and pseudo-Dyck paths, the
monoid structure $\mono$ can be transported to a monoid structure $\monod$ on
the set of non-empty Dyck paths, where the product will be denoted $\colle$.
This means that
\begin{equation}
u \colle v = (1, \ov{u} \pscolle \ov{v}, 0).
\end{equation}
The unit of $\monod$ becomes $(1,0)$, and the free generators of $\monod$
are the element $(1,0,1,0)$ and all elements of the shape
$(1,w,1,0,0)$ for some Dyck path $w$.
The monoid structure $\monod$ interacts nicely with the partial order
on $\Dyck_n$.
\begin{lemma}
\label{cover_colle}
Let $w \in \Dyck_n$ be a Dyck path. Assume that
$w = w_1 \colle \dots \colle w_m$ as a product of generators of the
monoid $\monod$. Let $w \to w'$ be a cover relation in the partial order
on $\Dyck_n$. Then the decomposition of $w'$ as a product of
generators has at most $m$ factors. If this decomposition has
exactly $m$ factors, then there is one cover relation inside one of the
factors, and the other factors are unchanged. Otherwise, several
consecutive factors are replaced by a single new factor, all other
factors being unchanged.
\end{lemma}
\begin{proof}
(A) Assume first that the cover relation is sliding one block of
$w$, and therefore that two consecutive blocks $v$ and $v'$ of $w$
are replaced by a new single block in $w'$. One has to understand the
level-decomposition of this new block in terms of those of
$v=\level(v_1,\dots,v_k)$ and $v'$. This depends on the height
$1 \leq i \leq k+1$ of the starting point of the block $v'$ after it
has been slid.
\begin{center}
Initial situation: \includegraphics[width=4cm]{figures/section3_picture1.pdf}
\end{center}
Assume first that $1 \leq i \leq k$. Then the new level decomposition
will be made of $v_1,\dots,v_{i-1}$, then a new term coming from
$v_{i},\dots,v_k$, then the level decomposition of
$v'$. There are strictly less factors in $w'$ than in
$w$, because the factor $(1,0,1,0)$ separating the two blocks disappears.
\begin{center}
After sliding when $1 \le i\le k$\,: \includegraphics[width=4cm]{figures/section3_picture2.pdf}
\end{center}
There remains the case when $i = k + 1$. Then the new level
decomposition is $v_1,\dots,v_k$, followed by the empty Dyck path, then by the
level decomposition of $v'$. Therefore the number of factors stays the
same with just one change, the factor $(1,0,1,0)$ being replaced by the
factor $(1,1,0,0)$. This corresponds to a cover relation inside this factor.
\begin{center}
After sliding when $i = k + 1$\,: \includegraphics[width=4cm]{figures/section3_picture3.pdf}
\end{center}
(B) Assume now that the cover relation is happening inside one block
$v$ of $w$. Let $v = \level(v_1,\dots,v_k)$ be the
level-decomposition of $v$. Then the cover relation can only happen
inside some $v_i$ as a cover relation $v_i \to v'_i$. Therefore in
the monoid $\monod$, one gets $w'$ from $w$ by replacing the factor
$(1,v_i,1,0,0)$ by $(1,v'_i,1,0,0)$.
\end{proof}
Informally, this means that performing a cover relation in a $\colle$ product can
either preserve the product or merge terms of the product, but can never split
them.
Let us now give two lemmas that will be used in the next section to
define a product~$\colle$ on the set of all intervals.
\begin{lemma}
\label{factor_cover_left}
Let $w \to w'$ be a cover relation of non-empty Dyck paths. Let $u$
be a non-empty Dyck path. Then there is a cover relation from
$u \colle w$ to $u \colle w'$.
\end{lemma}
\begin{proof}
One can assume that $u$ is not $(1,0)$, because it is the unit of $\monod$.
Let $\ov{u} = (u', 0^k)$ be the decomposition of $\ov{u}$ according
to its final sequence of $0$. Let $\ov{w} = w_1 w_2$ and
$\ov{w'} = w'_1 w'_2$ be the decompositions whose first term is the
longest prefix before going below the horizontal axis. Then $\ov{u} \pscolle \ov{w}$ and $\ov{u} \pscolle \ov{w'}$ are
$(u',w_1,0^k,w_2)$ and $(u',w'_1,0^k,w'_2)$. If either $w_1 = w'_1$
or $w_2 = w'_2$, then the statement is clear, as the cover relation is
inside either $w_1$ or $w_2$. Otherwise, the cover relation must merge
the first two blocks of $w$ by sliding the second block. One can
then write $w = (1,w_1,0,x,w_3)$ and $w' = (1, y, 0, w_3)$ where $x$
is the slid subpath, $y$ is the result of sliding $x$ on $w_1$ and
$w_3$ may be empty. Then the products ${u}\colle{w}$ and ${u}\colle{w'}$ are equal to $(1,u',w_1,0^{k+1},x,w_3)$ and
$(1,u',y,0^{k+1},w_3)$. One can slide $x$ to get the wanted cover
relation.
\end{proof}
\begin{lemma}
\label{factor_cover_right}
Let $w \to w'$ be a cover relation of non-empty Dyck paths. Let $u$
be a non-empty Dyck path. Then there is a cover relation from
$w \colle u$ to $w' \colle u$.
\end{lemma}
\begin{proof}
One can assume that $u$ is not $(1,0)$, because it is the unit of
$\monod$. Let $\ov{u} = u' u''$ be the decomposition whose first
term is the longest prefix before going below the horizontal
axis. Let $\ov{w} = (v, 0^{k})$ and $w' = (v', 0^{k'})$ be the
decompositions according to the final sequences of $0$. Then
$\ov{w}\pscolle\ov{u}$ and $\ov{w'}\pscolle\ov{u}$ are
$(v, u', 0^k, u'')$ and $(v', u', 0^{k'}, u'')$. If $k = k'$, then
the statement is clear, as the cover relation is inside
$v$. Otherwise, the cover relation must merge the last two blocks of
$w$ by sliding the last block. One can then write
$w = (w_1, w_2, 0^{i}, w_3, 0^{k+1})$ and
$w' = (w_1, w_2, w_3, 0^{i+k+1})$ for some $i \geq 1$, where $w_1$
may be empty, $(w_2,0^i)$ is the next-to-last block and
$(w_3,0^{k+1})$ is the last block, being slid. Then the right products
${w}\colle{u}$ and ${w'}\colle{u}$ are equal to
$(w_1, w_2, 0^{i}, w_3, u', 0^{k}, u'', 0)$ and
$(w_1, w_2, w_3, u', 0^{i+k}, u'', 0)$. Then the expected cover
relation is given by sliding $(w_3, u', 0^{k+1})$, using also the
starting $0$ of $u''$ or the final $0$ if $u''$ is empty.
\end{proof}
\section{A monoid on intervals}
\label{sec4}
In this section, building upon the monoid on Dyck paths and
its compatibility with the dexter partial order obtained in the
previous section, we will define and study another monoid $\monoi$ on
the set of all intervals in the posets $\Dyck_n$ for $n \geq 1$. This
monoid will be one of the crucial ingredients in the enumeration of
intervals in \Cref{section-counting}.
%\smallskip
Let $[w_1,w'_1]$ in $\Dyck_m$ and $[w_2,w'_2]$ in $\Dyck_n$ be two
intervals.
\begin{lemma}
\label{lemma_ww_ww}
In $\Dyck_{m+n-1}$, one has $w_1 \colle w_2 \leq w'_1 \colle w'_2$.
\end{lemma}
\begin{proof}
Let us pick any sequence of cover relations from $w_1$ to $w'_1$ and any
sequence of cover relations from $w_2$ to $w'_2$. Using
\Cref{factor_cover_left} and the chosen cover relations from $w_2$ to
$w'_2$, one gets a sequence of cover relations from $w_1 \colle w_2$ to
$w_1 \colle w'_2$. Using then \Cref{factor_cover_right} and the
chosen cover relations from $w_1$ to $w'_1$, one gets a sequence of
cover relations from $w_1 \colle w'_2$ to $w'_1 \colle w'_2$.
\end{proof}
Let us therefore define a product $\colle$ on the set of all intervals
(except the unique interval in $\Dyck_0$) by the formula
\begin{equation}
[w_1, w'_1] \colle [w_2, w'_2] = [w_1 \colle w_2, w'_1 \colle w'_2].
\end{equation}
This defines a monoid $\monoi$ on this set of intervals. This monoid
is graded by the size minus $1$. The unit is the unique interval in
$\Dyck_1$.
\begin{prop}
\label{free_M2}
The monoid $\monoi$ is free with generators all
intervals with maximal elements of the shape $(1,w,1,0,0)$ plus
the interval $[(1,0,1,0),(1,0,1,0)]$ in $\Dyck_2$.
\end{prop}
Note that the generators of $\monoi$ are exactly the intervals whose
maximal element is a generator of the monoid $\monod$.
\begin{proof}
Take any interval $[w,w']$. Let $w' = w'_1 \colle \dots \colle w'_k$
be the unique expression of $w'$ as a product of generators in the
monoid $\monod$. By \Cref{cover_colle}, the minimum $w$ can be
expressed as $w_1 \colle \dots \colle w_k$ where $w_i \leq w'_i$ for
every $i$ and the $w_i$ need not be generators in $\monod$. This
implies that the interval $[w,w']$ can be written as the product
\begin{equation*}
[w, w'] = [w_1, w'_1] \colle \dots \colle [w_k, w'_k].
\end{equation*}
Therefore the monoid $\monoi$ is indeed generated by the proposed generators.
Conversely, given a product of some generators, one can recover uniquely the
generator factors by the same procedure of decomposition of the maximum in
$\monod$. Therefore the monoid $\monoi$ is free.
\end{proof}
The monoid $\monoi$ interacts nicely with the partial order.
\begin{theorem}
\label{factoriser}
The interval $I = [w_1, w'_1] \colle [w_2, w'_2]$ is isomorphic as a
poset to the Cartesian product of the intervals $I_1 = [w_1, w'_1]$
and $I_2 = [w_2, w'_2]$. The isomorphism is given by the product
$\colle$ of Dyck paths.
\end{theorem}
\begin{proof}
By \Cref{lemma_ww_ww}, for $x_1 \in I_1$ and $x_2 \in I_2$,
the product $x_1 \colle x_2$ is in $I$.
By \Cref{factor_cover_left} and \Cref{factor_cover_right}, every
cover relation in the Cartesian product $I_1 \times I_2$ is mapped
to a cover relation in $I$. Conversely, let us prove that
\begin{itemize}
\item every element of $I$ is a product
$x_1 \colle x_2$ with $x_1 \in I_1$ and $x_2 \in I_2$,
\item every cover relation in $I$ comes from a cover relation of $I_1$
or $I_2$.
\end{itemize}
Let $x = x_1 \colle x_2 \to y$ be a cover relation between elements of
$I$. If we can prove that $y$ can be written $y_1 \colle y_2$, with
$y_1 \in I_1$ and $y_2 \in I_2$, then by induction from the bottom
of $I$, one will get the two required properties.
By \Cref{cover_colle}, the cover relation $x_1 \colle x_2 \to y$
either happens inside one of the factors of the complete factorisation
of $x_1 \colle x_2$ or merges some consecutive factors in this
complete factorisation. It cannot merge the last factor of $x_1$ and
the first factor of $x_2$, because again by \Cref{cover_colle} these
factors would still be merged in $w'_1 \colle w'_2$, which is
absurd.
The cover relation $x \to y$ must therefore respect the
factorisation of $x$ into $x_1 \colle x_2$. If some factors are
merged, they are either all inside $x_1$ or all inside
$x_2$. Therefore $y$ can be written $y_1 \colle y_2$ in the expected
way, and $x \to y$ comes from a cover relation of the Cartesian
product of posets $I_1 \times I_2$.
\end{proof}
The number of generators of the monoid $\monoi$ is a sequence starting with
\begin{equation}
3,
3,
11,
51,
267,
1507,
8955,
55251,
350827,\dots
\end{equation}
which apparently has not been studied so far.
\subsection{Specific corollaries}
\label{specific}
Let us now state some interesting special cases of \Cref{factoriser},
which can be presented without mention of the monoid $\monoi$.
First, there is a simple factorisation property, for which we give
another direct proof.
Let $[u,v]$ be an interval in $\Dyck_n$. Let $v_1,\dots,v_k$ be the
unique decomposition of $v$ into blocks. Because the cover relations in
$\Dyck_n$ can only increase the heights, the Dyck path $u$ must touch
the horizontal line at every point where $v$ does so. So one can
decompose $u$ by cutting at these points. This defines the Dyck paths
$u_i$ for $i=1,\dots,k$.
\begin{prop}
\label{facto_tous}
Every interval $[u,v]$ in $\Dyck_n$ is isomorphic to the Cartesian
product of the intervals $[u_i,v_i]$ for $i = 1,\dots,k$.
\end{prop}
\begin{proof}
The same property used above to decompose $u$ is true for all
elements of the interval $[u,v]$. Cutting at the touch points of $v$
defines a bijection, with inverse just given by concatenation,
between elements of $[u,v]$ and elements of the product of the
intervals $[u_i,v_i]$. Note that the cover relations between elements
of $[u,v]$ can only happen inside one block. The bijection is
therefore clearly an isomorphism of posets.
\end{proof}
For $w\in \Dyck_n$, let $I(w)$ be the interval $[\wmin, w]$. As a
special case of \Cref{facto_tous}, every interval $I(w)$ is isomorphic
to the product of the intervals $I(w_i)$ over the blocks $w_i$ of $w$.
For $w\in \Dyck_n$, let $J(w)$ be the interval $[\wmin, (1,w,1,0,0)]$
in $\Dyck_{n+2}$.
Keeping the same notations, one has another factorisation result, easily deduced from \Cref{factoriser}.
\begin{theorem}
\label{th_level_iso}
Let $w$ be a block-indecomposable Dyck path. The interval $I(w)$ is
isomorphic to the product of the intervals $J(w_i)$, where the $w_i$
are the Dyck paths in the level-decomposition of $w$.
\end{theorem}
It follows that in this case the isomorphism type of the interval
$I(w)$ only depends on the multiset of Dyck paths in the
level-decomposition of $w$, and not on their order. Combining with
\Cref{facto_tous}, one obtains the following clean statement.
\begin{theorem}
\label{th_iso}
For any $w$, the isomorphism type of the interval $I(w)$ only
depends on the multiset of Dyck paths in the
level-decomposition of all blocks of $w$.
\end{theorem}
Conversely, it seems to be true that different multisets give distinct
isomorphism types, but this remains to be proved.
\section{More combinatorial decompositions}
\label{more_combi}
In this section, we turn to the other required ingredients in the combinatorial
description of intervals in the dexter order, namely a natural
decomposition of the principal upper ideals and a subtle description
of the set of core intervals.
\subsection{Factorisation of principal upper ideals}
\label{princi}
Let us now study the principal upper ideals in $\Dyck_n$. When looking at the
posets $\Dyck_n$ for small $n$, one can see that some of their
principal upper ideals are isomorphic to Cartesian products of principal upper
ideals for some smaller Dyck paths. The main result of this section is
a general description of that phenomenon.
For a Dyck path $w$, let $\up(w)$ be the principal upper ideal
generated by $w$, namely the set of all $u$ such that $w \leq u$.
Let us say that a Dyck path $w$ admits a \defin{strip} if it can be written as
$(u,1,v,1,0,0,0^k)$ where $v$ is any Dyck path. The strip itself is graphically the horizontal region of width~$1$ ranging from the letter $1$ after $u$ to the letter $0$ before $0^k$.
\begin{lemma}
A Dyck path $w$ does not admit a strip if and only if $w$ is empty or
$w$ ends by $(1,0)$.
\end{lemma}
\begin{proof}
If $w$ ends by $(1,0)$ or is empty, it clearly admits no strip.
Suppose that $w$ is not empty and does not end with $(1,0)$, and consider the second~$0$ in the final sequence of $0$. There is exactly one
block-indecomposable Dyck subpath $x$ inside $w$ that ends with this
letter $0$. Because the final sequence of $0$ in $x$ has length~$2$,
$x$ can be written as expected.
\end{proof}
Suppose now that $w$ admits a strip, so that $w = (u,1,v,1,0,0,0^k)$. Let $u' = (u,1,0,0^k)$.
\begin{prop}
\label{princi_factoriser}
The principal upper ideal
$\up(w)$ is isomorphic as a poset to the product of $\up(u')$ and $\up(v)$.
\end{prop}
\begin{proof}
By the hypotheses on $w$, any sliding move from $w$ either happens
inside $v$, or somewhere before $v$ in which case it can be identified
with a sliding move in $u'$. Moreover the resulting $w'$ has the
same properties as $w$ with modified $u$ or $v$, so that the full
principal upper ideal factorizes as expected.
\end{proof}
Conversely, one can realize in this way the product of any two
principal upper ideals $\up(u')$ and $\up(v)$, assuming only that the
first one is not empty.
%\medskip
As the simplest non-trivial example, $\up((1,0,1,1,0,1,0,1,0,0))$ is isomorphic to the product of $\up((1,0,1,0))$ with itself.
%\medskip
Let us define a \defin{reduced interval} as an interval whose minimum
is either empty or of the shape $(w,1,0)$. The \defin{empty interval}
is the interval from the empty Dyck path to itself.
From \Cref{princi_factoriser}, one can deduce a bijection between
non-reduced intervals and pairs (non-empty interval, interval) as
follows. A non-reduced interval is the same as a pair consisting of
$w$ and an element in $\up(w)$ for some non-empty $w$ not of the shape
$(w,1,0)$. Therefore one can use the factorization from
\Cref{princi_factoriser} to map uniquely this element to a pair made
of one element $x$ in $\up(u')$ ($u'$ being non empty) and one element
$y$ in $\up(v)$. This gives the pair (non-empty interval $[u', x]$,
interval $[v, y]$). That this is a bijection is clear by construction,
using the remark after \Cref{princi_factoriser}.
At the level of generating series for intervals according to their size, one gets from this
decomposition that
\begin{equation}
f_A = f_R + t (f_A - 1) f_A,
\end{equation}
where $f_A$ is the generating series for all intervals and $f_R$ the
generating series for reduced intervals. With an additional
variable $s$ accounting for the number of blocks in the minimum of the
intervals, one gets the refined equation
\begin{equation}
\label{eq_fA_fR}
f_A = f_R + t (f_A - 1) f_A|_{s=1}.
\end{equation}
\subsection{Properties of the core intervals}
\label{magie}
Let us study now the \emph{core intervals}, namely intervals whose
minimum has the shape $(v,1,0)$ (shape A) and whose maximum has the
shape $(1,w,1,0,0)$ (shape B), where $v$ and $w$ are Dyck paths. In
this section, one assumes that $n \geq 2$.
Let $E_n$ be the subset of elements of $\Dyck_n$ that have either
shape A or shape B.
\begin{lemma}
The set $E_n$ is a lower ideal in $\Dyck_n$.
\end{lemma}
\begin{proof}
An element of shape B can only cover elements of shape A or B. An
element of shape A can only cover elements of shape A. Indeed, the
number of final $0$ can only be increased by a cover relation.
\end{proof}
It follows that the Hasse diagram of the induced partial order on
$E_n$ is just the restriction of the Hasse diagram of $\Dyck_n$.
For every element $w \in \Dyck_{n-2}$, let us define a chain $E(w)$ of
cover relations in $E_n$. Start from $e_0(w)=(1,0,w,1,0)$. Sliding the
second block of $e_0(w)$ to height $1$ defines $e_1(w)$, which has one
block less then $e_0(w)$. Repeat the same operation and define
successive $e_i(w)$ until reaching a block-indecomposable Dyck path
$e_k(w)$, which has necessarily shape B. The number $k$ is the number
of blocks of $w$ plus $1$.
Suppose that $w$ is a concatenation of blocks $w_1,\dots,w_{k-1}$. One
can describe the chain $E(w)$ completely: the element $e_{i-1}(w)$ for
$1 \leq i \leq k$ is
\begin{equation*}
(1,w_1,w_2,\dots,w_{i-1},0,w_{i},\dots,w_{k-1},1,0)
\end{equation*}
and the last element $e_k(w)$ is just $(1,w,1,0,0)$. One can therefore recover the
first element of this chain from its last element.
\begin{lemma}
The set $E_n$ is the disjoint union of the chains $E(w)$ for
$w \in \Dyck_{n-2}$.
\end{lemma}
\begin{proof}
Consider the following map $\theta$ from $E_n$ to $E_n$. If
$w \in E_n$ has shape $A$, slide its second block to height $1$ to
get $\theta(w)$. Otherwise $w$ can be written as $(1,w',1,0,0)$, so
one can define $\theta(w)$ to be $(1,0,w',1,0)$. By the previous
remarks, the chains $E(w)$ are nothing but the orbits of $\theta$.
\end{proof}
Note also that the final step in every chain $E(w)$ is a cover relation
from shape A to shape B. Every such cover relation is the last step of such a chain.
%\medskip
The poset $E_n$ is not a disjoint union of total orders, but its structure
is organised around this set of chains as follows.
\begin{prop}
\label{autre_chaine}
Consider a cover relation $u_1 \to u_2$ in $E_n$ where $u_1$ and
$u_2$ are in two distinct chains $E(w_1)$ and $E(w_2)$. Then there
exists a cover relation $w_1 \to w_2$ in $\Dyck_{n-2}$.
\end{prop}
\begin{proof}
The cover relation $u_1 \to u_2$ must be between two elements of
shape A or two elements of shape B, because cover relations from shape A
to shape B are inside chains, as noted above. If both $u_1$ and $u_2$
have shape B, then the statement is clear. Assume therefore that
both $u_1$ and $u_2$ have shape A.
In this situation, $u_1$ can be written as $(1,w'_1,0,w''_1,1,0)$,
where $w_1 = w'_1 w''_1$ is a concatenation of Dyck paths. The cover
relation $u_1 \to u_2$ can not be the sliding move along the $0$
between $w'_1$ and $w''_1$, because this move is in the chain
$E(w_1)$. It can therefore only happen inside $w'_1$ or inside
$w''_1$. This implies that $u_2$ is $(1,w'_2,0,w''_2,1,0)$, with
either only $w'_2$ or only $w''_2$ changed by a cover
relation. Therefore $w_2 = w'_2 w''_2$ and this implies that there
is a cover relation from $w_1$ to $w_2$.
\end{proof}
\begin{prop}
Let $v$ be an non-empty Dyck path. The top element of
the unique chain $E(w)$ containing $(v,1,0)$ is the unique minimal
element among all Dyck paths $(1,w',1,0,0)$ such that
$(v,1,0) \leq (1,w',1,0,0)$.
\end{prop}
\begin{proof}
Consider any sequence of cover relations from $(v,1,0)$ to some
$(1,w',1,0,0)$. Note that this takes place entirely inside
$E_n$. The chosen sequence of cover relations is made either of
cover relations inside one chain, or of cover relations between chains. By
\Cref{autre_chaine}, the first reached element of shape B
must be the last element $(1,w'',1,0,0)$ of some chain $E(w'')$ where
$w \leq w''$. The remaining cover relations are between elements of shape
B, and therefore $w \leq w'' \leq w'$. The statement follows.
\end{proof}
Let us now use all of this to give a precise description of the set of core intervals. By replacing the bottom
element of such an interval $[u,(1,w',1,0,0)]$ by the top element of its chain $E(w)$, one
gets an interval between elements of shape B, or equivalently an
interval $[w,w']$ in $\Dyck_{n-2}$. The position of $u$ in the chain
$E(w)$ is described by an integer $i$ between $0$ and the number of
blocks of $w$. This defines a map from the set of core intervals
sending $[u,(1,w',1,0,0)]$ to the pair ($[w,w']$, $i$). Conversely, given any
interval $[w,w']$ in $\Dyck_{n-2}$ and any integer $i$ between $0$ and
the number of blocks of $w$, one can recover the full chain $E(w)$ and
pick $u$ by its index in this chain.
To summarize, one has the following description.
\begin{prop}
\label{core_cata}
There is a bijection between core intervals in $\Dyck_{n}$ and pairs
made of an arbitrary interval $[w,w']$ in $\Dyck_{n-2}$ and an
integer between $0$ and the number of blocks of $w$.
\end{prop}
\section{Counting the intervals}
\label{section-counting}
In this section, we use the previous structural results on intervals to count them.
\begin{theorem}
\label{comptage}
The number of intervals in the poset $\Dyck_n$ is $1$ for $n=0$ and
\begin{equation}
3 \frac{2^{n-1} (2n)!}{n!(n+2)!} \quad \text{for}\quad n \geq 1.
\end{equation}
\end{theorem}
This formula describes exactly the sequence \oeis{A000257}, whose
first few terms are
\begin{equation*}
1, 1, 3, 12, 56, 288, 1584, 9152, \dots
\end{equation*}
This is also the number of rooted bicubic planar maps on $2n$ vertices
\cite{tutte}, the number of rooted Eulerian planar maps with $n$ edges, the
number of modern intervals in the Tamari lattice on $\Dyck_n$ and the
number of new intervals in the Tamari lattice on $\Dyck_{n+1}$
\cite{chap_slc}. For a simple bijection between these last two kinds of
intervals, see~\cite{rognerud}.
\begin{proof}
The proof uses a recursive description of all the intervals, based on
the previous structural results. The good catalytic parameter turns
out to be the number of blocks of the minimum of the interval.
Let $A_n$ be the set of all intervals in $\Dyck_n$ for $n \geq 0$. Let
$R_n$ be the subset of $A_n$ made of intervals whose minimum has the
shape $(w,1,0)$ (\emph{Reduced intervals}), plus the interval (empty,
empty). Let $C_n$ be the subset of $A_n$ made of intervals whose
minimum has the shape $(w,1,0)$ and whose maximum has the shape
$(1,w,1,0,0)$ (\emph{Core intervals}), plus the interval
$(1,0,1,0),(1,0,1,0)$.
Let $f_A$, $f_R$, $f_C$ be the associated generating series,
with a variable $t$ for the size and a variable $s$ for the number of
blocks in the minimum of the interval.
From the factorisation property of principal upper ideals in \Cref{princi}, one gets~\eqref{eq_fA_fR}, that we repeat here:
\begin{equation}
f_A = f_R + t (f_A - 1) f_A|_{s=1}.
\end{equation}
Let us apply the freeness of the monoid of intervals $\monoi$
(\Cref{free_M2}) to the subset of intervals whose minimum ends with
$(1,0)$. This gives that any such interval can be written uniquely as
a product in $\monoi$. Then because the minimum ends with $(1,0)$, the
minimum of the last factor also ends with $(1,0)$ and this last factor
is therefore a core interval. This gives a bijection between reduced
intervals and pairs (interval, core interval), where the left term is
the product of the other factors. This implies
\begin{equation}
\frac{f_R - 1}{s t} = 1 + \frac{f_A - 1}{st} \frac{f_C}{st},
\end{equation}
where the division by $s t$ is necessary to respect the grading of $\monoi$.
From the properties of core intervals obtained in \Cref{magie}, namely \Cref{core_cata}, one gets
\begin{equation}
f_C = s^2 t^2 \left( 1 + \frac{s f_A-f_A|_{s=1}}{s - 1} \right).
\end{equation}
All together, these three equations give the functional equation
\begin{equation}
f_A = 1 + s t + s t (f_A - 1) \left( 1 + \frac{s f_A-f_A|_{s=1}}{s - 1} \right) + t (f_A - 1) f_A|_{s=1}.
\end{equation}
Using the general method of~\cite{mbmj} to deduce an algebraic
equation from this kind of functional equation with one catalytic
parameter, one gets (as the unique pertinent factor) the equation
\begin{equation}
16 g^{2} t^{2} - g (8 t^{2} + 12 t - 1) + t^{2} + 11 t - 1
\end{equation}
for the generating series $g = f_A|_{s=1}$, in which one recognizes
the known algebraic equation for the sequence \oeis{A000257}. This
implies \Cref{comptage}.
\end{proof}
%\smallskip
The first few terms of these series are
\begin{gather*}
f_A = 1 + st + \left(2s^{2} + s\right)t^{2} + \left(5s^{3} + 5s^{2} + 2s\right)t^{3} + \left(14s^{4} + 21s^{3} + 15s^{2} + 6s\right)t^{4} + \cdots
\\
%\end{equation*}
%\begin{equation*}
f_R = 1 + st + 2s^{2}t^{2} + \left(5s^{3} + 3s^{2}\right)t^{3} + \left(14s^{4} + 16s^{3} + 8s^{2}\right)t^{4} + \cdots
\\
%\end{equation*}
%\begin{equation*}
f_C = 2s^{2}t^{2} + \left(s^{3} + s^{2}\right)t^{3} + \left(2s^{4} + 3s^{3} + 3s^{2}\right)t^{4} + \cdots
\end{gather*}
\subsection{Refinement of enumerative correspondence}
It follows from \Cref{comptage} that the number of intervals in
$(\Dyck_n, \leq)$ is the same as the number of modern intervals in the
Tamari partial order on the same set. In this section, a conjectural
refinement of this equality is proposed.
%\smallskip
We will use the short form \emph{binary tree} for \emph{rooted binary plane tree}.
Let us define a map $\kappa$ from Dyck paths of size $n$ to binary trees with $n$ inner vertices, by induction on $n$. When
$n=0$, the empty Dyck path is sent to the binary tree that is just one
leaf. If the Dyck path $w$ is block-indecomposable, it can be written
$w = (1,w',0)$ for some smaller Dyck path $w'$. Then $\kappa(w)$ is
obtained from $\kappa(w')$ by adding one inner vertex (and two leaves) on the rightmost
leaf. Otherwise, cutting $w$ before the last block defines two
smaller Dyck paths $w_1$ and $w_2$ such that $w = w_1 w_2$. Then
$\kappa(w)$ is defined by grafting the root of $\kappa(w_1)$ on the
second leaf from the right of $\kappa(w_2)$.
\begin{prop}
The map $\kappa$ is a bijection.
\end{prop}
\begin{proof}
It is enough to be able to build the inverse by induction. Let us
simply sketch the construction. Consider a binary tree
$t$. Let $v$ be the parent vertex of its rightmost leaf.
If $v$ is directly connected to two leaves, then one can remove $v$
to get another binary tree $t'$, apply the inverse of $\kappa$ by
induction to get a Dyck path $w'$ and define $w = (1,w',0)$. Clearly
$\kappa(w) = t$.
Otherwise, cut the tree $t$ along the left branch of the vertex
$v$. This gives two trees $t_1$ (above the cut) and $t_2$ (below the
cut). Applying the inverse of $\kappa$ by induction gives two Dyck
paths $w_1$ and $w_2$. Define $w$ to be their concatenation
$w_1 w_2$. Clearly again $\kappa(w) = t$.
\end{proof}
\begin{prop}
The bijection $\kappa$ from Dyck paths to binary trees
is such that, when $t = \kappa(w)$, the number of vertices on
the rightmost branch of $t$ is the number of final zeros of $w$.
\end{prop}
\begin{proof}
By induction on $n$. This is obvious for $n=0$. The
two possible steps (for block-indecomposable $w$ or otherwise) in
the inductive definition of the bijection $\kappa$ do preserve this
property, as can be readily checked.
\end{proof}
\begin{conjecture}
The bijection $\kappa$ from Dyck paths to binary trees
is such that, when $t = \kappa(w)$, the number of modern intervals
with minimum $t$ in the Tamari lattice is the size of the dexter
upper ideal with minimum $w$.
\end{conjecture}
\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=.4]
\draw[gray,very thin] (0, 0) grid (16, 3);
\draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 2) -- (11, 3) -- (12, 2) -- (13, 1) -- (14, 0) -- (15, 1) -- (16, 0);
\end{tikzpicture}
\includegraphics[width=3cm]{figures/kappa.pdf}
\caption{Illustration of the bijection $\kappa$}
\end{figure}
\section{Semilattice property}
\label{section-semilattice}
The aim of this section is to prove that $\Dyck_n$ is a lower
semilattice, namely any two elements have a meet. This will be done by
providing an explicit procedure to compute the meet of two elements
$a$ and $b$. At each step of this procedure, the pair $(a,b)$ is
replaced by another pair $(a',b')$ such that $(a',b')$ are strictly closer to
each other (in the sense of sharing a longer prefix) and the elements below both $a$ and $b$ are
exactly the elements below both $a'$ and $b'$. The procedure ends when $a$
becomes equal to $b$.
\subsection{Some technical lemmas}
This subsection proves several useful lemmas, that will be used in
\Cref{proof_semi} to describe the meet-building procedure.
Let us say that two elements $u$ and $v$ in $\Dyck_n$ share a prefix
of length $i$ if the first $i$ letters of $u$ are the same as the
first $i$ letters of $v$.
\begin{lemma}
\label{forcer_un}
Let $u \in \Dyck_n$, with a letter $0$ at position $i+1$. Consider
the set $R_i(u)$ of elements $v \in \Dyck_n$ such that $u \leq v$,
$u$ and $v$ share a prefix of length $i$ and $v$ has a letter~$1$ at
position $i+1$.
Either $R_i(u)$ is empty or $R_i(u)$ has a unique minimal element.
\end{lemma}
This will follow from \Cref{sub_forcer_un}.
Keeping the same notations, let us denote by $p$ (as \emph{prefix}) the first $i$ letters
of $u$. Then $u$ has a unique expression of the form
\begin{equation}
\label{locked_pic}
u = p \, 0^{\ell} \, X_0 0^{k_0} \, X_1 0^{k_1} \, \dots X_r 0^{k_r} \, X_{r+1},
\end{equation}
where for $j \leq r$ each $X_j$ is a non-empty Dyck path, $\ell > 0$,
all $k_j > 0$ and the final $X_{r+1}$ is any Dyck path (possibly
empty). This expression is obtained by starting after the prefix $p$ and
repeatedly doing the following : go down along the $0$ until reaching a
point before a letter $1$ (or final), then move on the path until reaching the
first point at the same height that is followed by a letter $0$ (or final).
%\medskip
Each of the $X_j$ is made of one or several blocks. Such a block is
\emph{unlocked} if it can be slid without changing the prefix, and
\emph{locked} otherwise.
In each $X_j$ for $j \leq r$, all the blocks but the last one are
unlocked. In the last Dyck path $X_{r+1}$, all the blocks are unlocked.
\begin{center}
Here is a sketch: \includegraphics[width=4cm]{figures/section7_picture1.pdf}, with locked blocks darker.
\end{center}
If for every $j \leq r$, the Dyck path $X_j$ has only one block and
$X_{r+1}$ is empty, then there is no unlocked block in $u$. In this
case, the set $R_i(u)$ in the statement of \Cref{forcer_un} will be
empty. Indeed any cover relation not changing the prefix will keep the
shape of the expression~\eqref{locked_pic} fixed, so that no block
becomes unlocked and $X_0$ can never be slid.
Let us therefore from now on assume the contrary. In this case, let us
denote by $\rise_i(u)$ the element obtained from $u$ by sliding the
first block in the first $X_j$ that contains an unlocked block, up to
the height of the starting point of the last block of the previous
$X_{j-1}$ or up to the end of the prefix $p$ of $u$ if $j = 0$. In the
resulting Dyck path, there is an unlocked block inside $X_{j-1}$ if
$j > 0$.
This defines an operator $\rise_i$ that acts by sliding one unlocked block. One
will also need the operator $\rise^{(2)}_i$ defined similarly but
sliding the second available unlocked block.
\begin{lemma}
\label{sub_forcer_un}
Let $u \in \Dyck_n$, with a letter $0$ at position $i+1$. Let
$v \in \Dyck_n$ such that $u \leq v$, $u$ and $v$ share a prefix of
length $i$ and $v$ has a letter $1$ at position $i+1$. Then
$\rise_i(u) \leq v$.
\end{lemma}
\begin{proof}
The proof will use a decreasing induction (in the poset) on $u$
among elements smaller than $v$ and sharing with $u$ the same prefix
of length $i+1$.
Since $u \leq v$, there must be an element $u'$ covering $u$ such
that $u' \leq v$. Necessarily, $u'$ shares a prefix of length $i$
with $u$ and $v$.
It can happen that there is no such $u'$ sharing with $u$ a prefix
of length $i+1$. This is the base case for the induction and it will
just be taken care of below inside the case~\ref{sub2.1}. Otherwise, pick
such an $u'$.
\smallskip
The possible such cover relations $u \leq u'$ can be classified into several types:
\begin{enumerate}%[label=(\arabic*)]
\item\label{proof_lemma7.2_1} strictly inside one of the blocks of $X_k$ with $k \leq j$,
\item\label{proof_lemma7.2_2} one block of $X_j$ is slid,
\item\label{proof_lemma7.2_3} somewhere on the right of $X_j$.
\end{enumerate}
Let us first assume that there is a cover relation $u \leq u'$ of type~\eqref{proof_lemma7.2_1}
with $u' \leq v$. In $u'$, one finds the same first unlocked block
as in $u$. By induction, one also has $\rise_i(u') \leq v$. There
is a sequence of cover relations $u \leq u' \leq \rise_i(u')$. But these
cover relations commute, so that $\rise_i(u) \leq \rise_i(u')$.
Let us now assume that there is a cover relation $u \leq u'$ of type~\eqref{proof_lemma7.2_3} with $u' \leq v$. In $u'$, one finds the same first unlocked
block as in $u$, because this block is not the last block of
$X_j$. By induction, one also has $\rise_i(u') \leq v$. There is a
sequence of cover relations $u \leq u' \leq \rise_i(u')$. But these
cover relations also commute, so that again
$\rise_i(u) \leq \rise_i(u')$.
There remains to assume that there is a cover relation $u \leq u'$
of type~\eqref{proof_lemma7.2_2} with $u' \leq v$. There are three sub-cases.
\begin{enumerate}[(2.\arabic{enumi})]
% (2.3)
\setcounter{enumi}{2}
\item\label{sub2.3}
If the slid block $B$ is neither the
first block nor the second block of $X_j$, then one can argue as in
type~\eqref{proof_lemma7.2_3}, because the first unlocked block remains the
first block of $X_j$, which is not affected.
\setcounter{enumi}{1}
\item\label{sub2.2}
% (2.2)
If the slid block $B$ is the second block of $X_j$, then either
$X_j$ contains at least~$3$ blocks or the block $B$ is at the end of
$u$, for otherwise $B$ is locked. Then one can
check directly that there is a cover relation
$\rise_i(u) \to \rise_i(u')$. By induction, one also has $\rise_i(u') \leq v$.
\begin{figure}[htb]
\centering
$u$\begin{tikzpicture}[scale=.15]
\draw[rounded corners=1, color=black, line width=2] (4, 4) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 2) -- (11, 1) -- (12, 0) -- (13, 1) -- (14, 2) -- (15, 1) -- (16, 0) -- (17, 1);
\draw[rounded corners=1, color=black, fill=gray, line width=2] (12, 0) -- (13, 1) -- (14, 2) -- (15, 1) -- (16, 0);
\end{tikzpicture}$\quad\phantom{\longrightarrow}\put(-15,5){$\longrightarrow$} \quad u'$
\begin{tikzpicture}[scale=.15]
\draw[rounded corners=1, color=black, line width=2] (4, 4) -- (5, 3) -- (6, 2) -- (7, 1) -- (8, 0) -- (9, 1) -- (10, 2) -- (11, 1) -- (12, 2) -- (13, 3) -- (14, 2) -- (15, 1) -- (16, 0) -- (17, 1);
\draw[rounded corners=1, color=black, fill=gray, line width=2] (11, 1) -- (12, 2) -- (13, 3) -- (14, 2) -- (15, 1) ;
\end{tikzpicture}
\caption{First blocks of $X_j$ for the case~\ref{sub2.2} in the proof of \Cref{sub_forcer_un}}
\label{cas2.2}
\end{figure}
\setcounter{enumi}{0}
\item\label{sub2.1}
% (2.1)
Assume now that the slid block $B$ is the first block of
$X_j$. If $u' = \rise_i(u)$, the statement holds directly. This is
what happens in the base case of the induction. Otherwise, the block
$B$ can either be slid too high or too low compared to the exact
height of the end of $X_{j-1}$ if $j > 0$, or too low compared to the end of the
prefix $p$ of $u$. In both cases, it becomes (part of) a locked
block. The existence of $v$ then forces that there is (in $u$ and $u'$) another
unlocked block in $X_k$ for some $k \geq j$.
If the first block $B$ of $X_j$ is slid too low in $u'$, one can
apply repeatedly $\rise_i$ to $u'$ until this operator is sliding
again the block $B$ itself. Let us call $u''$ the result. Starting
from $X_k$ which contains the first unlocked block in $u'$, each
$\rise_i$ unlocks the first block in the previous $X$. Then by
induction, one has $u'' \leq v$. One can also see that
$\rise_i(u) \leq u''$ by repeating on $\rise_i(u)$ all the same
slidings performed from $u'$ to $u''$.
The first block $B$ of $X_j$ can only be slid too high in $u'$ if
$j > 0$, because otherwise the prefix would change. In this case,
one can apply repeatedly $\rise_i$ to $u'$ until this operator is
unlocking the block containing the slid block $B$ itself. Let us
call $u''$ the result. Then by induction, one has $u'' \leq v$. Then
one can apply the operator $\rise^{(2)}_i$ several times on
$\rise_i(u)$ until making the slid block $B$ unlocked again. In
other words, one replays on $\rise_i(u)$ all the sliding moves
performed on $u'$, by replacing the action of $\rise_i$ by the
action of $\rise^{(2)}_i$. Let us call the result $\bar{u}$. Then in $\bar{u}$,
the block $B$ is unlocked and sliding this block (to the appropriate
height) gives a cover relation $\bar{u} \to u''$. This implies that
$\rise_i(u) \leq u''$.
\end{enumerate}
In all cases, one obtains that $\rise_i(u) \leq v$.
\end{proof}
\begin{proof}
Let us now give the proof of \Cref{forcer_un}.
One can assume that $R_i(u)$ is not empty. Let us pick any $v$ in $R_i(u)$.
Then one can iterate \Cref{sub_forcer_un}, which when applied to the
pair $(u,v)$ gives another pair $(\rise_i(u),v)$ that satisfies the
same hypotheses as long as $j > 0$. At each step, the index $j$ of
$x_j$ containing the first unlocked block in $u$ is decreased by
one. In the last step, when $j=0$, the element $\rise_i(u)$ becomes an
element $w$ of $R_i(u)$ such that $w \leq v$.
Because the construction of $w$ is an iteration of $\rise_i$ applied
to $u$, it does not depend on $v$. Therefore $w$ is smaller than any
element of $R_i(u)$. Uniqueness of such a global minimum is clear.
\end{proof}
%\medskip
For $v,w$ in $\Dyck_n$, let $M(v,w)$ be the set of Dyck paths that are
smaller than both $v$ and $w$. This set is never empty.
\begin{lemma}
\label{meet_with_prefix}
Let $v$ and $w$ in $\Dyck_n$ that share a prefix of length $i$. Then
for every element $u$ in $M(v,w)$, there exists $u'$ in $M(v,w)$
such that $u \leq u'$ and $u'$ shares a prefix of length $i$ with $v$
and $w$.
\end{lemma}
\begin{proof}
By induction on $i$. This is true for $i=1$, for $u'=u$. Assume now
that $v$ and $w$ share a prefix of length $i+1$ and let $u'_i$
be defined by induction hypothesis for the shorter common prefix of
length $i$. If the last letter in the common prefix of length $i+1$
is the same as the letter of $u'_i$ at position $i+1$, one can take
$u'$ to be $u'_i$.
Because $u'_i \in M(v,w)$, there remains only the case where the
letter of $u'_i$ at position $i+1$ is $0$ and the last letter in the
common prefix of length $i+1$ of $v$ and $w$ is $1$. Let us apply
\Cref{forcer_un} to $u'_i$. The set $R_{i}(u'_i)$ is not empty as
it contains $v$ and $w$. One can therefore take $u'$ to be its unique
minimal element.
\end{proof}
\subsection{Proof of semilattice property}
\label{proof_semi}
Let us start with more lemmas.
Let $w$ be a Dyck path such that the $i$-th step in $w$ is $1$ and
this step does not start at height $0$. On the right from the start
$i_0$ of $i$-th step, move on the path $w$ until meeting a point $i_1$
at the same height and followed by a $0$ step. This must happen, as
the height of $i_0$ is not zero. Between $i_0$ and $i_1$, there is in
$w$ a non-empty sequence of block-indecomposable subpaths $x_1, \dots, x_N$.
Let us define another Dyck path $\des_i(w)$ by sliding down in $w$ the
subpath $x_N$ as much as possible, namely by exchanging $x_N$ with all
the consecutive $0$ steps on its right. Then there is a cover relation
$\des_i(w) \to w$ that is sliding the subpath $x_N$ up.
\begin{lemma}
\label{sub_force_0}
Let $w$ be a Dyck path such that the $i$-th step in $w$ is $1$ and
this step does not start at height $0$. Let $u \leq w$ such that the
$i$-th step in $u$ is $0$ and $u$ and $w$ share a prefix
of length $i - 1$. Then $u$ is smaller than $\des_i(w)$.
\end{lemma}
\begin{proof}
The proof will be by increasing induction (in the poset) on $w$
among elements larger than $u$ and sharing with $u$ the same prefix
of length $i - 1$.
Since $u \leq w$, there exists $w'$ covered by $w$ such that
$u \leq w'$. Necessarily, $w'$ shares the same prefix of length
$i-1$ with $u$ and $w$.
It can happen, in the base case of the induction, that there is no
such $w'$ that shares with $w$ a prefix of length $i$. Then it must
be the case that $N=1$ and $w' = \des_i(w)$.
If $w' = \des_i(w)$, the statement clearly holds.
Because of the shared prefix, the other possible down-sliding moves
from $w$ are of three types, according to the slid subpath $x$:
\begin{enumerate}%[label=(\arabic*)]
\item\label{proof_lemma7.4_1} $x$ is inside one of the $x_j$, not ending in the final
sequence of $0$ of $x_j$,
\item\label{proof_lemma7.4_2} $x$ is inside one of the $x_j$, ending in the final
sequence of $0$ of $x_j$,
\item\label{proof_lemma7.4_3} $x$ is somewhere on the right of $x_N$.
\end{enumerate}
In type~\eqref{proof_lemma7.4_1}, $x_j$ is replaced by another block-indecomposable
subpath. In type~\eqref{proof_lemma7.4_2}, if $j < N$, then $x_j$ is replaced by (split
into) two block-indecomposable subpaths.
Assume first that $u \leq w'$ where $w' \to w$ is of type~\eqref{proof_lemma7.4_3}. By
induction, $u \leq \des_i(w')$. There is a chain of cover relations
$\des_i(w') \to w' \to w$. These two cover relations commute if the slid
subpath in the sliding move $w' \to w$ is not the first subpath after
$x_N$. Otherwise, one can find a chain of two cover relations from
$\des_i(w')$ to $\des_i(w)$. In all cases,
$\des_i(w') \leq \des_i(w)$.
Assume now that $u \leq w'$ where $w' \to w$ is of type~\eqref{proof_lemma7.4_1}. By
induction, $u \leq \des_i(w')$. There is a chain of cover relations
$\des_i(w') \to w' \to w$. These cover relations commute, and therefore
$\des_i(w') \leq \des_i(w)$.
Assume then that $u \leq w'$ where $w' \to w$ is of type~\eqref{proof_lemma7.4_2}. By
induction, $u \leq \des_i(w')$. There is a chain of cover relations
$\des_i(w') \to w' \to w$. If $j < N - 1$, these cover relations
commute, and therefore $\des_i(w') \leq \des_i(w)$.
If $j = N$, then one can apply twice the induction step to obtain that
$u \leq \des_i(\des_i(w'))$. But $\des_i(\des_i(w')) \leq \des_i(w)$
because one can split $x_N$ after it has been slid down.
If $j = N-1$, one can also apply twice the induction step, to get
that $u \leq \des_i(\des_i(w'))$. One then checks that
$\des_i(\des_i(w')) \leq \des_i(w)$ holds also in this case, by just
one cover relation.
One therefore deduces the statement in all cases.
\end{proof}
Keeping the same notations, let $s_i(w)$ denote $\des_i^N(w)$, the
image of $w$ under the $N$-times iteration of the application
$\des_i$.
\begin{lemma}
\label{force_0}
Let $w$ be a Dyck path such that the $i$-th step in $w$ is $1$ and
this step does not start at height $0$. Let $S_i(w)$ be the set
of all Dyck paths $u$ such that $u \leq w$, the $i$-th letter of $u$
is $0$ and $u$ and $w$ share the same prefix before the $i$-th letter.
Then $s_i(w)$ is the unique maximal element of $S_i(w)$.
\end{lemma}
\begin{proof}
First note that $s_i(w)$ is indeed in $S_i(w)$.
Let $u$ be an element of $S_i(w)$. One can apply \Cref{sub_force_0}
to the pair $(u,w)$ to get another pair $(u, w')$ where
$w'=\des_i(w)$. Either $w' = s_i(w)$, or this new pair satisfies
again the hypotheses of \Cref{sub_force_0}. One can therefore repeat
this exactly $N$ times, until reaching the pair $(u,s_i(w))$. In
particular, $u \leq s_i(w)$.
\end{proof}
\begin{theorem}
The poset $(\Dyck_n, \sm)$ is a meet-semilattice.
\end{theorem}
\begin{proof}
Let $v$ and $w$ be two Dyck paths, and let us look for their
meet. One can assume that $v$ and $w$ are not equal.
Start from the left, until meeting a difference between $v$ and
$w$. Let $i$ be the last common point. One can assume that $w$ is
above $v$ just after the point $i$, by exchanging $v$ and $w$ if
necessary. Note that the height of $i$ cannot be zero.
One can therefore apply \Cref{force_0} to $w$ for the step after
position $i$, and obtain an element $w'$ which is maximal among all
elements smaller than $w$ that share the same prefix followed by
the letter $0$.
This gives a new pair of elements $(v,w')$ with $w' \leq w$. Let us
prove that $M(v,w) = M(v,w')$. The inclusion $M(v,w') \subseteq
M(v,w)$ is clear because $w' \leq w$.
Conversely, let $u$ be an element of $M(v,w)$. Using
\Cref{meet_with_prefix}, one can find $u'$ in $M(v,w)$ with $u \leq
u'$ and $u'$ share the common prefix of $v$ and $w$. Note that the
first letter after the common prefix in $u'$ is $0$, because $u'
\leq v$. It therefore follows from the definition of $w'$ that $u'
\leq w'$.
Hence $M(v,w) = M(v,w')$, and the common prefix of $v$ and $w'$ is
strictly longer. Therefore iterating this whole procedure on pairs
of Dyck paths ends at a common Dyck path $z$, that is smaller than
$v$ and $w$ and such that $M(z,z) = M(v,w)$. This $z$ is therefore
the meet of $v$ and $w$.
\end{proof}
\section{The Hochschild polytope as an interval}
\label{section-hochschild}
In this section, we explain an unexpected connection between a
specific interval in $\Dyck_{n+2}$ and a cell complex called the
Hochschild polytope, introduced in algebraic topology by Saneblidze
\cite{san_arxiv, san_note, rivera_san}. Our initial reason for looking at this
particular interval was its appearance inside the interval of largest
cardinality among all $I(w)$, as defined in \Cref{specific}.
Let us start by one word of caution. Although the name ``Hochschild
polytope'' refers to a true convex polytope, the Saneblidze
coordinates that we will be using here only describes a topological or
cubical deformation of it. In other words, some of the Saneblidze
coordinates are not extremal in their convex hull. For the correct
polytopal construction of the Hochschild polytope as an iterated
truncation of a simplex, and the relation to the
Saneblidze coordinates, see Section~3.2 of~\cite{rivera_san}.
\looseness-1
For $n \geq 1$, let $F_n$ be the interval in $\Dyck_{n+2}$ between
$(1,1,0,0,(1,0)^{n})$ and $(1,1^n,0^n,1,0,0)$. This is indeed an
interval, as one can go from the former to the latter by sliding (in
their order from left to right) all the initial blocks $(1,0)$
(all of them are slid to the maximal possible height, except the
last one that is slid to height $1$).
\begin{figure}[htb]
\centering
\begin{tikzpicture}[>=latex,line join=bevel,scale=0.25]
%%
\node (node_1) at (89.0bp,135.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\node (node_0) at (89.0bp,33.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=.15] \draw[gray,very thin] (0, 0) grid (6, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);\end{tikzpicture}$}}$};
\draw [blue,->,dashed] (node_0) ..controls (89.0bp,74.031bp) and (89.0bp,83.221bp) .. (node_1);
%
\end{tikzpicture}
\begin{tikzpicture}[>=latex,line join=bevel,scale=0.25]
%%
\node (node_4) at (243.0bp,381.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_3) at (370.0bp,251.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 3); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_2) at (117.0bp,251.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_1) at (144.0bp,135.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\node (node_0) at (217.0bp,33.0bp) [draw,draw=none] {$\vcenter{\hbox{$\begin{tikzpicture}[scale=0.15] \draw[gray,very thin] (0, 0) grid (8, 2); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0) -- (7, 1) -- (8, 0);\end{tikzpicture}$}}$};
\draw [red,->] (node_0) ..controls (251.39bp,77.124bp) and (261.29bp,90.01bp) .. (270.0bp,102.0bp) .. controls (292.05bp,132.36bp) and (315.59bp,167.08bp) .. (node_3);
\draw [blue,->,dashed] (node_0) ..controls (187.31bp,74.669bp) and (180.04bp,84.625bp) .. (node_1);
\draw [blue,->,dashed] (node_3) ..controls (314.98bp,307.46bp) and (305.27bp,317.24bp) .. (node_4);
\draw [blue,->,dashed] (node_1) ..controls (133.49bp,180.36bp) and (130.02bp,195.02bp) .. (node_2);
\draw [red,->] (node_2) ..controls (160.81bp,296.5bp) and (175.79bp,311.73bp) .. (node_4);
%
\end{tikzpicture}
\caption{The Hochschild intervals $F_1$ and $F_2$.}
\end{figure}
Let us start by three small lemmas, towards an alternative description of
the elements of $F_n$ in \Cref{intrinsics}.
Let us define a \emph{valley} in a Dyck path to be a subword
$(0,1)$, which means a local minimum for the height
function. Similarly, a \emph{peak} is a local maximum of height.
Note that all elements of $F_n$ start with $(1,1)$. Moreover, all the
valleys in all elements of $F_n$ have height $0$ or $1$. This follows
from the next lemma, as this is true for the maximum of $F_n$.
\begin{lemma}
\label{hauteur01}
Let $w$ be a Dyck path having only valleys at height $0$ or
$1$. If $y \leq w$, then $y$ has the same property.
\end{lemma}
\begin{proof}
It is enough to prove this when $y$ is covered by $w$.
\looseness-1
If $w$ has a valley at height $0$, then $y$ has the same valley. One
can therefore assume that $w$ is block-indecomposable, and has only
valleys at height $1$. Then one can check that all possible
down-sliding moves from $w$ can only create a valley at level $0$ or
$1$.
\end{proof}
\begin{lemma}
\label{ht_decroit}
Let $w \in F_n$. Then the height of the valleys in $w$ is weakly
decreasing from left to right.
\end{lemma}
\begin{proof}
Otherwise, there is a valley of height $0$ followed by a valley of
height $1$. The subpath after the valley of height $0$ must be
slid at some point in any chain of cover relations from $w$ to the maximum
of $F_n$, but this would create a valley of height at least
$2$. This is absurd.
\end{proof}
\begin{lemma}
\label{picfin}
For $n \geq 1$, every element of $F_n$ ends either with $(0,1,0)$ or
with $(0,1,0,0)$.
\end{lemma}
\begin{proof}
The only other possibility is to end with $(1,1,0,0)$,
because of the shape of the maximum of $F_n$. But then this final
subpath can not be slid with the result being still below
the maximum of $F_n$. This is absurd.
\end{proof}
\begin{lemma}
\label{intrinsics}
The set $F_n$ can be described as the set of Dyck paths starting
with $(1,1)$, having only valleys of height $0$ or $1$, where these
heights are decreasing from left to right, and ending either by
$(0,1,0)$ or by $(0,1,0,0)$.
\end{lemma}
\begin{proof}
Let us call $Q_n$ this set of elements. By the preceding lemmas and remarks,
$Q_n$ contains $F_n$. For the converse inclusion, one only needs to
check the two following statements: (1) an element of $Q_n$ which is
not the maximum of $F_n$ can be covered by another element of $Q_n$
and (2) an element of $Q_n$ which is not the minimum of $F_n$ covers
another element of $Q_n$.
%\begin{enumerate}
(1)
%\item
Let $z$ be an element of $Q_n$. If $z$ has exactly two peaks,
then $z$ is either the maximum of $F_n$ or is covered by this
maximum. One can therefore assume that there are at least three
peaks in $z$, hence at least two valleys. If there is a valley of
height $0$, one can slide by one step the subpath after the first
valley of height $0$, which becomes a valley of height $1$. The
result is still in $Q_n$. If all valleys have height $1$, one can
slide the peak after the first valley, to replace the first two
peaks by a single peak.
(2)
%\item
Let $z$ be an element of $Q_n$. If it ends with $(0,1,0,0)$, one
can slide down this last peak and get another element of
$Q_n$. Otherwise, $z$ ends with $(0,1,0)$. If it has a valley at
height $1$, one can slide down the subpath after the rightmost
valley of height $1$. Otherwise one can take any peak of height at
least $2$ and slide down the top $(1,0)$ subpath of this peak. This
creates two peaks and the result is an element of $Q_n$ except when
the only available peak of height at least $2$ is at the beginning
of $z$ and has height $2$. But then $z$ is the minimum of $F_n$.\qedhere
%\end{enumerate}
\end{proof}
\begin{rema}
\label{two_peaks}
Note that being block-indecomposable is equivalent inside $F_n$ to
having no valley at height $0$. Note also that for $n \geq 1$ every
element of $F_n$ has at least two peaks, because the unique path
with just one peak is not in $F_n$.
\end{rema}
Let us define $F_{n,b}$ as the subset of block-indecomposable elements
of $F_{n}$.
We will now state many lemmas, whose aim is to prepare the ground for
the relationship with Saneblidze coordinates in \Cref{th_san}.
\begin{lemma}
\label{booleen_top}
For $n \geq 1$, the subset $F_{n,b}$ form a boolean lattice of
cardinality $2^{n-1}$ with minimum $w_{n,b} = (1,1,(0,1)^n,0,0)$ and the
same maximum as $F_n$.
\end{lemma}
\begin{proof}
Because all valleys must have height $1$, the shape of possible Dyck
paths is strongly constrained by \Cref{intrinsics}. The rightmost
peak must have height $2$, and this forces at least one valley just
before the final $(1,0,0)$. Every subset of the valleys of $w_{n,b}$
that contains this rightmost one defines a unique element in the
interval. The induced partial order is given by inclusion of subsets
of valleys.
\end{proof}
\begin{rema}
\label{split_Fb}
This boolean lattice on $F_{n,b}$ can be written as the disjoint union of
two boolean lattices of half cardinality: elements ending with
$(1,0,1,0,0)$ (bottom part) and the others (top part).
\end{rema}
\begin{lemma}
\label{booleen_bot}
The subset of $F_n$ of elements having only valleys of height $0$ is
a boolean lattice of cardinality $2^{n-1}$. The minimum is the same
as the minimum of $F_n$ and the maximum is $(1^{n+1},0^{n+1},1,0)$.
\end{lemma}
\begin{proof}
The proof is very similar to the proof of \Cref{booleen_top}.
\end{proof}
Let us now define a map $\rho$ from $F_n$ to some set of words of
length $n$ in the alphabet $\{0,1,2\}$. Let $w$ be a Dyck path in
$F_n$. One reads the word $w \in F_n$ from left to right skipping the first two letters, while
keeping track of an integer $N_2$ (initially set to $0$) and some
prefix of the image $\rho(w)$ (initially the empty word). When a letter $1$ is read in $w$ and is preceded by another $1$,
the integer $N_2$ is increased by $1$. When a valley of $w$ is read
(with height $h$ being either $0$ or $1$ by \Cref{hauteur01}), the
word $[h,2^{N_2}]$ (where the power means that the letter $2$ is repeated) is appended to the current prefix, and $N_2$ is
then set back to $0$. The result $\rho(w)$ is the prefix obtained
after reading all of $w$. The length of $\rho(w)$ is $n$ because every
letter $1$ in $w$ (except the two initial ones) contributes a letter in $\rho(w)$.
For example, the image by $\rho$ of $(1,1,1,0,0,1,0,0,1,0) \in F_3$ is
$[1,2,0]$. The minimal element of $F_n$ is mapped by $\rho$ to the
word $[0,\dots,0]$, and the maximal element to the word
$[1,2,\dots,2]$. The image of the Dyck path $w_{n,b}=(1,1,(0,1)^n,0,0)$
is $[1,\dots,1]$.
By the map $w \mapsto \rho(w)$, the number of valleys at height $0$
(resp $1$) of $w$ becomes the number of letters $0$ (resp. $1$) in
$\rho(w)$.
The construction of $\rho$ can be reversed as follows, proving that it
is injective. Starting from any element $z$ in the image $\rho(F_n)$:
\begin{enumerate}
\item
%(1)
Split $z$ as a sequence of bricks $[1,2,\dots,2]$ and
$[0,2,\dots,2]$, formed by a letter~$0$ or $1$ and the maximal
sequence of following $2$.
\item
%(2)
Start a new Dyck path at height $0$. For each brick, use the number $N_2$ of $2$ in this
brick to move up to the appropriate height (one more for the initial
brick), then move down to height $0$ or $1$ according to the first
letter of the brick.
\item
%(3)
When the list of bricks is exhausted, move up by one step and go
down to height $0$.
\end{enumerate}
For example, one can find in this way that the pre-image of $[1,0,2]$ by $\rho$, which has
two bricks $[1]$ and $[0,2]$, is $(1,1,0,1,1,0,0,0,1,0)$.
\begin{lemma}
\label{cover_increase}
For a cover relation $w \to w'$ in $F_n$, the words $\rho(w)$ and
$\rho(w')$ differ by exactly one letter, which increases.
\end{lemma}
\begin{proof}
One has to distinguish two kinds of cover relations. If the number of
peaks is unchanged, then one valley of height $0$ becomes a valley
of height $1$. On the image by $\rho$, only the letter encoding this
height is modified. Otherwise, the number of peaks is decreased by
one and the two associated bricks in the image by $\rho$ become just
one brick. The valleys corresponding to these two bricks have the
same height. In the image by $\rho$, this means that one subword
$[x,2^M,x,2^N]$ is replaced by $[x,2^{M+1+N}]$, where $x$ is either
$0$ or $1$.
\end{proof}
%\medskip
Let us define $F_{n,0}$ and $F_{n,1}$ as the partition of $F_n$
according to the height of the first valley. This corresponds to the
decomposition of $\rho(F_n)$ according to the first letter.
\begin{lemma}
\label{intervalle_Fn1}
For $n \geq 1$, the set $F_{n,1}$ is the interval between
the element $w_{n,1} = (1,1,0,1,0,0,(1,0)^{n-1})$ and the maximum of $F_n$.
\end{lemma}
\begin{proof}
The property ($\clubsuit$) of having the first valley at height $1$ is
preserved by cover relations inside $F_n$, that can only delete a valley
of height $1$ if it is followed by another valley of height $1$.
Therefore all the elements that are greater than $w_{n,1}$ have property ($\clubsuit$).
Conversely, for any element $w \not= w_{n,1}$ with property
($\clubsuit$), one can find a strictly smaller element $w'$ with
property ($\clubsuit$). Namely, if $w$ has the shape
$(1,(1,0)^k,0,(1,0)^\ell)$, one can take $w'= w_{n,1}$. Otherwise,
$w$ has either a peak of height at least $3$ or a peak of height
at least $2$ after a valley of height $0$. In both cases, one can
slide down the $(1,0)$ subpath at the top of the peak and this
preserves the property ($\clubsuit$). This builds the required $w'$.
It follows that $w_{n,1}$ is the unique minimal element with property ($\clubsuit$).
\end{proof}
Let us also denote
$F_{n,1,0}$, $F_{n,1,1}$ and $F_{n,1,2}$ for the partition of
$F_{n,1}$ according to the last letter of the image by $\rho$.
From \Cref{cover_increase} and \Cref{intervalle_Fn1}, one deduces:
\begin{lemma}
The set $F_{n,1,2}$ is an upper ideal in $F_n$.
\end{lemma}
Some more lemmas are required, in order to obtain a full recursive
description of the sets $F_n$.
\begin{lemma}
\label{F1_F12}
For $n \geq 1$, the map that inserts $(1,0)$ at the top of the
next-to-rightmost peak defines a bijection from $F_{n,1}$ to
$F_{n+1,1,2}$. This corresponds to adding $2$ at the end of
$\rho(w)$.
\end{lemma}
\begin{proof}
This is easily checked directly for $n=1$. Let us assume that $n \geq 2$.
First, one deduces from \Cref{intrinsics} that adding $(1,0)$ at the
top of the next-to-rightmost peak defines a map from $F_{n}$ to
$F_{n+1}$. This clearly preserves the height of the first valley,
hence defines an injective map from $F_{n,1}$ to $F_{n+1,1}$.
Using the definition of $\rho$, this application does add $2$ at the
end of the image by $\rho$, because it increases the height of the
next-to-last peak by one. Therefore its image is contained in
$F_{n+1,1,2}$.
Conversely for any element $z$ of $F_{n+1,1,2}$, one can remove
$(1,0)$ on the top of the next-to-rightmost peak to define a Dyck
path $x$. This does not change the height of the valleys, in
particular the first valley of $x$ has height $1$. One just needs to
prove that $x$ is in $F_n$. Using \Cref{intrinsics}, one needs only
to check the conditions at the beginning and at the end. The
condition that $x$ starts by $(1,1)$ can fail if and only if the
next-to-rightmost peak of $z$ is its first peak and has height
$2$. This only happens when $z$ is the maximal element of $F_1$, but
$z$ belongs to $F_{n+1}$ for some $n \geq 1$. The condition at the
end is ensured by the final letter $2$ in $\rho(z)$, which implies
that removing $(1,0)$ on its top does not delete the
next-to-rightmost peak.
\end{proof}
Let us define a map $\mu$ on $F_n$ by adding $(1,0)$ at the end.
\begin{lemma}
The image of $\mu$ is contained in $F_{n+1}$.
\end{lemma}
\begin{proof}
This follows easily from \Cref{intrinsics}.
\end{proof}
Using the definition of $\rho$, one can check that adding $(1,0)$ at
the end of any $w$ in $F_n$ corresponds to adding $0$ at the end of
$\rho(w)$.
\begin{lemma}
\label{F1_F10}
For $n \geq 1$, the map $\mu$ is a bijection from $F_{n,1}$ to
$F_{n+1,1,0}$.
\end{lemma}
\begin{proof}
Applying $\mu$ on an element of $F_{n,1}$ gives an element
of $F_{n+1,1,0}$. This is clearly an injective map.
Conversely, any element $w$ of $F_{n,1,0}$ must end with $(1,0)$,
because its last valley has height $0$.
Using \Cref{intrinsics}, one can show that cutting this final
$(1,0)$ gives an element of $F_{n,1}$ whose image by $\mu$ is
$w$. The only required check is the condition at the end, which
follows from the hypothesis that the last letter of $\rho(w)$ is
$0$. This proves the surjectivity.
\end{proof}
\begin{lemma}
\label{Fb_F11}
The map that inserts $(1,0)$ just before the final letter $0$ defines a
bijection from $F_{n,b}$ to $F_{n+1,1,1}$. This corresponds to
adding $1$ at the end of $\rho(w)$.
\end{lemma}
\begin{proof}
By \Cref{booleen_top} and the remark following it, there are two
inclusions of the set $F_{n,b}$ in $F_{n+1,b}$. One can check that
the bottom inclusion is given by inserting $(1,0)$ just before the
final letter $0$. Through the application of $\rho$, this amounts to
adding a final $1$ to $\rho(w)$. The image is therefore in
$F_{n+1,1,1}$. This is clearly an injective map.
Conversely, let $w$ in $F_{n+1,1,1}$. Because the last letter in
$\rho(w)$ is $1$, and using \Cref{ht_decroit}, all valleys of $w$
have height $1$. Moreover the Dyck path $w$ must end with $(1,0,0)$,
because it is smaller than the maximum of $F_n$. But it must in fact
end with $(0,1,0,1,0,0)$, for otherwise the final letter of $\rho(w)$
would be $2$. Hence one can remove $(1,0)$ just before the final
$0$, and get an element of $F_{n,b}$, whose image is $w$.
\end{proof}
\begin{lemma}
\label{Fx_F0}
The map that slides down the subpath after the first valley defines
a bijection from the subset of $F_{n,1}$ where only the first valley
has height $1$ to $F_{n,0}$. It amounts to replacing the first
letter of $\rho(w)$ by $0$.
\end{lemma}
\begin{proof}
Let us consider an element $w$ of $F_{n,1}$ with one valley of
height $1$ and all other valleys of height $0$. There is a unique
element $w'$ in $F_{n,0}$ that is covered by $w$, which is obtained by
sliding down the subpath after the first valley in $w$. One can
check that $\rho(w')$ is obtained by replacing the first letter of
$\rho(w)$ by $0$.
Conversely, let $w'$ in $F_{n,0 }$. Then $w'$ has only valleys of
height zero. Let $w$ be obtained by sliding the subpath after the
first valley of $w'$, by just one step in order to create a valley
of height $1$. Then one can check that $w'$ is still in $F_n$ using
\Cref{intrinsics}, because the height of the rightmost peak is
always at most $2$.
Moreover $w$ has exactly one valley of height $1$. These two constructions
are clearly inverses of each other.
\end{proof}
%\medskip
The Hasse diagram of the interval $F_n$ looks like the graph of
vertices and edges of some polytope. It turns out to be related to a
familly of cell complexes due to Saneblidze. Namely, one can identify
its image by $\rho$ as the set of vertices defined by
Saneblidze in~\cite{san_arxiv}.
\begin{theorem}
\label{th_san}
The interval $F_n$ is mapped by $\rho$ to the set of coordinates of
the Hochschild polytope of Saneblidze.
\end{theorem}
%\medskip
Before entering the proof, let us start by giving a recursive
description of these sets $Z_n$ inside $\{0,1,2\}^n$, extracted
carefully from this reference and reformulated in simpler terms, as
the disjoint union of subsets $Z_n = Z_{n,0} \sqcup Z_{n,1}$. The
recursive description also involves a subset
$Z_{n,b} \subseteq Z_{n,1}$.
For $n=1$, this is given by $Z_{n,0} = \{ [0] \}$ and $Z_{n,1} = Z_{n,b} = \{ [1] \}$.
For $n \geq 1$, the description is given by:
\begin{enumerate}%[label=(\roman*)]
\item\label{intext_i} $Z_{n+1,1}$ is made of all elements $[z,0]$ and $[z,2]$ for
$z \in Z_{n,1}$ and all elements $[z,1]$ for $z \in Z_{n,b}$,
\item\label{intext_ii} $Z_{n+1,b}$ is made of all elements
$[z,1]$ and $[z,2]$ for $z \in Z_{n,b}$.
\item\label{intext_iii} The subset $Z_{n+1,0}$ is made by replacing the initial letter by
$0$ in all elements of $Z_{n+1,1}$ in which the letter $1$ only appears
as the first letter.
\end{enumerate}
By induction, all elements of $Z_{n,0}$ (resp. $Z_{n,1}$ and
$Z_{n,b}$) start with $0$ (resp. $1$). Note also that the elements of
$Z_{n,b}$ only contain the letters $1$ and $2$.
\begin{prop}
The image of $F_n$ by $\rho$ is equal to $Z_n$. Moreover $F_{n,b}$
is mapped to $Z_{n,b}$, $F_{n,0}$ to $Z_{n,0}$ and $F_{n,1}$ to
$Z_{n,1}$.
\end{prop}
\begin{proof}
By induction on $n \geq 1$. The statement holds by inspection for $n=1$.
Let us assume that the statement holds up to $n - 1$. We then need to
perform a decomposition of $F_{n}$ that is parallel to the
recursive definition of $Z_{n}$.
First, $F_{n}$ is the disjoint union of $F_{n,0}$ and
$F_{n,1}$. Similarly, $Z_{n}$ is the disjoint union of $Z_{n,0}$
and $Z_{n,1}$, according to the first letter. It is therefore
enough to work separately on each part, starting with $F_{n,1}$.
Using the decomposition of $F_{n,1}$ into three parts according to
the last letter of the image by $\rho$, and the bijections stated in
\Cref{F1_F10}, \Cref{F1_F12} and \Cref{Fb_F11}, one obtains that
$\rho(F_{n,1})$ has the defining property~\eqref{intext_i} of $Z_{n,1}$.
In order to check that $\rho(F_{n,b})$ has the defining property~\eqref{intext_ii} of $Z_{n,b}$, one can use \Cref{booleen_top} and the remark
following it to check explicitly that elements of $\rho(F_{n+1,b})$ are obtained
by adding either $1$ or $2$ at the end of elements of
$\rho(F_{n,b})$.
There remains to check that $\rho(F_{n,0})$ has the defining
property~\eqref{intext_iii} of $Z_{n,0}$. This is exactly provided by \Cref{Fx_F0}.
\end{proof}
%\medskip
Words on the alphabet $\{0,1,2\}$ in $Z_n$ are considered as vectors
in $\ZZ^n$. The partial order on $Z_n$ introduced by Saneblidze is
termwise-comparison: two words $z$ and $z'$ are comparable if and only
if $z_i \leq z'_i$ for all $1 \leq i \leq n$.
One certainly expects that the map $\rho$ should give an isomorphism
from the partial order on $F_n$ to this partial order on $Z_n$. One
direction of the proof is just \Cref{cover_increase}. Completing the
proof would require a precise study of the cover relations in
both partial orders. Because this does not seem to be central enough
in the present article, this is left for another work.
As a corollary of what precedes, one can count the elements of
$F_n$ as follows. From \Cref{booleen_bot}, \Cref{booleen_top},
\Cref{F1_F10}, \Cref{F1_F12} and \Cref{Fb_F11}, one deduces the
following relations
\begin{align*}
\# F_{n,0} &= 2^{n-1},\\
\# F_{n,b} &= 2^{n-1},\\
\# F_{n,1} &= 2 \# F_{n-1,1} + \# F_{n-1,b}.
\end{align*}
which imply the following statement.
\begin{prop}
The number of elements in $F_n$ is the sequence \oeis{A045623}:
\begin{equation}
2^{n-2} (n+3) = 2,5,12,28,64,144,\dots
\end{equation}
for $n \geq 1$.
\end{prop}
\begin{rema}
Computing the Coxeter polynomials of the first few lattices in this
familly, one observes that they have all their roots on the unit
circle. This has been checked by computer up to the lattice with
$3328$ elements. For example, for the poset $F_5$ of size $64$, the
result is
$\Phi_{1}^{2} \Phi_{2}^{4} \Phi_{6}^{4} \Phi_{7} \Phi_{23}^{2}$,
where the $\Phi_d$ are the cyclotomic polynomials. One can see some
very regular patterns in these Coxeter polynomials, when expressed
as products of $[d]_x = (x^d-1)/(x-1)$ factors. This is a little
further evidence that this roots-on-the-circle phenomenon could go
on for larger cases.
\end{rema}
\section{Derived equivalences of intervals}
\label{section-derived}
We now turn briefly to a more subtle equivalence between intervals,
namely \defin{derived equivalence}, which is defined as follows. One
can consider any finite poset $P$ as a small category, with a unique
morphism $x \to y$ if and only if $x \leq y$. Then the category of
modules over $P$ with coefficients in some base field $K$ can be
defined as the category of functors from $P$ to finite-dimensional
vector spaces over $K$. This is an abelian category, with enough
projectives and injectives, and finite global dimension. One can
therefore associate to $P$ the (bounded) derived category
$\deri_{K}(P)$ of this category of modules.
Two posets $P$ and $Q$ are said to be \defin{derived equivalent} (over
$K$) if there is a triangle-equivalence between $\deri_K(P)$ and
$\deri_K(Q)$.
In this section, we conjecture the existence of derived equivalences
between some particular kinds of intervals in $\Dyck_n$.
Recall from \Cref{specific} that the intervals $J(w) = I((1,w,1,0,0))$ are the factors in
the Cartesian factorisation of the intervals $I(w)$.
\begin{conjecture}
\label{th_iso_derive}
For any $w$, the derived isomorphism type of the interval $J(w)$ only
depends on the multiset of Dyck paths in the
level-decomposition of all blocks of $w$.
\end{conjecture}
This conjecture is based on experimental evidence, namely the
coincidence of some invariants of posets (Coxeter polynomials) which
only depend on the derived categories.
Note the striking similarity of this conjecture with \Cref{th_iso}. This conjecture may even be a characterisation of
derived equivalence classes.
%\medskip
As a special case, if two words $w$ and $w'$ are related by a
permutation of their blocks, then $J(w)$ and $J(w')$ should be
derived equivalent. As the simplest possible non-trivial example, let
us consider the posets $J(1,0,1,1,0,0)$ and $J(1,1,0,0,1,0)$. Both
have $9$ elements and share the same Coxeter polynomial
$\Phi_1^2 \Phi_2 \Phi_3 \Phi_5$, where the $\Phi_d$ are the cyclotomic
polynomials. These posets are in fact related by a flip-flop in the
sense of Ladkani~\cite{flipflop} (mapping two elements near the top of
$J(1,1,0,0,1,0)$ to two elements near the bottom of $J(1,0,1,1,0,0)$),
and therefore derived equivalent.
As another special case, if two block-indecomposable words $w$ and
$w'$ are related by a permutation of their level-decomposition, then
$J(w)$ and $J(w')$ should be derived equivalent. As the simplest
possible non-trivial example, let us consider the posets
$J(1,1,0,1,1,0,0,0)$ and $J(1,1,1,0,1,0,0,0)$. Both have $27$ elements
and share the same Coxeter polynomial $\Phi_2 \Phi_4 \Phi_{18}
\Phi_{54}$. It is not clear if these intervals are derived equivalent.
To illustrate the general case in the simplest possible way, consider
the posets $J(1,0,1,1,1,0,0,0)$ and $J(1,1,0,0,1,1,0,0)$. Both have
$20$ elements and share the same Coxeter polynomial
$\Phi_1^2 \Phi_2^2 \Phi_{3} \Phi_{5} \Phi_6^2 \Phi_7$. In this case,
there is no obvious flip-flop to prove the expected derived
equivalence.
\subsection{About the notion of \texorpdfstring{$f$}{f}-vector}
Beware that this section is very speculative.
The classical notion of $f$-vector is attached to cellular or
simplicial complexes, where it records the number of cells of every
dimension.
In some famillies of posets, including the one studied here, but also
the Tamari lattices, the Cambrian lattices and many of their relatives, the pictures of the
Hasse diagram of intervals, when visually inspected by the human eye,
strongly suggest the existence of a cellular complex whose skeleton
would be the Hasse diagram.
Although we will not try to give and justify a precise definition
here, there is one way to find the $f$-vector of this putative
cell-complex, using only the partial order. Namely, every cell can be
identified with its minimal and maximal elements. These two elements
must form something like a minimal spherical interval in the poset.
There is a general phenomenon, observed in several families of posets,
that derived equivalence of posets often come together with an equality
between $f$-vectors. One important instance is the conjectured derived
equivalence between Cambrian lattices and lattices of order ideals in
root posets, as stated in~\cite{chap_cats}.
This phenomenon seems also to be present in the intervals of the dexter
lattices, at least in the intervals $J(w)$. One expects that derived
equivalent $J(w)$ will share the same $f$-vector, but not conversely.
\section{Miscellany}
\label{misc}
This section collects various results and conjectures on the dexter
posets $\Dyck_n$.
\subsection{A symmetry of colored \texorpdfstring{$h$}{h}-polynomials}
\label{hpoly}
One can color the edges of the Hasse diagram of $\Dyck_n$ with two
colors as follows. When an edge corresponds to sliding a subpath to
its highest possible position, this edge is colored red. Other
edges are colored blue. For example, see \Cref{fig_dyck4} where blue
edges are also dashed.
As we will see, this coloring is interesting because the generating
polynomial of incoming edges according to their colors has an
unexpected symmetry.
As a warm-up, let us start with the simpler generating series of incoming edges, not taking colors into account:
\begin{equation}
A = \sum_{n \geq 0} \sum_{w \in \Dyck_n} x^{C(w)} t^n,
\end{equation}
where $C(w)$ is the number of elements covered by $w$.
Using the unique decomposition of Dyck paths into a list of blocks and \Cref{facto_tous}, one gets
\begin{equation}
\label{eq_h_A}
A = \frac{1}{1-B},
\end{equation}
where $B$ is the similar sum restricted to block-indecomposable Dyck paths.
Then using the level-decomposition of block-indecomposables
(\Cref{level_decomposition}) and \Cref{th_level_iso}, one gets
\begin{equation}
\label{eq_h_B}
B = \frac{t}{1-x t A}.
\end{equation}
Indeed, the elements covered by $w = \level(w_1,\dots,w_k)$ either
come from replacing $w_i$ by some element that it covers, or from
sliding down a subpath of $w$ that ends somewhere in the final sequence of
letters $0$ in $w$. There are exactly $k$ such additional covered elements.
Together~\eqref{eq_h_A} and~\eqref{eq_h_B} imply an equation for $A$
which is exactly the well-known equation for the generating series of
Narayana polynomials (\oeis{A1263}). Note that the Narayana
polynomials are the $h$-vectors of the associahedra, namely the
results of the same counting of incoming edges for the Hasse diagram
of the Tamari lattices. This hints at a possible cellular structure of
the Hasse diagram of $\Dyck_n$, with the same $f$-vector as the
associahedron. This is left for a future study.
Let us now introduce a refined colored version of $A$:
\begin{equation}
A = A(r, b, t) = \sum_{n \geq 0} \sum_{w \in \Dyck_n} r^{C_r(w)} b^{C_b(w)} t^n,
\end{equation}
and the associated series $B$ restricted to
block-indecomposables. Here $C_r(w)$ and $C_b(w)$ count the red and blue
incoming edges at $w$.
The first equation~\eqref{eq_h_A} holds unchanged, whereas~\eqref{eq_h_B} must be slightly modified into
\begin{equation}
B = \frac{t}{1-t(r+b(A-1))}.
\end{equation}
Indeed, the $k$ elements covered by $w = \level(w_1,\dots,w_k)$ that do
not come from an element covered by some $w_i$ can be either red or
blue. They are red exactly when $w_i$ is the empty Dyck path.
By elimination of $B$, one finds that $A$ satisfies the quadratic equation
\begin{equation}
A^{2} t b + A t r - 2 A t b + A t - t r + t b - A + 1 = 0,
\end{equation}
from which one can deduce the global symmetry
\begin{equation}
A - 1 = (A(1/r,b/r^2,r t) - 1)/r.
\end{equation}
This symmetry property can be stated as a simple
symmetry of the coefficient $A_n$ of $t^n$ in $A$:
\begin{equation}
\forall n \geq 1 \quad A_n(r, r b) = r^{n-1} A_n(1/r, b/r).
\end{equation}
The real meaning of this last symmetry is not clear for the moment. It
extends the usual symmetry of Narayana numbers.
\subsection{\texorpdfstring{$m$}{m}-analogues}
One can easily define the same kind of dexter variation for the $m$-Tamari
lattices~\cite{bpr, mbmpr} instead of the Tamari lattices, using their similar
description by sliding subpaths in Dyck paths of slope $m$. These
posets do not seem to be very interesting, at least because their
numbers of intervals involve large prime numbers. For example, the
first few numbers of intervals for $m=2$ are given by
\begin{equation}
1, 1, 5, 36, 311, 3001, 31203.
\end{equation}
\subsection{Zeta polynomials and chains}
Let us now give a few simple experimental observations related to
chains and zeta polynomials in $\Dyck_n$. We have not tried to prove them.
The length of the longest chain in $\Dyck_n$ seems to be
$\lfloor n^2/4 \rfloor +1 $ (\oeis{A33638}), realized between $\wmin$
and Dyck paths that end with as many final repetitions of $(1,0,0)$ as
possible.
The first few values at $-1$ of the zeta polynomials of $\Dyck_n$ for
$n \geq 1$ are
\begin{equation}
1, -1, 2, -5, 14, -42, 132, -429.
\end{equation}
One could guess that these should be (up to sign) the Catalan numbers.
The first few values at $-2$ of the zeta polynomials of $\Dyck_n$ for
$n \geq 1$ are
\begin{equation}
1, -2, 7, -29, 131, -625, 3099, -15818.
\end{equation}
This coincides (up to sign) with the beginning of sequence
\oeis{A007852} that is counting antichains in rooted plane trees on
$n$ nodes.
\appendix
\section{About the Tamari lattices}
\label{tamari}
Let us recall that the Tamari lattice~\cite{tamari_friedman} of size
$n$ can be defined on the set of Dyck paths of size $n$ as the partial
order induced by transitive closure of some cover relations, namely
the exchange in any Dyck path of a letter $0$ (assumed to be followed
by $1$) with the subpath following it. This cover relation is equivalent
to sliding this subpath by one step in the north-west direction. This
description is related in~\cite[\S 2]{berbon} to the more classical
description using rotation on binary trees.
For a Dyck path $w \in \Dyck_n$, let the \defin{height sequence} of $w$
be $(h_1,h_2,\dots,h_n)$ where $h_i$ is the height in $w$ just after
the $i^{th}$ letter $1$. Note that repeated sliding to the north-west
of a given subpath $x$ always increase the same subsequence of the
height sequence.
\begin{lemma}
\label{tamari_chain}
Let $w$ be a Dyck path. Let $w'$ be obtained from $w$ by sliding
once or several times the same subpath $x$ in the north-west
direction. Then the interval $[w,w']$ in the Tamari lattice is a
chain, in other words a total order, and all elements of $[w,w']$ are
obtained from $w$ by sliding the subpath $x$.
\end{lemma}
\begin{proof}
Only two kinds of Tamari cover relations can happen: either the subpath
$x$ itself is slid, or another subpath $y$ is slid.
Assume first that the latter happens, where $y$ is not contained in $x$. In
that case, at least one element $h_i$ of the height sequence gets
increased, that is not in the subsequence modified when sliding $x$.
Because the height sequence can never decrease, this element $h_i$ is
still larger in $w'$ than it was in $w$, which is absurd.
One can therefore assume that $y$ is contained in $x$. But sliding
$x$ commutes with sliding such $y$.
Let us pick an arbitrary chain of Tamari cover relations from $w$ to
$w'$. By the commuting relation just explained, one can assume that
all slidings of $x$ happen first in this chain.
But then after performing these initial slidings of $x$, the first
step of $x$ must have attained the position it will have in $w'$. So
in fact at this point, the top element $w'$ has been reached
already. Therefore our original chain only contains slidings of $x$.
So the full interval $[w,w']$ is just made of a sequence of slidings of $x$.
\end{proof}
\longthanks{The author would like to thank the referees for their careful work, that helped a lot to enhance this article.}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Chapoton_241}
\end{document}