\documentclass[revision]{FPSAC2019}

\articlenumber{36}
\addbibresource{36.bib}

\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{color}
\usepackage{todonotes}
\usepackage{subcaption}
\usepackage{tikz,pgf}
	\pgfdeclarelayer{background}
	\pgfsetlayers{background,main}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\ie}{i.e.\;}
\newcommand{\defs}{\stackrel{\mathrm{def}}{=}}
\newcommand{\tdef}[1]{\smash{\textcolor{blue}{\emph{#1}}}}
\newcommand{\nc}{N\!C}
\newcommand{\nn}{N\!N}
\newcommand{\Symmetric}{\mathfrak{S}}
\newcommand{\Tamari}{\mathcal{T}}
\newcommand{\Paths}{\mathcal{P}}
\newcommand{\Dyck}{\mathcal{D}}
\newcommand{\DyckBounce}{\Dyck^{\mathrm{bounce}}}
\newcommand{\DyckSteep}{\mathcal{D}^{\mathrm{steep}}}
\newcommand{\Comp}{\mathrm{Comp}}
\newcommand{\Trees}{\mathbb{T}}
\newcommand{\LAC}{\mathrm{LAC}}
\newcommand{\SteepPairs}{\mathcal{SP}} % set of steep pairs
\newcommand{\BouncePairs}{\mathcal{BP}} % set of bounce pairs
\newcommand{\inv}{\mathrm{Inv}}
\newcommand{\horiz}{\mathrm{horiz}}
\newcommand{\nested}{\times_{\mathrm{nested}}}
\newcommand{\bij}{\Xi}
\newcommand{\invbij}{\Lambda}
\newcommand{\lactoperm}{\bij_{\mathrm{perm}}}
\newcommand{\lactodyck}{\bij_{\mathrm{dyck}}}
\newcommand{\lactonc}{\bij_{\mathrm{nc}}}
\newcommand{\lactonn}{\bij_{\mathrm{nn}}}
\newcommand{\permtolac}{\invbij_{\mathrm{perm}}}
\newcommand{\dycktolac}{\invbij_{\mathrm{dyck}}}
\newcommand{\nctolac}{\invbij_{\mathrm{nc}}}
\newcommand{\nntolac}{\invbij_{\mathrm{nn}}}
\newcommand{\lactosteep}{\bij_{\mathrm{steep}}}
\newcommand{\steeptolac}{\invbij_{\mathrm{steep}}}
\newcommand{\lactobounce}{\bij_{\mathrm{bounce}}}
\newcommand{\bouncetolac}{\invbij_{\mathrm{bounce}}}
\newcommand{\steeppairtobouncepair}{\Gamma}

\title{The Steep-Bounce Zeta Map in Parabolic Cataland}

\author{Cesar Ceballos\thanks{Supported by the Austrian Science Foundation FWF, grant F 5008-N15.}\addressmark{1}, 
Wenjie Fang\thanks{Supported by the Austrian Science Foundation FWF, grant P27290.}\addressmark{2}, \and
Henri M{\"u}hle\addressmark{3}}

\address{\addressmark{1}Faculty of Mathematics, University of Vienna \\ \addressmark{2}Institute of Discrete Mathematics, Graz University of Technology\\ \addressmark{3}Institute of Algebra, Dresden University of Technology}

\received{\today}

\abstract{As a classical object, the Tamari lattice has many generalizations, including $\nu$-Tamari lattices and parabolic Tamari lattices. In this article, we unify these generalizations in a bijective fashion. We first prove that parabolic Tamari lattices are isomorphic to $\nu$-Tamari lattices for bounce paths $\nu$. We then introduce a new combinatorial object called ``left-aligned colorable tree'', and show that it provides a bijective bridge between various parabolic Catalan objects and certain nested pairs of Dyck paths. As a consequence, we prove the Steep-Bounce Conjecture using a generalization of the famous zeta map in $q,t$-Catalan combinatorics.}   

\resumetitle{R{\'e}sum{\'e}}

\resume{\'Etant un objet classique, le treillis de Tamari a beaucoup de g\'en\'eralisations, y compris les treillis $\nu$-Tamari et les treillis de Tamari paraboliques. Dans cet article, ces deux treillis sont unifi\'es de mani\`ere bijective. D'abord nous prouvons que les treillis de Tamari paraboliques sont isomorphes aux treillis de $\nu$-Tamari avec $\nu$ des chemins de rebond. Puis nous introduisons un nouvel objet dit ``arbre colorable à gauche'', et montrons qu'il donne un pont bijectif entre divers objets de Catalan paraboliques et certains paires de chemins de Dyck embo\^it\'ees. En cons{\'e}quence, nous prouvons la Conjecture de Steep-Bounce par une g{\'e}n{\'e}ralisation de la fameuse transformation zeta dans la combinatoire de $q,t$-Catalan.}

\keywords{parabolic Tamari lattice, $\nu$-Tamari lattice, bijection, left-aligned colorable tree, zeta map.}

%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{literature.bib}

\begin{document}

\maketitle

\definecolor{c1}{HTML}{FF9999}
\definecolor{c2}{HTML}{FFD27F}
\definecolor{c3}{HTML}{99C199}
\definecolor{c4}{HTML}{9999FF}
\definecolor{c5}{HTML}{99D1D1}
\definecolor{c6}{HTML}{D9A6F9}

\newcommand{\ncA}[1]{
	\includegraphics[scale=#1,page=1]{fig/figures-std.pdf}
}

\newcommand{\permA}[1]{
	\includegraphics[scale=#1,page=2]{fig/figures-std.pdf}
}

\newcommand{\pathA}[2]{
	\ifthenelse{\equal{#2}{1}}
	{
		\includegraphics[scale=#1,page=4]{fig/figures-std.pdf}
	}{
		\includegraphics[scale=#1,page=3]{fig/figures-std.pdf}
	}
}

\newcommand{\ncB}[1]{
	\includegraphics[scale=#1,page=5]{fig/figures-std.pdf}
}

\newcommand{\permB}[1]{
	\includegraphics[scale=#1,page=6]{fig/figures-std.pdf}
}

\newcommand{\pathB}[2]{
	\ifthenelse{\equal{#2}{1}}
	{
		\includegraphics[scale=#1,page=8]{fig/figures-std.pdf}
	}{
		\includegraphics[scale=#1,page=7]{fig/figures-std.pdf}
	}
}

\newcommand{\pathBReversed}[1]{
	\includegraphics[scale=#1,page=9]{fig/figures-std.pdf}
}

\newcommand{\paraTam}[1]{
	\includegraphics[width=#1,page=11]{fig/figures-std.pdf}
}

\newcommand{\nuTam}[1]{
	\includegraphics[width=#1,page=12]{fig/figures-std.pdf}
}

\newcommand{\lactreeB}[1]{
	\includegraphics[scale=#1, page=4]{fig/ipe-fig.pdf}
}

\newcommand{\lactreeBdot}[1]{
	\includegraphics[scale=#1, page=5]{fig/ipe-fig.pdf}
}

\newcommand{\treepostfix}[1]{
	\includegraphics[scale=#1, page=6]{fig/ipe-fig.pdf}
}

\newcommand{\markeddyck}[1]{
	\includegraphics[scale=#1, page=7]{fig/ipe-fig.pdf}
}

\newcommand{\quadrantwalk}[1]{
	\includegraphics[scale=#1, page=8]{fig/ipe-fig.pdf}
}

\newcommand{\steeppair}[1]{
	\includegraphics[scale=#1, page=9]{fig/ipe-fig.pdf}
}

\newcommand{\lactreeBnc}[1]{
	\includegraphics[scale=#1, page=10]{fig/ipe-fig.pdf}
}


%!TEX root = ./main_file.tex

\section{Introduction}


The Tamari lattice can be realized as a partial order on various Catalan objects.  It has been studied widely from various perspectives, leading to numerous generalizations. Two of its recent variants are the parabolic Tamari lattices of M\"uhle and Williams~\cite{muehle18tamari} and the $\nu$-Tamari lattices of Pr{\'e}ville-Ratelle and Viennot~\cite{preville17enumeration}. The parabolic Tamari lattices are defined as certain lattice quotients of the weak order in parabolic quotients of the symmetric group $\Symmetric_n$, which generalizes a construction in the classical Tamari lattice by Bj{\"o}rner--Wachs~\cite{bjorner97shellable}. The $\nu$-Tamari lattices are, in contrast, partial orders defined by manipulating lattice paths. They generalize the $m$-Tamari lattices which were initially motivated by connections to trivariate diagonal harmonics~\cite{BergeronPrevilleRatelle}, and now have remarkable applications to the theory of multivariate diagonal harmonics~\cite{ceballos_hopf_2018} and bijective links to other objects in combinatorics \cite{fpr17nonsep}. 

\medskip

In this article, we reunite these two variants of the Tamari lattice. Our first main result is that parabolic Tamari lattices are isomorphic to $\nu$-Tamari lattices indexed by bounce paths~$\nu$. We also introduce a new family of parabolic Catalan objects called \emph{left-aligned colorable trees} (or simply \emph{$\LAC$ trees}). These trees connect the parabolic generalizations of 231-avoiding permutations, noncrossing set partitions, and Dyck paths, all of which can be recovered easily from the tree. In turn, we use $\LAC$ trees to prove the Steep-Bounce Conjecture of Bergeron, Ceballos, and Pilaud~\cite[Conjecture~2.2.8]{ceballos_hopf_2018}, which connects the graded dimensions of a certain Hopf algebra of pipe dreams to a certain family of lattice walks in the positive quarter plane. Our proof is based on a bijection between two families of nested Dyck paths via $\LAC$ trees. Interestingly, we show that this bijection generalizes the famous zeta map in $q,t$-Catalan combinatorics~\cite[Proof of Theorem~3.15]{Haglund-qt-catalan}.

We have omitted many of the proofs due to space limitations.  The missing details can be found in the full version \cite{full-version} of this article.

\begin{figure}
	\centering
	\begin{tikzpicture}\small
		\def\dx{5.5};
		\def\dy{3};
		%%
		\draw(1*\dx,2.9*\dy) node(perm){\permB{1.1}};
		\draw(2*\dx,3.2*\dy) node(nc){\ncB{1.1}};
		\draw(0.7*\dx,2*\dy) node(bounce)[outer sep=-1.2cm]{\pathBReversed{0.95}};
		\draw(1.8*\dx,2*\dy) node(tree){\lactreeB{0.8}};
		\draw(3*\dx,2.78*\dy) node(walk){\markeddyck{0.8}};
		\draw(3*\dx,2*\dy) node(steep){\steeppair{0.8}};
		%%
		\draw[-latex](tree) -- (perm) node[right,midway] {\footnotesize $\lactoperm$};
		\draw[-latex](tree) -- (nc) node[right,midway] {\footnotesize $\lactonc$};
		\draw[-latex](tree) -- (bounce) node[above,midway] {\footnotesize $\lactobounce$};
		\draw[-latex](tree) -- (walk) node[above,midway] {\footnotesize $\lactodyck$};
		\draw[-latex](tree) -- (steep) node[above,midway] {\footnotesize $\lactosteep$};
	\end{tikzpicture}
	\caption{An overview of the bijections presented in this article.}
	\label{fig:big_picture}
\end{figure}


%!TEX root = ./main_file.tex

\section{Two Generalizations of the Tamari Lattice}
	\label{sec:tamari_lattices}
The \tdef{(classical) Tamari lattice} $\Tamari_{n}$ was introduced in \cite{tamari62algebra} as a partial order on parenthesizations of a string of length $n+1$, and has since then gained lots of interest in mathematical research.  See \cite{hoissen12associahedra} for a recent survey on topics related to these lattices. We recall two generalizations of this lattice, both depending on a composition $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{r})$ of $n>0$.

Let $[n]\defs\{1,2,\ldots,n\}$. For $i\in\{0,1,\ldots,r\}$, let $s_{i}\defs\alpha_{1}+\alpha_{2}+\cdots+\alpha_{i}$ and $t_{i}\defs n-s_{r-i}$ with $s_0\defs 0$.  For $i\in[r]$ we call the set $\{s_{i-1}+1,s_{i-1}+2,\ldots,s_{i}\}$ the $i$-th \tdef{$\alpha$-region}.  Let $\overline{\alpha}\defs(\alpha_{r},\ldots,\alpha_{2},\alpha_{1})$ denote the \tdef{reverse composition}.

\subsection{Parabolic Tamari Lattices}
	\label{sec:parabolic_tamari}
\paragraph{Parabolic $231$-Avoiding Permutations.}
	\label{sec:parabolic_231}
Let $\Symmetric_{n}$ be the symmetric group of degree~$n$. Its \tdef{parabolic quotient} with respect to $\alpha$ is defined by
\begin{displaymath}
	\Symmetric_{\alpha} \defs \bigl\{w\in\Symmetric_{n}\mid w(k)<w(k+1)\;\text{for}\;k\notin\{s_{1},s_{2},\ldots,s_{r-1}\}\bigr\}.
\end{displaymath}
In a permutation $w\in\Symmetric_{\alpha}$, an \tdef{$(\alpha,231)$-pattern} is a triple of indices $i<j<k$ in different $\alpha$-regions such that $w(k)<w(i)<w(j)$ and $w(i)=w(k)+1$. A permutation $w\in\Symmetric_{\alpha}$ without $(\alpha,231)$-patterns is \tdef{$(\alpha,231)$-avoiding}.  We denote by $\Symmetric_{\alpha}(231)$ the set of all $(\alpha,231)$-avoiding permutations in $\Symmetric_{\alpha}$. An example for $\alpha=(1,3,1,2,4,3)$ is shown in top-left of \cref{fig:big_picture}. In this article, we represent permutations in their one-line notation, and highlight the $\alpha$-regions with colors.

\paragraph{The Weak Order on $\Symmetric_{\alpha}(231)$.}
	\label{sec:parabolic_weak_order}

\begin{figure}
	\centering
	\begin{subfigure}[t]{.49\textwidth}
		\paraTam{\textwidth}
		\caption{The parabolic Tamari lattice $\Tamari_{(1,2,2)}$.}
		\label{fig:parabolic_tamari_5_122}
	\end{subfigure}
	\hspace*{.1cm}
	\begin{subfigure}[t]{.49\textwidth}
		\nuTam{\textwidth}
		\caption{The $\nu_{(1,2,2)}$-Tamari lattice.}
		\label{fig:nu_tamari_5_122}
	\end{subfigure}
	\caption{The lattices $\Tamari_{\alpha}$ and $\Tamari_{\nu_{\alpha}}$ for $\alpha=(1,2,2)$.}
	\label{fig:parabolic_5_122}
\end{figure}
	
For every $w\in\Symmetric_{\alpha}$, we define its \tdef{inversion set} as $\inv(w) \defs \bigl\{(i,j)\mid i<j\;\text{and}\;w(i)>w(j)\bigr\}$. The elements of $\inv(w)$ are the \tdef{inversions} of $w$. The \tdef{(left) weak order} $(\Symmetric_{\alpha}, \leq_{L})$ is defined as $w_{1}\leq_{L}w_{2}$ if and only if $\inv(w_{1})\subseteq\inv(w_{2})$.  Its restriction $\Tamari_{\alpha}\defs\bigl(\Symmetric_{\alpha}(231),\leq_{L}\bigr)$ is the \tdef{parabolic Tamari lattice}. It was established in \cite[Theorem~1.1]{muehle18tamari} that $\Tamari_{\alpha}$ is indeed a lattice.  \cref{fig:parabolic_tamari_5_122} shows the lattice $\Tamari_{(1,2,2)}$.  It follows for instance from \cite[Theorem~9.6]{bjorner97shellable} that $\Tamari_{(1,1,\ldots,1)}\cong\Tamari_{n}$.

\subsection{$\nu_{\alpha}$-Tamari Lattices}
	\label{sec:nu_tamari}
\paragraph{Dyck Paths.}
	\label{sec:north_east_paths}
A \tdef{Dyck path} is a lattice path in $\mathbb{N}^{2}$ starting from the origin, composed of steps $E\defs(1,0)$ (or \tdef{east-steps}) and $N\defs(0,1)$ (or \tdef{north-steps}), ending on the main diagonal while always staying weakly above it.  Such paths can also be regarded as words in the letters $N$ and $E$.  Let $\Dyck_{n}$ denote the set of all Dyck paths with $2n$ steps. %For a Dyck path $\nu$ we derive the path $\overline{\nu}$ by reversing $\nu$ and exchanging east- and north-steps.

A Dyck path that is of the form $N^{i_{1}}E^{i_{1}}N^{i_{2}}E^{i_{2}}\ldots N^{i_{r}}E^{i_{r}}$, for some integers $i_{1},i_{2},\ldots,i_{r}$, is \tdef{bounce} (because it ``bounces off'' the main diagonal $s-1$ times).  A Dyck path is \tdef{steep} if it has no consecutive east-steps except possibly at $y$-coordinate $n$.  

The \tdef{$\alpha$-bounce path} is $\nu_{\alpha} \defs N^{\alpha_{1}}E^{\alpha_{1}}N^{\alpha_{2}}E^{\alpha_2}\ldots N^{\alpha_{r}}E^{\alpha_{r}}$.  Any Dyck path with $2n$ steps that stays weakly above $\nu_{\alpha}$ is an \tdef{$\alpha$-path}, and we denote by $\Dyck_{\alpha}$ the set of $\alpha$-paths.

\paragraph{The Rotation Order on Dyck Paths.}
	\label{sec:rotation_order}
Given an $\alpha$-path $\mu$ and any lattice point $\vec{p}$ on $\mu$, we define $\horiz_{\alpha}(\vec{p})$ as the maximal number of east-steps that can be taken from $\vec{p}$ without going to the other side of $\nu_{\alpha}$.  A \tdef{valley} of $\mu$ is a lattice point $\vec{p}$ preceded by an east-step and followed by a north-step.  For any valley $\vec{p}$ of $\mu$, let $\vec{q}$ be the first lattice point on $\mu$ after $\vec{p}$ such that $\horiz_{\alpha}(\vec{p})=\horiz_{\alpha}(\vec{q})$, and let $\mu[\vec{p},\vec{q}]$ be the subpath of $\mu$ from $\vec{p}$ to $\vec{q}$. By swapping $\mu[\vec{p},\vec{q}]$ with the east-step preceding $\vec{p}$, we obtain another $\alpha$-path $\mu'$, and we define the relation $\lessdot_{\alpha}$ by taking $\mu\lessdot_{\alpha}\mu'$ for all possible $\mu$ and $\mu'$ obtained in such a way.  Let $\leq_{\alpha}$ be the reflexive and transitive closure of the relation $\lessdot_{\alpha}$. The poset $\Tamari_{\nu_{\alpha}}\defs\bigl(\Dyck_{\alpha},\leq_{\alpha}\bigr)$ is the \tdef{$\nu_{\alpha}$-Tamari lattice}.  It was established in~\cite[Theorem~1]{preville17enumeration} that $\Tamari_{\nu_{\alpha}}$ is indeed a lattice, and \cref{fig:nu_tamari_5_122} shows an example $\Tamari_{\nu_{(1,2,2)}}$.  It is well known that $\Tamari_{(NE)^{n}}\cong\Tamari_{n}$, the classical Tamari lattice of order $n$.

\subsection{The Lattices $\Tamari_{\nu_{\alpha}}$ and $\Tamari_{\alpha}$ are Isomorphic}
	\label{sec:tamari_isomorphism}
We now prove that the two lattices $\Tamari_{\nu_{\alpha}}$ and $\Tamari_{\alpha}$ are isomorphic. For this we use a bijection between the sets $\Symmetric_{\alpha}(231)$ and $\Dyck_{\alpha}$ already described in~\cite[Theorem~1.2]{muehle18tamari}. To that end we need another family of objects that depends on the composition $\alpha$.

\paragraph{Parabolic Noncrossing Partitions.}
	\label{sec:parabolic_nc}
An \tdef{$\alpha$-partition} is a set partition of $[n]$ where every part intersects an $\alpha$-region in at most one element.  We represent an $\alpha$-partition by its \tdef{diagram}, which consists of $n$ vertices labeled from $1$ through $n$ on a horizontal line, grouped by $\alpha$-regions.  Any two consecutive elements $a$ and $b$ in a part of an $\alpha$-partition are connected by a \tdef{bump}.  More precisely, the bump connecting $a$ and $b$ is a curve that leaves the vertex labeled $a$ at the bottom, stays below every vertex in the same $\alpha$-region as $a$, then moves up and continues above every vertex in the subsequent $\alpha$-regions until it reaches the vertex labeled $b$, which it enters at the top.  An $\alpha$-partition is \tdef{noncrossing} if it admits a diagram without bumps crossing.  A more formal definition can be found in~\cite[Definition~4.1]{muehle18tamari}. An example for $\alpha=(1,3,1,2,4,3)$ is the $\alpha$-partition $\bigl\{\{1,3\},\{2,6\},\{4,9,12\},\{5\},\{7,8\},\{10,14\},\{11\},\{13\}\bigr\}$ shown in the top-central part of \cref{fig:big_picture}. We denote by $\nc_{\alpha}$ the set of all noncrossing $\alpha$-partitions.

\paragraph{A Bijection from $\Dyck_{\overline{\alpha}}$ to $\Symmetric_{\alpha}(231)$.}
	\label{sec:tamari_bijection}
We first define a map $\Theta_{1}\colon\Dyck_{\overline{\alpha}}\to\nc_{\alpha}$.  Let $\mu\in\Dyck_{\overline{\alpha}}$.  Starting from the $\alpha$-partition $\mathbf{P}_{0}$ without any bumps, we consider all valleys of $\mu$ and inductively add bumps to $\mathbf{P}_{0}$ \emph{from right to left} for each valley of $\mu$. Let the coordinates of the valleys of $\mu$ be $(p_1,q_1),(p_2,q_2),\dots (p_m,q_m)$, and $\mathbf{P}_{i}$ the noncrossing $\alpha$-partition after dealing with the $i$ first valleys.  There is a unique index $0 \leq k < r$ with such that $t_{k}\leq q_{i+1}<t_{k+1}$, meaning that $q_{i+1}=t_{k}+\ell$ for some $0\leq \ell<t_{k+1}-t_{k}$.  To go from $\mathbf{P}_{i}$ to $\mathbf{P}_{i+1}$, we add a bump from $a$ to $b$, where $a$ is the $(\ell+1)$-st element in the $(r-k)$-th $\alpha$-region and $b$ is the $(p_{i+1}-p_i)$-th element after the $(r-k)$-th $\alpha$-region that is not already below any other bump. We define $\Theta_{1}(\mu) = \mathbf{P}_{m}$. It was proven in~\cite[Theorem~5.2]{muehle18tamari} that the $\alpha$-partition $\Theta_{1}(\mu)$ is indeed noncrossing and that $\Theta_{1}$ is a bijection. Two examples are illustrated in the top part of \cref{fig:cover_map}.

\medskip

Now we describe another map $\Theta_{2}\colon\nc_{\alpha}\to\Symmetric_{\alpha}(231)$.  Let $\mathbf{P}\in\nc_{\alpha}$, and $\bar{P}$ the unique part of $\mathbf{P}$ containing $1$. Suppose that $\bar{P}=\{i_{1},i_{2},\ldots,i_{k}\}$ with $i_{1}=1$.  The permutation $w=\Theta_{2}(\mathbf{P})$ is the permutation satisfying $w(i_{1})=w(i_{2})+1=\cdots=w(i_{k})+k-1$ with as few inversions as possible. To get $w$, we set $w(i_{1})$ to be the size of a set $\bar{Q}$ whose elements are vertices lying below either the bumps in $\bar{P}$, or any bump starting in the same $\alpha$-region but to the left of some element in $\bar{Q}$ (including end points in both cases).  See \cite[Section~1.2.2]{full-version} for a detailed explanation including an example.  The remaining values of $w$ are determined inductively by viewing $\mathbf{P}\setminus\bar{P}$ as an element of $\nc_{\alpha'}$ for some appropriate composition $\alpha'$ of $n'<n$.  It was proven in~\cite[Theorem~4.2]{muehle18tamari} that the permutation $w=\Theta_{2}(\mathbf{P})$ is indeed $(\alpha,231)$-avoiding and that $\Theta_{2}$ is a bijection. Two examples are illustrated in the lower part of \cref{fig:cover_map}.

We now prove that the map $\Theta\defs\Theta_{2}\circ\Theta_{1}$ induces an isomorphism from $\Tamari_{\nu_{\alpha}}$ to $\Tamari_{\alpha}$.  %Since $\Tamari_{\overline\nu_{\alpha}}$ is the dual of $\Tamari_{\nu_{\alpha}}$ \cite[Theorem~2]{preville17enumeration}, the lattice $\Tamari_{\nu_{\alpha}}$ is isomorphic to $\Tamari_{n}^{\alpha}$.

\begin{theorem}\label{thm:parabolic_nu_tamari_isomorphism}
	For every integer composition $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{r})$, the parabolic Tamari lattice $\Tamari_{\alpha}$ is isomorphic to the $\nu_{\alpha}$-Tamari lattice $\Tamari_{\nu_{\alpha}}$.
\end{theorem}
\begin{proof}[Proof sketch]
	Due to the space limit, we will only present the proof strategy; the details can be found in \cite[Section~2.3]{full-version}.
	
	We use the fact that both $\Tamari_{\alpha}$ and $\Tamari_{\nu_{\alpha}}$ are extremal lattices in the sense of \cite{markowsky92primes}; see \cite[Theorem~1.3]{muehle18noncrossing}, and \cite[Theorem~22]{markowsky92primes} in conjunction with \cite[Theorem~3]{preville17enumeration}, respectively.  Every extremal lattice is represented uniquely by its \tdef{Galois graph}~\cite[Theorem~1]{markowsky92primes}. The Galois graph of $\Tamari_{\alpha}$ was given in \cite[Theorem~1.8]{muehle18noncrossing}.  We then explicitly describe the Galois graph of the dual of $\Tamari_{\nu_{\overline{\alpha}}}$, and show that $\Theta$ induces an isomorphism of these two Galois graphs.  Since by \cite[Theorem~2]{preville17enumeration} $\Tamari_{\nu_{\alpha}}$ is isomorphic to the dual of $\Tamari_{\nu_{\overline{\alpha}}}$, we conclude that $\Tamari_{\alpha}$ and $\Tamari_{\nu_{\alpha}}$ are isomorphic.
\end{proof}

\begin{figure}
	\centering
	\begin{tikzpicture}\small
		\def\dx{8.5};
		\def\dy{1.75};
		%%
		\draw(1*\dx,1.3*\dy) node{\permA{1.2}};
		\draw(1*\dx,2*\dy) node{\ncA{1.2}};
		\draw(1*\dx,3.3*\dy) node{\pathA{1.1}{0}};

		\draw(1.5*\dx,1.3*\dy) node{$\gtrdot_{L}$};
		\draw(1.5*\dx,3.3*\dy) node{$\lessdot_{\overline{\alpha}}$};

		\draw(2*\dx,1.3*\dy) node{\permB{1.2}};
		\draw(2*\dx,2*\dy) node{\ncB{1.2}};
		\draw(2*\dx,3.3*\dy) node{\pathB{1.1}{0}};
		
		\draw(1*\dx,2.3*\dy) node{$\downarrow\Theta_{1}$};
		\draw(2*\dx,2.3*\dy) node{$\downarrow\Theta_{1}$};
		\draw(1*\dx,1.6*\dy) node{$\downarrow\Theta_{2}$};
		\draw(2*\dx,1.6*\dy) node{$\downarrow\Theta_{2}$};
	\end{tikzpicture}
	\caption{A cover relation in $\Tamari_{\alpha}$ and the corresponding cover relation in $\Tamari_{\nu_{\overline{\alpha}}}$ for $\alpha=(1,3,1,2,4,3)$.}
	\label{fig:cover_map}
\end{figure}

In fact, we suspect that $\Theta$ is an anti-isomorphism from $\Tamari_{\nu_{\overline{\alpha}}}$ to $\Tamari_{\alpha}$.  \cref{fig:cover_map} illustrates this suspicion by showing an example of a cover relation in $\Tamari_{\nu_{\overline{\alpha}}}$ that is mapped under $\Theta$ to a dual cover relation in $\Tamari_{\alpha}$ for $\alpha=(1,3,1,2,4,3)$.  %Unlike $231$-avoiding permutations, simply removing the descent in the permutation on the left of Figure~\ref{fig:cover_map} produces a permutation which has an $(\alpha,231)$-pattern.  We must therefore remove another descent to obtain the lower cover of this permutation in $\Tamari_{n}^{\alpha}$.

\cref{thm:parabolic_nu_tamari_isomorphism} states that $\Tamari_{\alpha}$ and $\Tamari_{\nu_{\alpha}}$ are isomorphic lattices.  We want to point out that these two lattices provide two different perspectives.  By definition of $\Tamari_{\nu_{\alpha}}$ it is simple to check when two $\alpha$-Dyck paths form a cover relation, but it is not easy (in general) to check whether two such paths are comparable in this lattice.  In $\Tamari_{\alpha}$, the situation is quite the opposite: by definition it is easy to check when two $(\alpha,231)$-avoiding permutations are comparable in $\Tamari_{\alpha}$, but to determine whether they form a cover relation is nontrivial.


%!TEX root = ./main_file.tex
\section{LAC Trees and Parabolic Catalan Objects}
	\label{sec:lac_trees_parabolic_catalan}
In this section, which is at the heart of this abstract, we introduce a new family of combinatorial objects depending on a fixed composition $\alpha$.  These objects, called \emph{$\alpha$-trees}, are plane rooted trees that can be colored by the algorithm that we now describe.

Let $\alpha=(\alpha_1, \alpha_2, \ldots, \alpha_r)$ be a composition of $n$. Given a plane rooted tree $T$ with $n$ non-root vertices, our goal is to color nodes in $T$ with $r$ colors. The algorithm consists of $r$ coloring steps, and in the $i$-th step we try to color $\alpha_{i}$ non-root nodes of $T$ with color $i$. During a coloring step, a non-root node is \tdef{active} if it is not yet colored, and its parent is either the root or is colored. At the $i$-th coloring step, the first~$\alpha_i$ active vertices in the left-to-right traversal order on $T$ are colored by $i$. After each coloring, we update the status of being active accordingly.  If there are less than $\alpha_i$ active vertices at step $i$, the algorithm fails. When it succeeds, we obtain the \tdef{left-aligned coloring} of $T$ by $\alpha$ (\tdef{$\LAC$} for short), which is unique (since this algorithm is deterministic).  In this case, we say that $T$ and $\alpha$ are \tdef{left-aligned compatible} (or simply \tdef{compatible}).  Any plane rooted tree that is compatible with $\alpha$ is an \tdef{$\alpha$-tree}.  We denote the set of all $\alpha$-trees by $\Trees_{\alpha}$.  An example for $\alpha=(1,3,1,2,4,3)$ is shown in the center of \cref{fig:big_picture}.

\begin{figure}
  \centering
  \includegraphics[page=1,width=0.8\textwidth]{fig/ipe-fig.pdf}
  \caption{An illustration of the map $\lactoperm$ for $\alpha=(1,3,1,2,4,3)$.}
  \label{fig:tree-perm-bij}
\end{figure}

\begin{theorem}
	For every integer composition $\alpha$, there is an explicit bijection from $\Trees_{\alpha}$ to each of the following sets: $\Symmetric_{\alpha}(231)$, $\nc_{\alpha}$, $\Dyck_{\alpha}$.  
\end{theorem}

\subsection{LAC Trees and Parabolic $231$-Avoiding Permutations}
	\label{sec:lac_trees_231_avoiding}
Let $T\in\Trees_{\alpha}$.  We label the non-root nodes of $T$ in \tdef{postfix order}, \ie by the order of \emph{last} visits in left-to-right traversal, and read labels in each block from left to right, with blocks in increasing order of color.  This gives a permutation in $\Symmetric_{\alpha}$, which is in fact also $(\alpha,231)$-avoiding.  Let $\lactoperm\colon\Trees_{\alpha}\to\Symmetric_{\alpha}(231)$ denote the corresponding map.

Conversely, for $w\in\Symmetric_{\alpha}(231)$, we recursively construct a plane rooted tree with $n$ non-root nodes compatible with $\alpha$.  Starting from a root node labeled by $n+1$, we successively insert nodes labeled by $w(i)$ for $i$ from $1$ through $n$ to get a labeled plane tree.  In the $i$-th step, \ie when we want to insert a node labeled by $w(i)$, we start a visit of the tree from the root.  Suppose that we are at a node labeled by $a$.  If $w(i) < a$, we move to the first child of this node, otherwise we move to its first sibling.  If the intended next node does not exist, we create it and label it by $w(i)$.  After all entries of $w$ are inserted, we obtain a plane tree which turns out to be compatible with $\alpha$.  We denote by $\permtolac\colon\Symmetric_{\alpha}(231)\to\Trees_{\alpha}$ the corresponding map, which is illustrated in \cref{fig:tree-perm-bij}. Readers familiar with binary trees may notice this map essentially is the insertion algorithm for binary search trees composed with the classical bijection between binary and plane trees. 

\begin{proposition}\label{prop:lac-to-perm}
	For every integer composition $\alpha$, the map $\lactoperm\colon\Trees_{\alpha}\to\Symmetric_{\alpha}(231)$ is a bijection, whose inverse is $\permtolac$.
\end{proposition}

\subsection{LAC Trees and Parabolic Noncrossing Partitions}
	\label{sec:lac_trees_noncrossing}

Let $T\in\Trees_{\alpha}$.  We write the $n$ non-root nodes on a horizontal line, grouped by color, with nodes in the each group in left-to-right order in $T$, and with groups in increasing order of colors.  We connect two vertices $a$ and $b$ by a bump in this \tdef{flattening} if and only if $b$ is the rightmost child of $a$.  See \cref{fig:lac-to-nc} for an example. By construction, the corresponding diagram belongs to an $\alpha$-partition, which is in fact noncrossing.  We denote by $\lactonc\colon\Trees_{\alpha}\to\nc_{\alpha}$ the corresponding map.

\begin{figure}
	\centering
	\begin{tikzpicture}
	\draw(0,0) node(lac){\lactreeBnc{0.9}};
	\draw(8,0) node(nc){\ncB{1.5}};
	\draw[->] (lac) -- (nc) node[above,midway]{$\lactonc$};
	\end{tikzpicture}
	\caption{An illustration of the map $\lactonc$ for $\alpha=(1,3,1,2,4,3)$.} \label{fig:lac-to-nc}
\end{figure}

Conversely, for $\mathbf{P}\in\nc_{\alpha}$, to construct an $\alpha$-tree, we start with a collection of $n+1$ labeled nodes, with the node labeled by $n+1$ being the root.  Consider the $i$-th node $u_i$ in the diagram of $\mathbf{P}$.  If $u_i$ does not see any bump above, then it becomes a child of the root; if it lies directly below the bump starting from the $k$-th node $u_k$ in the diagram, then $u_i$ becomes a child of $u_k$.  Here, a vertex lies \tdef{directly below} a bump if it is either the end point of said bump or it is not separated from this bump by another bump.  The resulting plane rooted tree is unique and compatible with $\alpha$; thus an $\alpha$-tree.  We denote by $\nctolac\colon\nc_{\alpha}\to\Trees_{\alpha}$ the corresponding map.

\begin{proposition} \label{prop:lac-to-nc}
	For every integer composition $\alpha$, the map $\lactonc\colon\Trees_{\alpha}\to\nc_{\alpha}$ is a bijection, whose inverse is $\nctolac$.
\end{proposition}

\subsection{LAC Trees and Parabolic Dyck Paths}
	\label{sec:lac_trees_nonnesting}

Let $T\in\Trees_{\alpha}$.  For $k\in [r]$, let $s_k=\alpha_1+\alpha_2+\dots+\alpha_k$ as defined in \cref{sec:tamari_lattices}, and $a_{k}$ the number of active nodes at the $k$-th coloring step in the construction of $T$, which are the nodes in $T$ of color bigger than $k$ whose parent has color at most $k$.  We construct a Dyck path by describing the positions of its valleys, which correspond to nodes in $T$ with at least one child.  Suppose that the right-most child of the $i$-th vertex of color $k$ is the $j$-th active node in the $k$-th coloring step.  The corresponding valley then has coordinates $(p,q)$ with $p=s_k-i+1$ and $q=s_k+a_{k}-j$. It turns out that this uniquely defines a Dyck path that is indeed weakly above $\nu_{\alpha}$. We denote by $\lactonn\colon\Trees_{\alpha}\to\Dyck_{\alpha}$ the corresponding map.

Conversely, for $\mu\in\Dyck_{\alpha}$, we construct a plane rooted tree recursively as follows.  Starting with a root node, we add as many children to it as there are north-steps in $\mu$ on the $y$-axis.  We then color $\alpha_{1}$ of them with color $1$.  Now, for $k\in[r-1]$ we add as many children to the $i$-th node of color $k$ as there are north-steps in $\mu$ with $x$-coordinate equal to $s_{k}-i+1$.  After every node of color $k$ has received all its children, we color the first $\alpha_{k+1}$ uncolored nodes from left to right with color $k+1$.  Since $\mu$ is weakly above $\nu_{\alpha}$, the tree $T$ is compatible with $\alpha$.  We denote by $\nntolac\colon\Dyck_{\alpha}\to\Trees_{\alpha}$ the corresponding map.  

\begin{proposition} \label{prop:lac-to-nn}
	For every integer composition $\alpha$, the map $\lactonn\colon\Trees_{\alpha}\to\Dyck_{\alpha}$ is a bijection, whose inverse is $\nntolac$.
\end{proposition}

\begin{remark}
	We have $\Theta_{1}(\overline{\mu})=\lactonc\circ\nntolac(\mu)$ for every $\mu\in\Dyck_{\alpha}$, where $\overline{\mu}$ is the reversed path of $\mu$.
\end{remark}


%!TEX root = ./main_file.tex
\section{LAC Trees and Level-Marked Dyck Paths}
	\label{sec:lac_trees_level_marked_paths}
We introduce yet another family of combinatorial objects in bijection with left-aligned colorable trees. A \tdef{level-marked Dyck path} is a Dyck path with two types of north-steps $N_{\bullet}$ and $N_{\circ}$ under the condition that, for each lattice point $(p,q)$ on the path, there are at least $q-p$ north-steps of type $N_{\bullet}$ (or \tdef{marked north steps}) that come before it.  Let $\Dyck_{n}^{\bullet}$ be the set of level-marked Dyck paths consisting of $2n$ steps. Level-marked Dyck paths have been introduced in \cite[Section~2.2.3]{ceballos_hopf_2018} under the name ``colored Dyck paths'', and it was shown there that $\Dyck_{n}^{\bullet}$ is in bijection with the set of lattice walks in $\mathbb{N}\times\mathbb{N}$ with $2n$ steps in the set $\bigl\{(0,1),(-1,1),(1,-1)\bigr\}$ that start at the origin and end on the $x$-axis, by sending $N_{\bullet}$ to $(0,1)$, $N_{\circ}$ to $(-1,1)$ and $E$ to $(1,-1)$.

\begin{figure}
  \centering
  \includegraphics[page=2,width=0.83\textwidth]{fig/ipe-fig.pdf}
  \caption{Illustrations of the maps $\lactodyck$ and $\lactosteep$ for $n=14$ and $\alpha=(1,3,1,2,4,3)$.}
  \label{fig:bij-tree-dyck}
\end{figure}

Let us write $\alpha\models n$ to mean that $\alpha$ is an integer composition of $n$.  For $n>0$ we denote by $\LAC_{n}\defs\bigl\{(T,\alpha)\mid\alpha\models n,T\in\Trees_{\alpha}\bigr\}$ the set of all \tdef{LAC trees} of $n$.  

Given $(T,\alpha)\in\LAC_{n}$, we construct a marked Dyck path by a \emph{right-to-left} traversal of $T$.  At each time we reach a new node, if its color with respect to $\alpha$ is not seen before, we add a marked north-step $N_\bullet$, otherwise we add a regular north-step $N_\circ$. At each time we go back up one level, we add an east-step $E$.  It turns out that this path is indeed a level-marked Dyck path.  We denote by $\lactodyck\colon\LAC_{n}\to\Dyck_{n}^{\bullet}$ the corresponding map, which is illustrated in \cref{fig:bij-tree-dyck}.

Conversely, for $\mu^{\bullet}\in\Dyck_{n}^{\bullet}$, we construct a plane rooted tree starting from a single root as follows.  
We go over $\mu^{\bullet}$ as a word, and construct a tree according to the following rules: when we read a north-step (marked or unmarked) we add a child to the left of the current node and move there, and when we read an east-step we go to the parent of the current node. Simultaneously, we determine the coloring of the non-root nodes by taking into account the markings.  For this we start with an empty list of colors which is updated throughout the process maintaining a pointer on the colors.   
When we read a marked north-step~$N_\bullet$, we insert a new color $c$ in the list just after the pointer, and move the pointer there, while coloring the new node by $c$.
When we read an unmarked north-step $N_\circ$, we move the pointer to the next color $c'$ in the list and color the new node by $c'$.
When we read an east-step, we move the pointer to the previous color in the list.
The marking condition of level-marked Dyck paths ensures that we always have enough colors to move the pointer accordingly.
When we finish reading $\mu^{\bullet}$, we reorder the colors by their first appearances in \emph{left-to-right} order.  If we have used $r$ colors, then we obtain a composition $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{r})$ of $n$, where $\alpha_{i}$ is the number of nodes with color $i$.  It turns out that the resulting tree is compatible with $\alpha$.  We denote by $\dycktolac\colon\Dyck_{n}^{\bullet}\to\LAC_{n}$ the map we have just described. 

\begin{proposition}
	For $n>0$ the map $\lactodyck\colon\LAC_{n}\to\Dyck_{n}^{\bullet}$ is a bijection, whose inverse is $\dycktolac$.
\end{proposition}

%!TEX root = ./main_file.tex
\section{The Steep-Bounce Zeta Map}

A pair $(\mu_{1},\mu_{2})$ of Dyck paths of the same length is \tdef{nested} if $\mu_{1}$ always stays weakly below~$\mu_{2}$.  Let $\SteepPairs_{n}$ denote the set of all nested pairs $(\mu_{1},\mu_{2})$ such that $\mu_{1},\mu_{2}\in\Dyck_{n}$ and $\mu_{2}$ is steep.  We call the elements of $\SteepPairs_{n}$ \tdef{steep pairs}.  Similarly, we denote by $\BouncePairs_{n}$ the set of all nested pairs $(\mu_{1},\mu_{2})$ such that $\mu_{1},\mu_{2}\in\Dyck_{n}$ and $\mu_{1}$ is bounce.  We call the elements of $\BouncePairs_{n}$ \tdef{bounce pairs}.

We now explain how to encode a level-marked Dyck path $\mu^{\bullet}\in\Dyck_{n}^{\bullet}$ as a nested pair of Dyck paths.  Let $\mu_{1}$ be the Dyck path obtained by forgetting the marking, and $\mu_{2}\in\Dyck_{n}$ constructed by forgetting all east steps, replacing each marked north-step $N_\bullet$ in $\mu^{\bullet}$ by $N$ and each regular north-step $N_\circ$ in $\mu^{\bullet}$ by $EN$, and appending east-steps at the end until reaching $(n,n)$. Then, $\mu_{2}$ is steep, and it follows that the map that sends $\mu^{\bullet}$ to the pair $(\mu_1,\mu_2)$ is a bijection from~$\Dyck_{n}^{\bullet}$ to $\SteepPairs_{n}$~\cite[Section~2.2.3]{ceballos_hopf_2018}. We denote by~$\lactosteep\colon\LAC_{n}\to\SteepPairs_{n}$ the composition of $\lactodyck$ with this map. Then~$\lactosteep$ is a bijection and we denote by~$\steeptolac$ its inverse. See \cref{fig:bij-tree-dyck} for an example.

The purpose of this section is to prove the Steep-Bounce Conjecture of Bergeron, Ceballos and Pilaud~\cite[Conjecture~2.2.8]{ceballos_hopf_2018}.  This conjecture arises as a combinatorial approach to understand an intriguing connection between the study of lattice walks in the positive quarter plane mentioned above and certain Hopf algebras with applications in the theory of multivariate diagonal harmonics.  

Any $\alpha$-path $\mu\in\Dyck_{\alpha}$ can be regarded as a bounce pair $(\nu_{\alpha},\mu)\in\BouncePairs_{n}$.  We may thus extend the bijection $\lactonn\colon\Trees_{\alpha}\to\Dyck_{\alpha}$ from \cref{sec:lac_trees_nonnesting} to a bijection $\lactobounce\colon\LAC_{n}\to\BouncePairs_{n}$, where $\lactobounce(T,\alpha)=\bigl(\nu_\alpha,\lactonn(T)\bigr)$. We denote by $\bouncetolac$ its inverse.

\begin{figure}
	\centering
	\includegraphics[page=11, scale=0.87]{fig/ipe-fig.pdf}
	\caption{An illustration of the steep-bounce zeta map $\Gamma$.}
	\label{fig:steep_bounce_zeta_map}
\end{figure}

\begin{theorem}[The Steep-Bounce Theorem]\label{thm_steepbounceconjecture}
	Let $\steeppairtobouncepair\defs\lactobounce\circ\steeptolac$.  For $n>0$ and every $r\in[n]$, $\steeppairtobouncepair$ is a bijection from 
	\begin{itemize}
		\item the set of nested pairs $(\mu_{1},\mu_{2})$ of Dyck paths with $2n$ steps, where $\mu_{2}$ is a steep path ending with exactly $r$ east steps with $y$-coordinate equal to $n$, to
		\item the set of nested pairs $(\mu'_{1},\mu'_{2})$ of Dyck paths with $2n$ steps, where $\mu'_{1}$ is a bounce path that touches the main diagonal $r+1$ times.
	\end{itemize}
\end{theorem}

\begin{corollary}[{\cite[Conjecture~2.2.1]{ceballos_hopf_2018}}]
	The graded dimension of degree $n$ of the Hopf algebra considered in~\cite[Section~2.2]{ceballos_hopf_2018} equals the number of walks in the quarter plane starting from the origin, ending on the $x$-axis, and consisting of $2n$ steps taken from $(-1, 1), (1, -1), (0, 1)$.
\end{corollary}

An example of the bijection $\steeppairtobouncepair$ can be found in \cref{fig:steep_bounce_zeta_map}.  Interestingly, the map $\steeppairtobouncepair$ generalizes the classical zeta map in $q,t$-Catalan combinatorics.  More precisely, we recall that we can associate with any Dyck path $\mu\in\Dyck_{n}$ a ``smallest'' steep path $\mu_{\mathrm{steep}}$ weakly above $\mu$, and a ``largest'' bounce path $\mu_{\mathrm{bounce}}$ weakly below~$\mu$, both using a greedy algorithm.  
Under the bijections $\steeptolac$ and $\bouncetolac$, the pairs of the form $(\mu,\mu_{\mathrm{steep}})$ and $(\nu_{\mathrm{bounce}},\nu)$ are mapped to $\LAC$ trees $(T,\alpha)$ such that $\alpha_i$ is the number of non-root nodes at distance $i$ from the root. With these relations, we prove the following result. 

\begin{theorem}
For $n>0$, the map $\steeppairtobouncepair$ restricts to a bijection from 
	\begin{itemize}
		\item the set of pairs $(\mu,\mu_{\mathrm{steep}})$ where $\mu$ is a Dyck path with $2n$ steps, to
		\item the set of pairs $(\nu_{\mathrm{bounce}},\nu)$ where $\nu$ is a Dyck path with $2n$ steps.
	\end{itemize}
Moreover, if $(\nu_{\mathrm{bounce}},\nu)=\steeppairtobouncepair(\mu,\mu_{\mathrm{steep}})$ then $\nu=\zeta(\mu)$ where $\zeta$ is the zeta map from $q,t$-Catalan combinatorics. 
\end{theorem}

A generalization of the zeta map on parking functions, due to Haglund and Loehr~\cite{haglund_conjectured_2005}, can also be obtained as a labeled version of this result.  We refer to \cite[Section~3.3]{full-version} for more details.



\printbibliography

\end{document}
