%% if you are submitting an initial manuscript then you should have submission as an option here %% if you are submitting a revised manuscript then you should have revision as an option here %% otherwise options taken by the article class will be accepted \documentclass[submission]{FPSAC2026} %% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc %% note that the class file already loads {amsmath, amsthm, amssymb} \usepackage{thmtools} \usepackage{subfig} \usepackage{caption} \hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue} \usepackage{float} \usepackage[table]{xcolor} \usepackage{xcolor} \usepackage{xargs} %% removed because there was an option clash %\usepackage[noabbrev,capitalise]{cleveref} \usepackage[noabbrev]{cleveref} \usepackage[export]{adjustbox} \usepackage{paralist} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{remark}[theorem]{Remark} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{example}[theorem]{Example} %\newtheorem{thm}{Theorem}[section] %\newtheorem{lem}[thm]{Lemma} %\newtheorem{prop}[thm]{Proposition} %\newtheorem{defi}[thm]{Definition} %\newtheorem{cnj}[thm]{Conjecture} %\newtheorem{cor}[thm]{Corollary} %\newtheorem{rem}[thm]{Remark} \newcommand{\N}{\mathbb N} \newcommand{\C}{\mathbb C} \renewcommand{\L}{\mathbf L} \newcommand{\K}{\mathbf K} \renewcommand{\P}{\mathcal P} \newcommand{\Cc}{\mathcal C} \newcommand{\Ss}{\mathfrak S} \newcommand{\ASM}{\mathbf{ASM}} \newcommand{\HFM}{\mathbf{HFM}} \newcommand{\NCP}{\mathbf{NCP}} \newcommand{\Cat}{\mathbf{Cat}} \newcommand{\Dyck}{\mathbf{Dyck}} \newcommand{\GT}{\mathbf{GT}} \newcommand{\DPoset}{\mathcal D} \newcommand{\TPoset}{\mathcal T} \newcommand{\JIrr}{\mathcal J} \newcommand{\MIrr}{\mathcal M} \newcommand{\CT}{\operatorname {CT}} \newcommand{\BPD}{\operatorname {BPD}} \newcommand{\BCPD}{\operatorname {BCPD}} \newcommand{\bcc}{\operatorname {bcc}} \newcommand{\Upper}{\mathbf{Up}} \newcommand{\Lower}{\mathbf{Lo}} \newcommand{\JIdeal}{\operatorname J} \newcommand{\jAnti}{\operatorname j} \newcommand{\MIdeal}{\operatorname M} \newcommand{\mAnti}{\operatorname m} \newcommand{\Nappe}{\operatorname N} \newcommand{\Epos}{\operatorname{E}_{\mathrm{pos}}} % excedance positions \newcommand{\Eval}{\operatorname{E}_{\mathrm{val}}} % excedance values \newcommand{\TL}{\operatorname {TL}} \newcommand{\CS}{\Sigma} \newcommand{\SixV}{\operatorname{SV}} \newcommand{\Sym}{\operatorname{Sym}} \newcommand{\QSym}{\operatorname{QSym}} \definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color \newcommand{\darkblue}{\color{darkblue}} % darkblue command \newcommand{\defn}[1]{\textsl{\darkblue #1}} % emphasis of a definition \newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation \renewcommand{\b}[1]{\boldsymbol{#1}} % bold \newcommand{\dotprod}[2]{\langle #1 | #2 \rangle} % dot product \newcommand{\ie}{\textit{i.e.}~} % id est \newcommand{\eg}{\textit{e.g.}~} % exempli gratia \newcommand{\aka}{\textit{aka.}~} % also known as \newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % := \newcommand{\ssm}{\smallsetminus} % set difference \newcommand{\precdot}{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}} \newcommand{\OEIS}[1]{\cite[{\rm \href{http://oeis.org/#1}{\texttt{#1}}}]{OEIS}} \newcommand{\cross}[1][black]{\raisebox{-.15cm}{\includegraphics[scale=.9]{figures/cross}}} \newcommand{\elbow}[1][black]{\raisebox{-.15cm}{\includegraphics[scale=.9]{figures/elbow}}} \usepackage{todonotes} \newcommand{\florent}[1]{\todo[color=orange!30]{#1 \\ \hfill --- F.}} \newcommand{\ludovic}[1]{\todo[color=green!30]{#1 \\ \hfill --- L.}} \newcommand{\vincent}[1]{\todo[color=blue!30]{#1 \\ \hfill --- V.}} % formating the table of contents \setcounter{tocdepth}{2} \makeatletter \def\l@section{\@tocline{1}{1pt}{0pc}{}{}} \def\l@part{\@tocline{1}{7pt}{0pc}{}{}} \makeatother \let\oldtocpart=\tocpart \newcommand{\tocpart}[2]{\sc\large\oldtocpart{#1}{#2}} \let\oldtocsection=\tocsection \newcommand{\tocsection}[2]{\bf\oldtocsection{#1}{#2}} \let\oldtocsubsubsection=\tocsubsubsection \newcommand{\tocsubsubsection}[2]{\quad\oldtocsubsubsection{#1}{#2}} %% define your title in the usual way \title[Heaps of rhombic dodecahedra, catalan congruences on ASMs, and bases of the TL algebra]{Heaps of rhombic dodecahedra, \\ catalan congruences on alternating sign matrices, \\ and bases of the Temperley--Lieb algebra} %%\thanks ne fonctionne pas %\thanks{VP was partially supported by the Spanish project PID2022-137283NB-C21 of MCIN/AEI/10.13039/501100011033 / FEDER, UE, by the Spanish--German project COMPOTE (AEI PCI2024-155081-2 \& DFG 541393733), by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R\&D (CEX2020-001084-M), by the Departament de Recerca i Universitats de la Generalitat de Catalunya (2021 SGR 00697), and by the French--Austrian project PAGCAP (ANR-21-CE48-0020 \& FWF I 5788).} %% define your authors in the usual way %% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details %% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author \author{Florent Hivert\thanks{Supported by the French--Austrian project PAGCAP (ANR-21-CE48-0020 \& FWF I 5788) and the EU H2020 projet FRESCO (No.101001995).}\addressmark{1}, Vincent Pilaud\thanks{Supported by the Spanish project PID2022-137283NB-C21 of MCIN/AEI/10.13039/501100011033 / FEDER, UE, by the Spanish--German project COMPOTE (AEI PCI2024-155081-2 \& DFG 541393733), by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R\&D (CEX2020-001084-M), by the Departament de Recerca i Universitats de la Generalitat de Catalunya (2021 SGR 00697), and by the French--Austrian project PAGCAP (ANR-21-CE48-0020 \& FWF I 5788).}\addressmark{2}, \and Ludovic Schwob\addressmark{3}} %\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1} \and you\addressmark{2}} %% then use \addressmark to match authors to institutions here %\address{\addressmark{1}Department of This, University of That, There \\ \addressmark{2}School of Something, University of Something Else, Somewhere} \address{\addressmark{1}LISN (UMR CNRS 9015), Université Paris Saclay, INRIA, CNRS \\ \addressmark{2}Universitat de Barcelona \& Centre de Recerca Matemàtica, Barcelona \\ \addressmark{3} LIGM, Universit\'e Gustave Eiffel, Champs-sur-Marne} %% put the date of submission here \received{\today} %% leave this blank until submitting a revised version %\revised{} %% put your English abstract here, or comment this out if you don't have one yet %% please don't use custom commands in your abstract / resume, as these will be displayed online %% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year) \abstract{We prove that the excedance relation on permutations of N.~Bergeron and L.~Gagnon extends to a congruence of the lattice on alternating sign matrices. We therefore study all congruences of the lattice on ASMs whose quotient is isomorphic to the Stanley lattice on Dyck paths. The maxima of their classes are always covexillary permutations (and all covexillary permutations appear this way), and the minimal permutations in each class are always precisely the $321$-avoiding permutations. Finally, any choice of representative permutations in each class yield a basis of the \mbox{Temperley--Lieb} algebra, vastly generalizing the bases arising from the \mbox{excedance relation}.} %% put your French abstract here, or comment this out if you don't have one %\resume{\lipsum[2]} %% put your keywords here, or comment this out if you don't have them yet \keywords{Alternating sign matrices, lattice congruences, Temperley--Lieb algebra} %% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier %% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text %% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex %% but you can use bibtex if you want %\usepackage[backend=bibtex]{biblatex} %\addbibresource{Quotient_ASMs.bib} %% I COULDN'T GET IT TO WORK WITH STYLE = ALPHETIC \bibliography{Quotients_ASMs} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \articlenumber{17} \begin{document} \maketitle %% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above \section{Introduction} \label{sec:introduction} The quotient $\K[X]/\langle\Sym^+(X)\rangle$ of the polynomial ring on~$X = \{x_1,\dots,x_n\}$ by the ideal generated by symmetric polynomials with no constant terms is of dimension~$n!$ and is isomorphic to the regular representation of the symmetric group~$\Ss_n$. Chevalley–Shephard–Todd's theorem asserts that this statement remains true when the symmetric group is replaced by any real or complex reflection group. In the combinatorics community, a large body of work has been devoted to understanding this representation-theoretic structure in more explicit terms. One notable outcome is A.~Lascoux’s theory of Schubert polynomials~\cite{lascouxschutzenberger87,macdonald.1991}, which provides a remarkably elegant basis \mbox{for this quotient.} There is another closely related case which, however, remains much less understood: the ring of quasi-symmetric polynomials. Recall that these were introduced by I.~Gessel~\cite{Gessel.1984} as generating series encoding permutations with a prescribed descent set. While many parallels with the theory of symmetric functions have been developed, both from combinatorial and representation-theoretic perspectives~\cite{KrobThibon.1997, Hivert2000}, the invariant-theoretic viewpoint has long remained elusive. Nevertheless, there have been persistent indications that a structure analogous to the symmetric and coinvariant settings should exist. On the one hand, the ring of quasi-symmetric polynomials is invariant under a modified action of the symmetric group~\cite{Hivert2000}. In contrast to the classical situation, this action is not faithful and factors through the \mbox{Temperley--Lieb} algebra~$\TL(2)$, whose dimension is the $n$-th Catalan number~$C_n$. On the other hand, J.~C.~Aval and N.~Bergeron~\cite{AvalBergeron2003} noticed that the quotient $\K[X]/\langle\QSym^+(X)\rangle$ is also of dimension~$C_n$. However, the connection between these two occurrences of Catalan numbers is not straightforward. The reason is that the Temperley–Lieb action is not multiplicative, hence the space~$\K[X]/\langle\QSym^+(X)\rangle$ does not naturally inherit an action~of~$\TL(2)$. %, making the relationship between the two Catalan structures subtle to uncover. In a recent breakthrough~\cite{BergeronGagnon}, N.~Bergeron and L.~Gagnon constructed a particular set of~$C_n$ permutations whose projection in $\TL(2)$ gives a basis, and such that the graded ideal of the vanishing ideal is equal to~$\langle\QSym^+(X)\rangle$. They defined the \defn{excedance equivalence}~$\equiv$ on permutations of~$[n]$, where two permutations are excedance equivalent if they share the same sets of positions and of values of their excedances. They prove that \begin{compactenum}[(i)] \item the excedance classes are Bruhat intervals, whose minima are the $321$-avoiding permutations, and whose maxima are some covexillary permutations, \item the poset quotient of the Bruhat order on permutations by the excedance relation is isomorphic to the Stanley lattice on Dyck paths, \item any choice of representatives of the excedance classes yields a basis of~$\TL(2)$, \item the top degree homogeneous components of the vanishing ideal of the set of permutations which are maximal in their excedance classes and the positive degree quasisymmetric polynomials generate the same ideal. \end{compactenum} Our work starts from the observation that this excedance relation on the Bruhat order extends to a congruence of the lattice of alternating sign matrices (which is the MacNeille completion of the Bruhat order). Using a combination of lattice and geometric perspectives on alternating sign matrices, we then study all lattice congruences~$\equiv$ on alternating sign matrices whose quotient is isomorphic to the Stanley lattice, which we call \defn{catalan congruences}. We encode bijectively these congruences using several combinatorial structures, related to Gelfand--Tsetlin patterns and pipe dreams. Using these descriptions, we finally prove that for any catalan congruence~$\equiv$, \begin{compactenum}[(i)] \item the maxima of classes of~$\equiv$ are covexillary permutation matrices, \item the minimal permutations in the classes of~$\equiv$ are the $321$-avoiding permutations, \item any choice of permutations in each class of~$\equiv$ yields a basis of~$\TL(2)$. \end{compactenum} We refer to~\cite{HivertPilaudSchwob} for many details and all proofs omitted in this extended abstract. % due to space limitations. %%%%%%%%%%%%%%% \pagebreak \section{Two distributive lattices} \label{sec:distributiveLattices} %%%%% \subsection{Meet and join representations in distributive lattices} \label{subsec:meetJoinRepresentationsDistributiveLattices} A \defn{lower} (resp.~\defn{upper}) \defn{set} of a poset~$\P$ is a subset~$X$ of~$\P$ such that~$x \in X$ and~$x \ge y$ (resp.~$x \le y$) implies~$y \in X$. A \defn{lattice}~$\L$ is \defn{distributive} if~${x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)}$ and~$x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$ for all~$x,y,z \in \L$. An element~$x \in \L$ is \defn{join} (resp.~\defn{meet}) \defn{irreducible} if it covers (resp.~is covered by) a single~$x_\star$ (resp.~$x^\star$). We denote by~$\JIrr(\L)$ (resp.~$\MIrr(\L)$) the subposet of~$\L$ induced by its join (resp.~meet) irreducibles. The following classical result is known as the fundamental theorem for distributive lattices. \begin{theorem}[Birkhoff] \label{thm:ftfdl} \begin{compactitem} \item The set~$\Lower(\P)$ (resp.~$\Upper(\P)$) of lower (resp.~upper) sets of any poset~$\P$ ordered by inclusion forms a distributive lattice. \item Conversely, any distributive lattice~$\L$ is isomorphic to the inclusion poset of lower (resp.~upper) sets of its join (resp.~meet) irreducible poset~$\JIrr(\L)$ (resp.~$\MIrr(\L)$). \end{compactitem} \end{theorem} For~$x \in \L$, we denote by~$\JIdeal(x) \eqdef \set{j \in \JIrr(\L)}{j \le x}$ the corresponding lower set of~$\JIrr(\L)$, and by~$\jAnti(x) \eqdef \max(\JIdeal(x))$ the corresponding antichain of~$\JIrr(\L)$. Define dually $\MIdeal(x) \eqdef \set{m \in \MIrr(\L)}{x \le m}$ and $\mAnti(x) \eqdef \min(\MIdeal(x))$. %%%%% \subsection{Dyck paths} \label{subsec:DyckPaths} A \defn{Dyck path} of semilength~$n$ is a path with up steps~$(1,1)$ and down steps~$(1,-1)$, starting at~$(0,0)$, ending at~$(2n,0)$, and never passing strictly below the horizontal axis. They define the \defn{Dyck path lattice}~$\Dyck_n$ (also known as the \defn{Stanley lattice}) with the relation~${P \le Q}$ if~$P$ stays below~$Q$. The join (resp.~meet) irreducible Dyck paths are those with a single peak (resp.~valley), hence the poset~$\JIrr(\Dyck_n)$ (resp.~$\MIrr(\Dyck_n)$) is isomorphic to the triangular poset~$\DPoset_n$ of triples $(y_1,y_2,y_3)$ with $y_1+y_2+y_3 =n-2$, ordered by $(y_1,y_2,y_3) \le (z_1,z_2,z_3)$ if and only if $y_1+y_2\le z_1+z_2$ and $y_2+y_3 \le z_2+z_3$. %%%%% \subsection{Alternating sign matrices} \label{subsec:ASMs} We closely follow the presentation of~\cite{Propp01}. Recall that an \defn{alternating sign matrix} (ASM) of order~$n \ge 1$ is an $(n \times n)$-matrix~$A = (A_{i,j})_{1 \le i,j \le n}$ with entries~$-1$, $0$ or~$1$, with row and column sums equal to~$1$, and such that nonzero entries alternate between~$1$ and~$-1$ in each row and each column. Its \defn{corner sum matrix}~(CSM) and \defn{height function matrix}~(HFM) are the $(n+1) \times (n+1)$-matrices~$C = (C_{i,j})_{0 \le i,j \le n}$ and~$H = (H_{i,j})_{0 \le i,j \le n}$ defined by~$C_{i,j} = \sum_{i' \le i, j' \le j} A_{i',j'}$ and $H_{i,j} = i+j-2C_{i,j}$ for~$0 \le i,j \le n$. See \cref{fig:ASM1}. \begin{figure}[h] \centerline{\scalebox{.8}{ $\begin{pmatrix} \cdot & \cdot & + & \cdot & \cdot \\[.1cm] \cdot & + & - & + & \cdot \\[.1cm] \cdot & \cdot & + & - & + \\[.1cm] + & - & \cdot & + & \cdot \\[.1cm] \cdot & + & \cdot & \cdot & \cdot \end{pmatrix}$\quad $\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 2 & 2 \\ 0 & 0 & 1 & 2 & 2 & 3 \\ 0 & 1 & 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 & 4 & 5 \end{pmatrix}$\quad $\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 2 & 3 & 4 \\ 2 & 3 & 2 & 3 & 2 & 3 \\ 3 & 4 & 3 & 2 & 3 & 2 \\ 4 & 3 & 4 & 3 & 2 & 1 \\ 5 & 4 & 3 & 2 & 1 & 0 \end{pmatrix}$\quad }} \caption{An ASM, a CSM, and a HFM, all corresponding to each other.} \label{fig:ASM1} \end{figure} The HFMs ordered componentwise define a distributive lattice~$\HFM_n$ where the join (resp.~meet) of two HFMs~$H, H'$ has \mbox{$(i,j)$-entry} $\max(H_{i,j}, H'_{i,j})$ (resp.~$\min(H_{i,j}, H'_{i,j})$). We now introduce a geometric interpretation of the join irreducible poset following~\cite{Propp01, Str11}. The join irreducible poset~$\JIrr(\HFM_n)$ can be seen geometrically as a poset~$\TPoset_n$ on the integer points inside the $(n-2)$th dilate of a $3$-dimensional tetrahedron resting on an edge~\cite{Propp01}. See \cref{fig:ASM2}. Using barycentric coordinates, this poset is defined on the quadruples~$\b{x} := (x_1, x_2, x_3, x_4) \in \N^4$ with~$x_i \ge 0$ for~$i \in [4]$ and~${x_1 + x_2 + x_3 + x_4 = n-2}$ ordered by $\b{x} \le \b{y}$ if and only if $x_1\ge y_1$, $x_2\le y_2$, $x_3\le y_3$ and $x_4\ge y_4$. Its cover relations are the pairs~$\b{x} \lessdot \b{y}$ such that~$\b{y} - \b{x}$ is one of the four vectors~$b \eqdef (-1,1,0,0)$, $r \eqdef (-1,0,1,0)$, $o \eqdef (0,1,0,-1)$ and~$g \eqdef (0,0,1,-1)$. We can thus see an HFM as a lower set in this 4-colored tetrahedral poset, as illustrated in \cref{fig:ASM2}\,(left). Note that via the above-mentioned bijection between ASMs and HFMs, we can transport the lattice~$\HFM_n$ on HFMs of order~$n$ to a lattice~$\ASM_n$ on ASMs of order~$n$. Identifying a permutation~$\sigma$ of~$[n]$ with its matrix~$P_\sigma \eqdef [\delta_{\sigma(i),j}]_{i,j \in [n]}$, this lattice~$\ASM_n$ is the MacNeille completion of the Bruhat order on permutations of~$[n]$. The join (resp.~meet) irreducible ASMs are known to be the matrices of the \defn{bigrassmannian} (resp.~\defn{anti-bigrass\-mannian}) permutations, \ie the permutations~$\sigma$ such that $\sigma$ and its inverse~$\sigma^{-1}$ have only one descent (resp.~ascent). An integer point~$\b{x} = (x_1, x_2, x_3, x_4)$ in the tetrahedron corresponds to the bigrassmannian and anti-bigrassmannian permutations \[ j(\b{x}) = \begin{pmatrix} I_{x_1} & 0 & 0 & 0 \\ 0 & 0 & I_{x_2+1} & 0 \\ 0 & I_{x_3+1} & 0 & 0 \\ 0 & 0 & 0 & I_{x_4} \end{pmatrix} \qquad\text{and}\qquad m(\b{x}) = \begin{pmatrix} 0 & 0 & 0 & \bar I_{x_2} \\ 0 & \bar I_{x_1+1} & 0 & 0 \\ 0 & 0 & \bar I_{x_4+1} & 0 \\ \bar I_{x_3} & 0 & 0 & 0 \end{pmatrix} \] where~$I_k$ (resp.~$\bar I_k$) is the $k \times k$ identity (resp.~anti-identity) matrix. \begin{figure}[b] \centerline{ \includegraphics[scale=.14,valign=c]{figures/ASM1} \quad \includegraphics[scale=.12,valign=c]{figures/ASM2} \quad \includegraphics[scale=.12,valign=c]{figures/ASM3} } \caption{The ASM of \cref{fig:ASM1} seen as a lower set~$X$ of the tetrahedron poset~$\TPoset_5$ (left) or equivalently as the surface separating~$X$ from its complement (middle and right).} \label{fig:ASM2} \end{figure} It is also interesting to represent an ASM as the surface~$S$ separating the lower set~$X$ of~$\TPoset_n$ and its complement. For this, we include additional edges so that each integer point of the tetrahedron gets $12$ incident arrows (one in the direction~$\b{e}_i-\b{e}_j$ for each~${i \ne j \in [4]}$). The horizontal edges, in direction~$\pm(1,0,0,-1)$ and~$\pm(0,1,-1,0)$, are colored in gray. The additional endpoints are considered in~$X$ (resp.~in its complement) if they are incident to an arrow which is also incident to one of the two bottom (resp.~top) faces of the tetrahedron. We then add a rhombus orthogonal to each arrow from a point in~$X$ to a point in its complement (the color of the rhombus matches the color of the orthogonal arrow). The corresponding surface is illustrated in \cref{fig:ASM2}\,(middle and right). As illustrated in \cref{fig:ASM3}, looking at this surface~$S$ from above (\ie from~$(-1,1,1,-1)$) makes transparent some well-known bijections between different models for ASMs: \begin{compactitem} \item Seen from above, the colored rhombi of~$S$ forms a \defn{rainbow tiling}. See \cref{fig:ASM3}\,(a). \item The \defn{ASM} records the saddle points of~$S$. See \cref{fig:ASM3}\,(b). \item The \defn{six-vertex model} is given by the horizontal diagonals of the rhombi of~$S$, oriented counterclockwise around the surface~$S$. See \cref{fig:ASM3}\,(c). \item The \defn{HFM} records the height of the surface above integer points. See \cref{fig:ASM3}\,(d). \item The \defn{fully packed loop} is given by the horizontal diagonals of the red and orange (resp.~green and blue) rhombi of~$S$ located at odd (resp.~even) heights. \cref{fig:ASM3}\,(e). \end{compactitem} \begin{figure}[h] \centerline{\scalebox{.98}{ \begin{tabular}{ccccc} \includegraphics[scale=.1,valign=c]{figures/ASM4a} & \includegraphics[scale=.1,valign=c]{figures/ASM4b} & \includegraphics[scale=.1,valign=c]{figures/ASM5a} & \includegraphics[scale=.1,valign=c]{figures/ASM6c} & \includegraphics[scale=.1,valign=c]{figures/ASM7a} \\[1.1cm] (a) & (b) & (c) & (d) & (e) \end{tabular}} } \caption{Reading bijections on the surface of the ASM of \cref{fig:ASM1}.} \label{fig:ASM3} \end{figure} Finally, it is also interesting to represent an ASM as a stack of rhombic dodecahedra. The \defn{rhombic dodecahedron} is the convex hull of the $8$ vertices~$\pm\b{e}_1 \pm\b{e}_2 \pm\b{e}_3$ of the standard cube together with the~$6$ points~$\pm2\b{e}_i$ for~$i \in [3]$. See \cref{fig:ASM5}. \begin{figure}[h] \centerline{ \includegraphics[height=3.1cm,valign=c]{figures/rhombicDodecahedron} \qquad \includegraphics[height=3.1cm,valign=c]{figures/scad1} \qquad \includegraphics[height=3.1cm,valign=c]{figures/scad4} } \caption{The rhombic dodecahedron (left), and the ASM of \cref{fig:ASM1} seen as a pile of rhombic dodecahedra, as 3d objects in OpenSCAD (middle) and in real life (right).} \label{fig:ASM5} \end{figure} %%%%%%%%%%%%%%% \clearpage \section{The excedance congruence of~$\ASM_n$} \label{sec:excedanceQuotient} This section defines a relevant lattice congruence of~$\ASM_n$, extending the excedance relation of the Bruhat order on permutations defined by N.~Bergeron and L.~Gagnon~in~\cite{BergeronGagnon}. %%%%% \subsection{The excedance relation on permutations} \label{subsec:excedanceRelation} A \defn{noncrossing partition} (NCP) of~$[n]$ is a collection~$\lambda \subseteq \set{(i,j)}{1 \le i \le j \le n}$ such that there is no~$(i,j), (k,\ell) \in \lambda$ with~$i \le k < j \le \ell$. Equivalently, it is a collection of arcs over the points~$1, \dots, n$ on the horizontal line, such that any two arcs do not cross in their interior, nor share their left endpoints nor their right endpoints. We denote by~$\lambda^- \eqdef \set{i}{(i,j) \in \lambda}$ the set of left endpoints and~$\lambda^+ \eqdef \set{j}{(i,j) \in \lambda}$ the set of of right endpoints of~$\lambda$. We denote by~$\NCP_n$ the transitive closure of the relation~$\precdot$ on NCPs of~$[n]$ defined by~$\lambda \precdot \mu$ if and only if~$\lambda = \mu \ssm \{(i,i+1)\}$ for some~$i \in [n-1]$ or~$\lambda = \mu \ssm \{(i,k)\} \cup \{(i,j), (j,k)\}$ for some~$1 \le i < j < k \le n$. Note that the standard bijection between NCPs of~$[n]$ and Dyck paths of semilength~$n$ (see \cref{fig:bijectionDyckPathNonCrossingPartition}) sends the poset~$\NCP_n$ to the Stanley lattice~$\Dyck_n$. \begin{figure}[ht] \centerline{\includegraphics[scale=1]{figures/bijectionDyckPathNonCrossingPartition}} \caption{The standard bijection from Dyck paths (left) to NCPs (right).} \label{fig:bijectionDyckPathNonCrossingPartition} \end{figure} \begin{definition}[\cite{BergeronGagnon}] A \defn{weak excedance} of a permutation~$\sigma \in \Ss_n$ is a pair~$(i, \sigma_i)$ such that~$i \le \sigma_i$. Define the \defn{excedance positions}~$\Epos(\sigma) \eqdef \set{i}{i \le \sigma_i}$ and \defn{values}~$\Eval(\sigma) \eqdef \set{\sigma_i}{i \le \sigma_i}$. The \defn{excedance relation} on~$\Ss_n$ is defined by~$\sigma \equiv \tau$ if~$\Epos(\sigma) = \Epos(\tau)$ and~$\Eval(\sigma) = \Eval(\tau)$. We denote by~$\Ss_n/{\equiv}$ the poset quotient on equivalence classes of~$\equiv$, defined by~$X \le Y$ if and only if there are~$x \in X$ and~$y \in Y$ such that~$x \le y$ in Bruhat order. \end{definition} \begin{definition}[\cite{BergeronGagnon}] \label{def:Clambda} For a NCP~$\lambda$ of~$[n]$, define the set of permutations \[ C_\lambda \eqdef \set{\sigma \in \Ss_n}{\Epos(\sigma) = [n] \ssm \lambda^- \text{ and } \Eval(\sigma) = [n] \ssm \lambda^+ }. \] \end{definition} \begin{theorem}[\cite{BergeronGagnon}] \label{thm:BG} For any~$n \in \N$, \begin{compactenum} \item For any~$\lambda \in \NCP_n$, the set~$C_\lambda$ is an interval~$[\sigma_\lambda, \tau_\lambda]$ of the Bruhat order on~$\Ss_n$, where the permutation~$\sigma_\lambda$ (resp.~$\tau_\sigma$) avoids the pattern~$321$ (resp.~$3412$). \item The map~$\lambda \mapsto C_\lambda$ is a bijection from the NCPs of~$[n]$ to the excedance classes of~$\Ss_n$. \item The quotient~$\Ss_n/{\equiv}$ is isomorphic to the Stanley lattice: $\lambda \le \mu \iff {C_\lambda \le C_\mu}$. \item Any choice of representatives of the excedance classes yields a basis of the Temperley--Lieb algebra~$\TL_n(2)$ (see \cref{subsec:TL} for details). \end{compactenum} \end{theorem} %%%%% \subsection{The excedance congruence on~$\ASM$} \label{subsec:excedanceCongruence} We now extend the excedance relation on permutations to a lattice congruence on~$\ASM_n$. For this, we consider the diagonal and the superdiagonal of the corresponding HFMs. \begin{definition} The \defn{excedance congruence} of~$\HFM_n$ is the equivalence relation~$\equiv$ defined by~$H \equiv H'$ if and only if~$H_{i,j} = H'_{i,j}$ for all~$0 \le i,j \le n$ with~$j-i \in \{0,1\}$. The \defn{excedance congruence} of~$\ASM_n$ is the corresponding equivalence relation~$\equiv$ on~$\ASM_n$. \end{definition} \begin{proposition} The excedance congruence on~$\ASM_n$ \begin{compactitem} \item is a lattice congruence (\ie $A \equiv A'$ and~$B \equiv B'$ $\Rightarrow$ $A \vee B \equiv A' \vee B'$ and $A \wedge B \equiv A' \wedge B'$), \item restricts to the excedance relation on~$\Ss_n$ (\ie $\sigma \equiv \tau \iff P_\sigma \equiv P_\tau$ for any ~$\sigma, \tau \in \Ss_n$). \end{compactitem} \end{proposition} We will now describe the classes of the excedance congruence. For this, we first associate to an ASM~$A$ the NCP~$\b{\lambda}(A)$ corresponding to the Dyck path whose height sequence is given by the diagonal and superdiagonal of the HFM corresponding to~$A$. See \cref{fig:ASM2NCP} for an illustration. % \begin{figure}[h] \centerline{ $\begin{pmatrix} \cdot & + & \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & + & \cdot \\ \cdot & \cdot & + & \cdot & \cdot & - & + \\ \cdot & \cdot & \cdot & \cdot & + & \cdot & \cdot \\ + & \cdot & - & + & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & + & \cdot \\ \cdot & \cdot & + & \cdot & \cdot & \cdot & \cdot \\ \end{pmatrix}$\quad $\begin{pmatrix} \color{red}\b{0} & \color{red}\b{1} & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & \color{red}\b{2} & \color{red}\b{1} & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & \color{red}\b{2} & \color{red}\b{3} & 4 & 5 & 4 & 5 \\ 3 & 4 & 3 & \color{red}\b{2} & \color{red}\b{3} & 4 & 5 & 4 \\ 4 & 5 & 4 & 3 & \color{red}\b{4} & \color{red}\b{3} & 4 & 3 \\ 5 & 4 & 3 & 4 & 3 & \color{red}\b{2} & \color{red}\b{3} & 2 \\ 6 & 5 & 4 & 5 & 4 & 3 & \color{red}\b{2} & \color{red}\b{1} \\ 7 & 6 & 5 & 4 & 3 & 2 & 1 & \color{red}\b{0} \\ \end{pmatrix}$\quad \raisebox{-2cm}{\includegraphics[scale=.95]{figures/DyckPathNonCrossingPartition}} } \caption{An ASM (left), its HFM (middle), its Dyck path (top right), and its NCP (bottom right).} \label{fig:ASM2NCP} \end{figure} The following are the analogues of \cref{def:Clambda,thm:BG}. \begin{definition} For~$\lambda \in \NCP_n$, we define~$D_\lambda \eqdef \set{A \in \ASM_n}{\b{\lambda}(A) = \lambda}$. \end{definition} \begin{theorem} \label{thm:excedence} \begin{compactenum} \item For any~$\lambda \in \NCP_n$, the set~$D_\lambda$ is an interval of~$\ASM_n$, whose maximum is the permutation matrix~$P_{\tau_\lambda}$, and we have~$C_\lambda = \set{\sigma \in \Ss_n}{P_\sigma \in D_\lambda}$. \item The map~$\lambda \mapsto D_\lambda$ is a bijection from the NCPs of~$[n]$ to the excedance classes of~$\ASM_n$. \item The lattice quotient~$\ASM_n/{\equiv}$ is isomorphic to the Stanley lattice: ${\lambda \le \mu \iff D_\lambda \le D_\mu}$. \end{compactenum} \end{theorem} The goal of this paper is to show that all properties of \cref{thm:BG} actually hold for any lattice quotient of~$\ASM_n$ isomorphic to~$\Dyck_n$. %%%%%%%%%%%%%%% \pagebreak \section{Catalan congruences of~$\ASM_n$} \label{sec:quotientsASMs} This section focuses on the following generalization of \cref{subsec:excedanceCongruence}. \begin{definition} A \defn{catalan congruence} is a congruence of the lattice~$\ASM_n$ on alternating sign matrices whose quotient is isomorphic to the Stanley lattice~$\Dyck_n$ on Dyck paths. \end{definition} In this section, we describe all catalan congruences and encode them bijectively using several combinatorial structures, in particular Gelfand--Tsetlin patterns and pipe dreams. %%%%% \subsection{Quotients of distributive lattices} \label{subsec:quotientsDistributiveLattices} Quotients of distributive lattices are distributive (by the definition of~$\vee$ and~$\wedge$ on~$\L/{\equiv}$), and behave properly with respect to Birkhoff's fundamental theorem of distributive lattices (\cref{thm:ftfdl}). Recall that we denote by~$j_\star$ the single element covered by a join irreducible~$j$. \begin{theorem} \label{thm:congruencesDistributiveLattices1} For a congruence~$\equiv$ on a distributive lattice~$\L$, denote by~$\JIrr(\equiv)$ the subposet of~$\JIrr(\L)$ induced by the join irreducibles~$j$ such that~$j \not\equiv j_\star$. Then \begin{compactitem} \item an element $x \in \L$ is minimal in its congruence class if and only if the corresponding antichain~$\jAnti(x)$ is contained in~$\JIrr(\equiv)$, \item the quotient~$\L/{\equiv}$ is isomorphic to the distributive lattice of lower sets of~$\JIrr(\equiv)$. \end{compactitem} Dual statements hold for meet irreducibles. \end{theorem} \begin{theorem}[\cite{Th50}] \label{thm:congruencesDistributiveLattices2} For two finite distributive lattices~$\L$ and~$\K$, the lattice congruences of~$\L$ whose quotients are isomorphic to~$\K$ are in bijection with the subposets of $\JIrr(\L)$ isomorphic~to~$\JIrr(\K)$. \end{theorem} %%%%% \subsection{Walls} \label{subsec:walls} We now specialize \cref{thm:congruencesDistributiveLattices2} to understand all catalan congruences of~$\ASM_n$. We have seen in \cref{sec:distributiveLattices} that $\JIrr(\ASM_n)$ is isomorphic to the tetrahedron poset~$\TPoset_n$, and~$\JIrr(\Dyck_n)$ is isomorphic to the triangular poset~$\DPoset_n$. Hence quotients of $\ASM_n$ isomorphic to $\Dyck_n$ are in bijection with subposets of~$\TPoset_n$ isomorphic to~$\DPoset_n$. We now show that this isomorphism always factorizes through the projection $(x_1, x_2, x_3, x_4) \mapsto (x_1, x_2+x_3, x_4)$ of~$\TPoset_n$. \begin{proposition} \label{prop:walls} Let $\P$ be a subposet of the tetrahedron poset~$\TPoset_n$ isomorphic to the triangular poset~$\DPoset_n$. For any~$(y_1, y_2, y_3)\in \DPoset_n$, the subposet~$\P$ contains exactly one element $(x_1, x_2, x_3, x_4)$ such that $x_1 = y_1$ and $x_4 = y_3$ (and thus~$x_2+x_3 = y_2$). \end{proposition} In other words, \cref{prop:walls} states that the subposets of~$\TPoset_n$ isomorphic to~$\DPoset_n$ can be seen as vertical (possibly undulating) sections of~$\TPoset_n$, which motivates the following. \begin{definition} A \defn{wall} of order~$n$ is a subposet of~$\TPoset_n$ isomorphic to~$\DPoset_n$. \end{definition} \begin{example} \label{exm:excedanceQuotientWall} The \defn{excedance quotient} defined in~\cref{subsec:excedanceCongruence} is given by the \defn{undulating wall} \( \set{(x_1,x_2,x_3,x_4) \in \TPoset_n}{x_3-x_2 \in \{0,-1\}}. \) \end{example} %%%%% \pagebreak \subsection{Depth triangles, catalan triangles, and bicolored pipe dreams} \label{subsec:depthTrianglesCatalanTrianglesBicoloredPipeDreams} For any wall $\P\subset \TPoset_n$, the projection~$(x_1,x_2,x_3,x_4) \mapsto (x_1,x_2+x_3,x_4)$ is a bijection from $\P$ to $\DPoset_n$ by \cref{prop:walls}. We can therefore encode the wall~$\P$ by recording the depth~$x_3-x_2$ of the point~$(x_1,x_2,x_3,x_4)$ in the direction of the projection. See \cref{fig:catalanTriangle}. We now characterize the triangular arrays obtained this way, transform them to certain Gelfand--Tsetlin patterns by an appropriate shift, and connect them to pipe dreams. \begin{definition} \label{def:depthTriangle} A \defn{depth triangle} of order~$n$ is a map~$\delta : \DPoset_n \to \mathbb Z$ such that \begin{compactitem} \item the bottom row is~$0 0 \cdots 0$, that is, $\delta(i, 0, n-2-i) = 0$ for all~$0 \le i \le n-2$, \item $|\delta(y_1, y_2, y_3) - \delta(y_1, y_2-1, y_3+1)| = 1 = |\delta(y_1, y_2, y_3) - \delta(y_1+1, y_2-1, y_3)|$. \end{compactitem} Note that a depth triangle of order~$n$ has~$n-1$ rows (or diagonals). See \cref{fig:depthTriangles}. % \begin{figure}[H] \centering \setlength{\tabcolsep}{1.1pt} \begin{tabular}{ccccc} & & $\!\!-2\!\!$ & & \\ & $\!\!-1\!\!$ & & $\!\!-1\!\!$ & \\ $0$ & & $0$ & & $0$ \end{tabular} \qquad \begin{tabular}{ccccc} & & $0$ & & \\ & $\!\!-1\!\!$ & & $\!\!-1\!\!$ & \\ $0$ & & $0$ & & $0$ \end{tabular} \qquad \begin{tabular}{ccccc} & & $0$ & & \\ & $1$ & & $\!\!-1\!\!$ & \\ $0$ & & $0$ & & $0$ \end{tabular} \qquad \begin{tabular}{ccccc} & & $0$ & & \\ & $\!\!-1\!\!$ & & $1$ & \\ $0$ & & $0$ & & $0$ \end{tabular} \qquad \begin{tabular}{ccccc} & & $0$ & & \\ & $1$ & & $1$ & \\ $0$ & & $0$ & & $0$ \end{tabular} \qquad \begin{tabular}{ccccc} & & $2$ & & \\ & $1$ & & $1$ & \\ $0$ & & $0$ & & $0$ \end{tabular} \caption{The $6$ depth triangles of order $4$.} \label{fig:depthTriangles} \end{figure} \end{definition} \begin{definition} \label{def:catalanTriangle} A \defn{Gelfand--Tsetlin pattern} of order~$n$ is a map~$\gamma : \DPoset_n \to \N$ such that $\gamma(y_1, y_2-1, y_3+1) \le \gamma(y_1, y_2, y_3) \le \gamma(y_1+1, y_2-1, y_3)$. We say that~$\gamma$ is \defn{doubly gapless} if $\gamma(y_1, y_2, y_3) - \gamma(y_1, y_2-1, y_3+1) \le 1$ and~${\gamma(y_1+1, y_2-1, y_3) - \gamma(y_1, y_2, y_3) \le 1}$. A \defn{catalan triangle} of order~$n$ is a doubly gapless Gelfand--Tsetlin pattern with bottom row $1 2 \cdots (n-1)$. Again, note that a catalan triangle of order~$n$ has~$n-1$ rows (or diagonals). See \cref{fig:catalanTriangles}. % \begin{figure}[H] \centering \setlength{\tabcolsep}{1.1pt} \begin{tabular}{ccccc} & & $1$ & & \\ & $1$ & & $2$ & \\ $1$ & & $2$ & & $3$ \end{tabular}\qquad \begin{tabular}{ccccc} & & $2$ & & \\ & $1$ & & $2$ & \\ $1$ & & $2$ & & $3$ \end{tabular}\qquad \begin{tabular}{ccccc} & & $2$ & & \\ & $2$ & & $2$ & \\ $1$ & & $2$ & & $3$ \end{tabular}\qquad \begin{tabular}{ccccc} & & $2$ & & \\ & $1$ & & $3$ & \\ $1$ & & $2$ & & $3$ \end{tabular}\qquad \begin{tabular}{ccccc} & & $2$ & & \\ & $2$ & & $3$ & \\ $1$ & & $2$ & & $3$ \end{tabular}\qquad \begin{tabular}{ccccc} & & $3$ & & \\ & $2$ & & $3$ & \\ $1$ & & $2$ & & $3$ \end{tabular} \caption{The $6$ catalan triangles of order $4$.} \label{fig:catalanTriangles} \end{figure} \end{definition} \begin{definition} \label{def:bicoloredPipeDream} A \defn{pipe dream}~$P$ is a filling of a triangular shape with crossings~\cross{} and contacts~\elbow{} so that all pipes entering on the left side exit on the top side~\cite{BergeronBilley, KnutsonMiller-GroebnerGeometry}. A \defn{bicolored pipe dream} is a pipe dream whose pipes are colored red or blue so that each contact is bichromatic. Note that there is no color restriction on the crossings: they are allowed to be both monocolor or bicolor. See \cref{fig:bicoloredPipeDreams}. % \begin{figure}[H] \centering \includegraphics[scale=.5]{figures/pipeDreamBiColor1} \qquad \includegraphics[scale=.5]{figures/pipeDreamBiColor2} \qquad \includegraphics[scale=.5]{figures/pipeDreamBiColor3} \qquad \includegraphics[scale=.5]{figures/pipeDreamBiColor4} \qquad \includegraphics[scale=.5]{figures/pipeDreamBiColor5} \qquad \includegraphics[scale=.5]{figures/pipeDreamBiColor6} \caption{The $6$ bicolored pipe dreams with $2$ pipes.} \label{fig:bicoloredPipeDreams} \end{figure} \end{definition} The following statement is illustrated in \cref{fig:catalanTriangle}. \begin{figure} \centerline{ \raisebox{-2cm}{\includegraphics[scale=.5]{figures/catalanTriangle}} \quad \setlength{\tabcolsep}{1.1pt} \begin{tabular}{ccccccc} & & & $\!\!-1\!\!$ & & & \\ & & $0$ & & $0$ & & \\ & $\!\!-1\!\!$ & & $1$ & & $\!\!-1\!\!$ & \\ $0$ & & $0$ & & $0$ & & $0$ \end{tabular}$$ \qquad \begin{tabular}{ccccccc} & & & $2$ & & & \\ & & $2$ & & $3$ & & \\ & $1$ & & $3$ & & $3$ & \\ $1$ & & $2$ & & $3$ & & $4$ \end{tabular}$$ \qquad \raisebox{-.6cm}{\includegraphics[scale=.5]{figures/pipeDreamBiColor}} } \caption{A subposet of $\TPoset_5$ isomorphic to $\DPoset_5$ (left) and its corresponding depth triangle (middle left), catalan triangle (middle right), and bicolored pipe dream (right).} \label{fig:catalanTriangle} \end{figure} \begin{theorem} \label{thm:depthTrianglesCatalanTrianglesBicoloredPipeDreams} The catalan congruences of~$\ASM_n$ are in bijection with walls of order~$n$, depth triangles of order~$n$, catalan triangles of order~$n$, and bicolored pipe dreams with~$n-2$~pipes. \end{theorem} \begin{example} \label{exm:excedanceQuotientDepth} Following~\cref{exm:excedanceQuotientWall}, for the excedance quotient of \cref{subsec:excedanceCongruence}, \begin{compactitem} \item the depth triangle is given by~$\delta(y_1, y_2, y_3) = 2 \lfloor y_2/2 \rfloor - y_2 = - (y_2 \mod 2)$ (in other words, odd rows are~$0$ while even rows are~$-1$) \item the catalan triangle is given by~$\gamma(y_1, y_2, y_3) = y_1 + \lfloor y_2/2 \rfloor + 1$. \item the bicolored pipe dream is the pipe dream with no crossing (hence waving pipes alternating colors), whose longest pipe is blue. \end{compactitem} \end{example} %%%%% \subsection{The lattice of catalan triangles} \label{subsec:latticeCatalanTriangles} Finally, we note that the set of catalan triangles carries itself a natural distributive lattice structure. \begin{proposition} \label{prop:latticeCatalanTriangles} The set of catalan triangles of order $n$ ordered by coordinatewise comparison forms a distributive lattice~$\Cat_n$, whose join-irreducibles poset is isomorphic to the poset of quadruples $(x_1,x_2,x_3,x_4)\in \N^4$ with $x_1+x_2+x_3+x_4=n-2$, ordered by $\mathbf x\le \mathbf y$ if and only if $x_2+x_3+x_4\le y_2+y_3+y_4$, $x_2+x_4\le y_2+y_4$, $x_3+x_4\le y_3+y_4$ and $x_4\le y_4$. \end{proposition} \begin{remark} \label{rem:latticeDepthTriangles} By \cref{thm:depthTrianglesCatalanTrianglesBicoloredPipeDreams}, \cref{prop:latticeCatalanTriangles} also translates to the depth triangles of \cref{def:depthTriangle} and the bicolored pipe dreams of \cref{def:bicoloredPipeDream}. \end{remark} \begin{remark} The lattice~$\Cat_n$ has an automorphism corresponding to the diagonal reflection of pipe dreams and an anti-automorphism corresponding to color exchange of pipe dreams. \end{remark} \begin{example} \label{exm:minMaxCatalanTriangle} The minimum (resp.~maximum) depth triangles, catalan triangles, and bicolored pipe dreams are given by: \begin{compactitem} \item $\delta_{\min}(y_1,y_2,y_3) = -y_2$ (resp.~$\delta_{\max}(y_1,y_2,y_3) = y_2$), \item $\gamma_{\min}(y_1,y_2,y_3) = y_1+1$ (resp.~$\gamma_{\max}(y_1,y_2,y_3) = y_1+y_2+1 = n-1-y_3$), \item the completely red (resp.~blue) pipe dreams with only crossings. \end{compactitem} \end{example} %%%%%%%%%%%%%%% \pagebreak \section{Properties of catalan congruences} \label{sec:properties} %%%%% \subsection{Maxima of classes and covexillary permutations} \label{subsec:maxima} We now describe the maxima of the classes of catalan congruences of~$\ASM_n$. \begin{theorem} \label{thm:covexillary} The following assertions are equivalent for an ASM~$A$ of order~$n$: \begin{compactenum}[(i)] \item $A$ is a covexillary permutation matrix (\ie avoiding the pattern~$3412$), \item there exists a wall of order~$n$ containing all meet irreducibles of~$\mAnti(A)$, \item there exists a catalan congruence of~$\ASM_n$ such that~$A$ is maximal in its class. \end{compactenum} \end{theorem} \begin{example} \label{exm:dominant} Following \cref{exm:minMaxCatalanTriangle}, the maxima of the classes of the congruence \mbox{corresponding} to the minimal (resp.~maximum) catalan triangle are the $231$ (resp.~$312$) \mbox{avoiding permutations}. \end{example} %%%%% \subsection{Minimal permutations in classes and $321$ avoidance} \label{subsec:minimalPermutations} We now describe the minimal permutations in classes of catalan congruences of~$\ASM_n$. In contrast to~\cref{subsec:maxima}, the minimum of the classes are not necessarily permutations. However, it turns out that each class contains a minimal permutation. \begin{proposition} \label{prop:minimalPermutation} Let~$\equiv$ be a catalan congruence on~$\ASM_n$. Let $\sigma\in \Ss_n$ containing the pattern~$321$, and let~$i \sigma(j) > \sigma(k)}$. Then at least one of the permutations $\sigma \circ (i,j)$ and $\sigma \circ (j,k)$ is congruent to $\sigma$. Moreover, if both are, then $\sigma\circ (i,k)$ is also congruent to $\sigma$. \end{proposition} \begin{theorem} \label{thm:minimalPermutation} For a catalan congruence on~$\ASM_n$, \begin{compactitem} \item each class contains a unique minimal permutation, \item the minimal permutations of the classes are precisely the $321$-avoiding permutations. \end{compactitem} \end{theorem} %%%%% \subsection{Bases of the Temperley--Lieb algebra} \label{subsec:TL} Extending the work of N.~Bergeron and L.~Gagnon~\cite{BergeronGagnon}, we finally construct various bases of the Temperley--Lieb algebra~$\TL_n(2)$ using the catalan congruences studied in \cref{sec:quotientsASMs}. Recall that, for~$q \in \C$, the \defn{Temperley--Lieb algebra}~$\TL_n(q)$ is the $\C$-algebra generated by~$e_1, \dots, e_{n-1}$ subject to the \defn{Jones relations} \begin{alignat*}{6} e_i^2 & = q e_i & \quad & \text{for~$i \in [n-1]$,} \qquad & e_i e_{i+1} e_i & = e_i & \quad & \text{for~$i \in [n-2]$,} \\ e_{i+1} e_i e_{i+1} & = e_{i+1} & \quad & \text{for~$i \in [n-2]$,} \qquad & e_i e_j & = e_j e_i & \quad & \text{for~$i,j \in [n-1]$ with~$|i-j| \ne 1$.} \end{alignat*} It is well known that the set~$T_n$ of $321$-avoiding permutations of~$[n]$ forms a basis of~$\TL_n(2)$. This was extended to \cref{thm:BG}\,(4) in~\cite{BergeronGagnon}. We extend their result to our catalan congruences of~$\ASM_n$. \begin{theorem} Any choice of representative permutations in the congruence classes of any catalan congruence on $\ASM_n$ forms a basis of~$\TL_n(2)$. \end{theorem} %%%%%%%%%%%%%%% %% if you use biblatex then this generates the bibliography %% if you use some other method then remove this and do it your own way \pagebreak \printbibliography \end{document}