%% 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[finalversion]{FPSAC2023}
\articlenumber{58}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{tikz}
\usepackage{multirow}
\usepackage{paralist}
\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio2.bib}

%tiks instructions for pipe dreams
\tikzstyle boundaries=[color=gray, very thin]
\tikzstyle entrance path=[color=black, very thick]
\tikzstyle pipes=[very thick, rounded corners=5pt]

%\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{algo}[theorem]{Algorithm}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{nota}[theorem]{Notation}
\newtheorem{conj}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{ex}{Example}[section]
\newtheorem{rem}[theorem]{Remark}

%newcommands
\DeclareMathOperator{\lin}{lin}
\DeclareMathOperator{\SC}{SC}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\cone}{Cone}
\DeclareMathOperator{\vect}{Vect}
\DeclareMathOperator{\ninv}{ninv}
\DeclareMathOperator{\ins}{ins}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\SCA}{SC^a}

% math special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\K}{\mathbb{K}} % field
\newcommand{\I}{\mathbb{I}} % set of integers
\newcommand{\C}{\mathbb{C}} % set of summands
\newcommand{\fS}{\mathfrak{S}} % symmetric group
\newcommand{\fP}{\mathfrak{P}} % ordered partition
\newcommand{\cC}{\mathcal{C}} % collection
\newcommand{\Fn}{\mathfrak{F}}

\newcommand{\less}{\vartriangleleft} % smaller WOIP
\newcommand{\more}{\vartriangleright} % larger WOIP
\newcommand{\lesse}{\preceq}
\newcommand{\moree}{\succeq}
\newcommand{\pos}{^{-1}}
\newcommand{\lessac}{\preceq}
\newcommand{\moreac}{\succeq}

\renewcommand{\labelitemi}{•}

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\newcommand{\cross}{\begin{tikzpicture}[scale=0.3] \draw[pipes] (0.5,0) -- (0.5,1); \draw[pipes] (0,0.5) -- (1,0.5); \end{tikzpicture}}
\newcommand{\elbow}{\begin{tikzpicture}[scale=0.3] \draw[pipes] (0.5,0) -- (0.5,0.5) -- (1,0.5); \draw[pipes] (0,0.5) -- (0.5,0.5) -- (0.5,1); \end{tikzpicture}}

% functions on pipe dreams
\newcommand{\contact}{^\#} % contact graph
\newcommand{\econtact}[1]{#1^\natural}
\newcommand{\pstart}[1]{\mathcal{S}_{#1}}
\newcommand{\pend}[1]{\mathcal{E}_{#1}}
\newcommand{\duality}{^\star} % dual
\newcommand{\pathh}[1]{\mathcal{#1}}

%functions on subword complexes
\newcommand{\rf}{\mathrm{r}}
\newcommand{\rc}{\mathrm{R}}

%% define your title in the usual way
\title{Acyclic pipe dreams, subword complexes and lattice quotients of weak order intervals}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Noémie Cartier\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Laboratoire Interdisciplinaire des Sciences du Numérique -- UMR CNRS 9015, Université Paris-Saclay, CNRS, Orsay, France}

%% 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{The Tamari lattice is a well-known quotient of the weak order on permutations, and can be realized as the increasing flip poset of a family of pipe dreams with a well-chosen exit permutation. We show that for any permutation~$\omega$, the increasing flip poset on acyclic pipe dreams with exit permutation~$\omega$ is a lattice quotient of the interval~$[\id, \omega]$ of the weak order. We then give similar quotients on acyclic pipe dreams on a family of non-triangular shapes. We finally discuss conjectural generalizations of these results to acyclic facets of subword complexes on any finite Coxeter group.}
%% put your French abstract here, or comment this out if you don't have one
\resume{Le treillis de Tamari est un quotient bien connu de l'ordre faible sur les permutations, et il peut être réalisé comme l'ordre des flips croissants sur une famille d'arrangements de tuyaux de permutation de sortie bien choisie. Nous montrons que pour toute permutation~$\omega$, l'ordre des flips croissants sur les arrangements de tuyaux acycliques de permutation de sortie~$\omega$ est un quotient de treillis de l'intervalle~$[\id, \omega]$ de l'ordre faible. Nous donnons ensuite des quotients similaires sur des arrangements de tuyaux acycliques sur une famille de formes non triangulaires. Nous discutons finalement des généralisations conjecturales de ces résultats aux facettes acycliques de complexes de sous-mots sur des groupes de Coxeter finis quelconques.}

%Le treillis de Tamari est connu pour être un quotient de l'ordre faible faible sur les permutations, et il peut être réalisé comme le poset des flips sur les arrangements de tuyaux avec une permutation de sortie bien choisie. Nous généralisons ce résultat et utilisons d'autres familles d'arrangements de tuyaux pour obtenir des quotients de treillis d'intervalles de l'ordre faible. Nous proposons une généralisation possible à l'ordre faible sur des groupes de Coxeter finis.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{weak order, Tamari lattice, lattice quotient, pipe dream, subword complex}

%% 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

%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction} \label{sec:intro}

A \emph{triangular pipe dream} is a filling of a triangular shape with crosses \cross{} and contacts \elbow{} so that all pipes entering on the left side exit on the top side, as illustrated in \cref{ex:triangular_pipe_dream}. We will only consider \emph{reduced} pipe dreams, where two pipes have at most one crossing. The pipes are labeled from~1 to~$n$ on the left size from top to bottom. For a pipe dream~$P$ with~$n$ pipes, its \emph{exit permutation} is the order in which the pipes exit the shape at the top, read from left to right. For a fixed permutation~$\omega \in \fS_n$, we denote by~$\Pi(\omega)$ the set of reduced pipe dreams with exit permutation~$\omega$.

A contact~$c$ on a pipe dream~$P$ is \emph{flippable} if the two pipes passing through~$c$ have a crossing~$x$. The \emph{flip} on~$c$ exchange the contact~$c$ with the crossing~$x$ to obtain a pipe dream with the same exit permutation as~$P$, as illustrated in \cref{ex:triangular_pipe_dream}. The flip is \emph{increasing} if~$c$ is north-east of~$x$ and \emph{decreasing} otherwise. The \emph{increasing flip graph} is the graph on~$\Pi(\omega)$ with an arc from~$P$ to~$P'$ if we can obtain~$P'$ by doing an increasing flip on~$P$. The \emph{increasing flip order} is the reflexive and transitive closure of the increasing flip graph.

Several authors \cite{Woo, PilaudPocchiola, Stump} have observed that the set~$\Pi(1 \: n \: (n-1) \: \ldots \: 3 \: 2)$ is counted by the Catalan number~$C_{n-1}$. Moreover, the increasing flip graph on this set is isomorphic to the Hasse diagram of the Tamari lattice. 
 Since there exists a simple lattice isomorphism from binary trees with~$n-1$ nodes to those pipe dreams and a surjective lattice morphism from the weak order on~$\fS_{n-1}$ to binary trees, we can combine them to obtain a lattice morphism from~$\fS_{n-1}$ to~$\Pi(1 \: n \: (n-1) \: \ldots \: 3 \: 2)$. The increasing flip order in this particular case is therefore a quotient of the weak order on permutations. In this paper, we discuss several extensions of this result obtained by changing the exit permutation, the shapes of pipes dreams, and even the group on which they are defined.
 
In \cref{sec:triangular}, we will first study the triangular pipe dreams with any fixed exit permutation. We will prove in \cref{thm:triangular_morphism} that for any permutation~$\omega$, the increasing flip graph on acyclic pipe dreams with exit permutation~$\omega$ is a lattice quotient of the weak order interval~$[\id, \omega]$. We will give a lattice morphism from this interval to the acyclic pipe dreams and several ways to compute the image of a permutation.

Then in \cref{sec:typeA}, we will consider pipe dreams on non-triangular shapes and discuss what hypothesis need to be modified to obtain a similar theorem, given in \cref{thm:typeA_morphism}.  We will see that the quotient may sometimes be realized on a subset of acyclic pipe dreams and may not use all of the increasing flip graph, but that it is linked to the brick polyhedron, an object introduced on spherical subword complexes in \cite{PilaudStump-brickPolytope} and generalized to any subword complex in \cite{JahnStump}.

Finally, as pipe dreams can be interpreted as the facets of some subword complexes in type A Coxeter groups, we will discuss in \cref{sec:Coxeter} how those results can be generalized to subword complexes in any finite Coxeter group and give a conjecture that has been extensively tested in this context in \cref{conj:Coxeter_morphism}.

The details and proofs omitted in this extended abstract will soon be available in two articles in preparation \cite{CartierPilaud, Cartier}. I am grateful to Nantel Bergeron, Cesar Ceballos and Vincent Pilaud for allowing me to use the results of \cite{CartierPilaud} here.

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1.2cm]
\fill[yellow] (0,-2) rectangle (1,-1) rectangle (2,0);
\draw[boundaries] (0,0); 
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5); 
\draw[pipes, color=black] (0.0,-0.5) node[left] {1} -- (0.5,-0.5) -- (0.5,0.0) node[above] {1};
\draw[pipes, color=red] (0.0,-1.5) node[left] {2} -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0) node[above] {2};
\draw[pipes, color=orange] (0.0,-2.5) node[left] {3} -- (0.5,-2.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0) node[above] {3};
\draw[pipes, color=green] (0.0,-3.5) node[left] {4} -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.0) node[above] {4};
\draw[pipes, color=blue] (0.0,-4.5) node[left] {5} -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (1.5,0.0) node[above] {5};
\node[black, scale=0.7, inner sep=1, outer sep=1] (1) at (-2, 0) {1};
\node[red, scale=0.7, inner sep=1, outer sep=1] (2) at (-2,-1.25) {2};
\node[orange, scale=0.7, inner sep=1, outer sep=1] (3) at (-2, -2.5) {3};
\node[green, scale=0.7, inner sep=1, outer sep=1] (4) at (-2,-3.75) {4};
\node[blue, scale=0.7, inner sep=1, outer sep=1] (5) at (-2, -5) {5};
\draw[->] (4) to (3);
\draw[->] (1) to (2);
\draw[->] (2) to [bend right=30] (5);
\draw[->] (5) to (4);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1.2cm]
\fill[yellow] (0,-2) rectangle (1,-1) rectangle (2,0);
\node[black, scale=0.7, inner sep=1, outer sep=1] (1) at (7, 0) {1};
\node[red, scale=0.7, inner sep=1, outer sep=1] (2) at (7,-1.25) {2};
\node[orange, scale=0.7, inner sep=1, outer sep=1] (3) at (7, -2.5) {3};
\node[green, scale=0.7, inner sep=1, outer sep=1] (4) at (7,-3.75) {4};
\node[blue, scale=0.7, inner sep=1, outer sep=1] (5) at (7, -5) {5};
\draw[->] (4) to (3);
\draw[->] (1) to [bend left=45] (5);
\draw[->] (5) to [bend left=30] (2);
\draw[->] (2) to [bend left=30] (4);
\draw[boundaries] (0,0); 
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5); 
\draw[pipes, color=black] (0.0,-0.5) node[left] {1} -- (0.5,-0.5) -- (0.5,0.0) node[above] {1};
\draw[pipes, color=red] (0.0,-1.5) node[left] {2} -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0) node[above] {2};
\draw[pipes, color=orange] (0.0,-2.5) node[left] {3} -- (0.5,-2.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0) node[above] {3};
\draw[pipes, color=green] (0.0,-3.5) node[left] {4} -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.0) node[above] {4};
\draw[pipes, color=blue] (0.0,-4.5) node[left] {5} -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0) node[above] {5};
\end{tikzpicture}
\caption{An increasing flip between two triangular pipe dreams with exit permutation~$15432$ and their contact graphs.}
\label{ex:triangular_pipe_dream}
\end{center}
\end{figure}

\section{Triangular pipe dreams} \label{sec:triangular}

We defined triangular pipe dreams and their flips in the introduction. The \emph{contact graph} of a pipe dream~$P$ is the directed graph~$P\contact$ that has a vertex for each pipe of~$P$ and contains the edges~$(a,b)$ if and only if a contact
\begin{tikzpicture}[scale=0.5, baseline=4pt]
\draw[pipes,red] (0,0.5) node[left] {a} -- (0.5,0.5) -- (0.5,1);
\draw[pipes,blue] (0.5, 0) -- (0.5,0.5) -- (1,0.5) node[right] {b};
\end{tikzpicture}
appears somewhere in~$P$ (see two examples in \cref{ex:triangular_pipe_dream}). 
We say that~$P$ is \emph{acyclic} if and only if its contact graph is acyclic, and in that case we denote by~$\lin(P)$ the linear extensions of its contact graph~$P\contact$. For any permutation~$\omega \in \fS_n$ we denote by~$\Sigma(\omega)$ the set of acyclic pipe dreams with exit permutation~$\omega$.
Our first result deals with these sets of linear extensions of pipe dreams.

\begin{theorem}\label{thm:triangular_partition}
The set~$\{ \lin(P) \mid P \in \Sigma(\omega) \}$ is a partition of the weak order interval~$[\id, \omega]$.
\end{theorem}

This partition defines an equivalence relation~$\equiv_\omega$ on~$[\id, \omega]$ with an equivalence class~$\lin(P)$ for each~$P \in \Sigma(\omega)$.

For instance, consider the exit permutation~$\omega = 1 \: n \: (n-1) \: \ldots \: 3 \: 2$. 
Then the interval~$[\id, \omega]$, i.e the set of all permutations in~$\fS_n$ starting with~1, is isomorphic for the weak order to~$\fS_{n-1}$ via the map~$\phi: \sigma \in \fS_{n-1} \mapsto 1 \: (\sigma(1) +1) \: \ldots (\sigma(n-1) + 1) \in [\id, \omega]$. 
Moreover, the contact graph of a pipe dream of ${\Pi(\omega)}$ is a binary search tree on~$\{2, \dots, n\}$ and with an additional node~$1$ pointing to the root.
Hence, the relation~$\equiv_\omega$ is the image by~$\phi$ of the sylvester congruence defined in \cite{HivertNovelliThibon-algebraBinarySearchTrees}, whose classes are linear extensions of standard binary search trees. This congruence is also the transitive closure of the rewriting rule~$UijV \equiv UjiV$ if and only if~$U$ contains a letter~$k$ such that~$i < k < j$, with~$U$ and~$V$ (possibly empty) words on~$[n]$ and~$i<j$ integers, and the following theorem gives a similar alternate definition of~$\equiv_\omega$ for any permutation.

\begin{theorem}\label{thm:triangular_rewriting}
The equivalence relation~$\equiv_\omega$ is the transitive closure of the rewriting rule saying that for any weak order cover~$UijV \lessdot UjiV$ in~$[\id, \omega]$, then~$UijV \equiv_\omega UjiV$ if and only if
\[
| \{ k < i \mid \omega\pos(k) < \omega\pos(j) \} | \quad \leqslant \quad | \{ k \in U \mid i < k < j \text{ and } \omega\pos(j) < \omega\pos(k) < \omega\pos(i) \} |
\]
\end{theorem}

A \emph{congruence} of a lattice~$(L, \leqslant, \wedge, \vee)$ is an equivalence relation~$\equiv$ on~$L$ which respects meets and joins: if~$x \equiv x'$ and~$y \equiv y'$, then~$x \wedge y \equiv x' \wedge y'$ and~$x \vee y \equiv x' \vee y'$. In that case, the \emph{lattice quotient}~$L / \equiv$ is the lattice on the classes of~$\equiv$ where for any two classes~$X$ and~$Y$, we have~$X \leqslant Y$ if and only if there exist~$x \in X$ and~$y \in Y$ such that~$x \leqslant y$ \cite{Reading-CambrianLattices}. As the sylvester congruence is a lattice congruence, and the Tamari lattice is the associated lattice quotient of the weak order, it is natural to study the same properties on~$\equiv_\omega$ for any permutation~$\omega$.

\begin{theorem}\label{thm:triangular_congruence}
For any permutation~$\omega$, the equivalence relation~$\equiv_\omega$ is a lattice congruence of the weak order interval~$[\id, \omega]$.
\end{theorem}

\cref{thm:triangular_partition} also allows us to define a map~$\ins_\omega: [\id, \omega] \mapsto \Sigma(\omega)$ such that for any~${\pi \in [\id, \omega]}$, the permutation~$\pi$ is a linear extension of the contact graph of~$\ins_\omega(\pi)$. We note that~$\ins_\omega(\id)$ is the unique source of the increasing flip graph on~$\Pi(\omega)$, \linebreak and~$\ins_\omega(\omega)$ is its unique sink. The fibers of the map~$\ins_\omega$ are the equivalence classes of the congruence~$\equiv_\omega$.

When~$w = 1 \: n \: (n-1) \: \ldots \: 3 \: 2$, the image~$\ins_\omega(\pi)$ can be computed by iterated insertions in a binary search tree as described in~\cite{HivertNovelliThibon-algebraBinarySearchTrees}.
For general~$w$, there are two known algorithms to compute~$\ins_\omega(\pi)$ for any~$\pi \leqslant \omega$: the sweeping algorithm, which fill the cells of the triangular shape one by one, and the insertion algorithm, which adds the pipes to the pipe dream one by one.

\begin{algo}\label{algo:triangular_sweeping}
The \emph{sweeping algorithm} on triangular pipe dreams, illustrated in \cref{ex:triangular_sweeping}, computes~$\ins_\omega(\pi)$ by filling the cells of the triangular shape from south-west to north-east with contacts and crosses as follows. We denote by~$i$ the pipe entering the current cell from the west side and by~$j$ the one entering from the south side, and we fill the cell with a cross if and only if
\begin{compactitem}
\item $i < j$ and~$\omega\pos(i) > \omega\pos(j)$ and
\item $\pi\pos(i) > \pi\pos(j)$ or the current cell lies in column~$\omega\pos(j)$.
\end{compactitem}

%\begin{compactitem}
%\item if~$\omega\pos(i) < \omega\pos(j)$, then the cell contains an elbow \begin{tikzpicture}[scale=0.3]
%\draw[pipes,red] (0,0.5) node[left, scale=0.7] {i} -- (0.5,0.5) -- (0.5,1);
%\draw[pipes,blue] (0.5, 0) -- (0.5,0.5) -- (1,0.5) node[right, scale=0.7] {j};
%\end{tikzpicture};
%\item else, if~$\pi\pos(j) < \pi\pos(i)$, then the cell contains a cross \begin{tikzpicture}[scale=0.3]
%\draw[pipes,red] (0,0.5) node[left, scale=0.7] {i} -- (1,0.5);
%\draw[pipes,blue] (0.5, 0) -- (0.5,1) node[right, scale=0.7] {j};
%\end{tikzpicture};
%\item else, if the cell is in the exit column~$\omega\pos(j)$ of pipe~$j$, the cell contains a cross
%\begin{tikzpicture}[scale=0.3]
%\draw[pipes,red] (0,0.5) node[left, scale=0.7] {i} -- (1,0.5);
%\draw[pipes,blue] (0.5, 0) -- (0.5,1) node[right, scale=0.7] {j};
%\end{tikzpicture}
% and otherwise it contains an elbow \begin{tikzpicture}[scale=0.3]
%\draw[pipes,red] (0,0.5) node[left, scale=0.7] {i} -- (0.5,0.5) -- (0.5,1);
%\draw[pipes,blue] (0.5, 0) -- (0.5,0.5) -- (1,0.5) node[right, scale=0.7] {j};
%\end{tikzpicture}.
%\end{compactitem}
\end{algo}

\begin{algo}\label{algo:triangular_insertion}
The \emph{insertion algorithm} on triangular pipe dreams, illustrated in \cref{ex:triangular_insertion}, computes~$\ins_\omega(\pi)$ by drawing the pipes of the pipe dream one by one in order of~$\pi$. At step~$t$, we draw pipe~$\pi(t)$ starting in row~$\pi(t)$, ending in column~$\omega\pos(\pi(t))$ and covering with its south-to-east elbows \begin{tikzpicture}[scale=0.3] \draw[pipes] (0.5,0) -- (0.5,0.5) -- (1,0.5); \end{tikzpicture} the west-to-north free elbows  \begin{tikzpicture}[scale=0.3] \draw[pipes] (0,0.5) -- (0.5,0.5) -- (0.5,1); \end{tikzpicture} in the rectangle between those two points.
\end{algo}

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-4);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-3);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-3);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=orange] (0.0,-2.5) -- (1,-2.5);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-3);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-2);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=red] (0.0,-1.5) -- (1,-1.5);
\draw[pipes, color=orange] (0.0,-2.5) -- (1,-2.5);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-3);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-1);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (1,-1.5);
\draw[pipes, color=orange] (0.0,-2.5) -- (1,-2.5);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-3);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-0.5) -- (1,-0.5);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (1,-1.5);
\draw[pipes, color=orange] (0.0,-2.5) -- (2.5,-2.5) -- (2.5, -2);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-0.5) -- (1,-0.5);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (1.5,-1.5) -- (1.5, -1);
\draw[pipes, color=orange] (0.0,-2.5) -- (2.5,-2.5) -- (2.5, -2);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-1.5) -- (2, -1.5);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-0.5) -- (1,-0.5);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (1.5,-1.5) -- (1.5, -.5) -- (2, -.5);
\draw[pipes, color=orange] (0.0,-2.5) -- (2.5,-2.5) -- (2.5, -2);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-1.5) -- (2, -1.5);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (1.5,-1.5) -- (1.5, -.5) -- (2, -.5);
\draw[pipes, color=orange] (0.0,-2.5) -- (2.5,-2.5) -- (2.5, -1.5) -- (3.5, -1.5) -- (3.5, -1);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-1.5) -- (2.5, -1.5) -- (2.5, -1);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (1.5,-1.5) -- (1.5, -.5) -- (3, -.5);
\draw[pipes, color=orange] (0.0,-2.5) -- (2.5,-2.5) -- (2.5, -1.5) -- (3.5, -1.5) -- (3.5, -1);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-1.5) -- (2.5, -1.5) -- (2.5, 0);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\node[black, left] at (0, -.5) {1};
\node[red, left] at (0, -1.5) {2};
\node[orange, left] at (0, -2.5) {3};
\node[green, left] at (0, -3.5) {4};
\node[blue, left] at (0, -4.5) {5};
\node[black, above] at (.5, 0) {1};
\node[red, above] at (4.5, 0) {2};
\node[orange, above] at (3.5, 0) {3};
\node[green, above] at (2.5, 0) {4};
\node[blue, above] at (1.5, 0) {5};
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0);
\draw[pipes, color=orange] (0.0,-2.5) -- (0.5,-2.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.0);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
\caption{The sweeping algorithm with~$\omega = 15432$ and~$\pi = 15243$.}
\label{ex:triangular_sweeping}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\node[black,left] at (0,-.5) {1};
\node[gray,left] at (0,-1.5) {2};
\node[gray,left] at (0,-2.5) {3};
\node[gray,left] at (0,-3.5) {4};
\node[gray,left] at (0,-4.5) {5};
\node[black,above] at (.5,0) {1};
\node[gray,above] at (1.5,0) {5};
\node[gray,above] at (2.5,0) {4};
\node[gray,above] at (3.5,0) {3};
\node[gray,above] at (4.5,0) {2};
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5);
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\node[black,left] at (0,-.5) {1};
\node[gray,left] at (0,-1.5) {2};
\node[gray,left] at (0,-2.5) {3};
\node[gray,left] at (0,-3.5) {4};
\node[blue,left] at (0,-4.5) {5};
\node[black,above] at (.5,0) {1};
\node[blue,above] at (1.5,0) {5};
\node[gray,above] at (2.5,0) {4};
\node[gray,above] at (3.5,0) {3};
\node[gray,above] at (4.5,0) {2};
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5); 
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\node[black,left] at (0,-.5) {1};
\node[red,left] at (0,-1.5) {2};
\node[gray,left] at (0,-2.5) {3};
\node[gray,left] at (0,-3.5) {4};
\node[blue,left] at (0,-4.5) {5};
\node[black,above] at (.5,0) {1};
\node[blue,above] at (1.5,0) {5};
\node[gray,above] at (2.5,0) {4};
\node[gray,above] at (3.5,0) {3};
\node[red,above] at (4.5,0) {2};
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5); 
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\node[black,left] at (0,-.5) {1};
\node[red,left] at (0,-1.5) {2};
\node[gray,left] at (0,-2.5) {3};
\node[green,left] at (0,-3.5) {4};
\node[blue,left] at (0,-4.5) {5};
\node[black,above] at (.5,0) {1};
\node[blue,above] at (1.5,0) {5};
\node[green,above] at (2.5,0) {4};
\node[gray,above] at (3.5,0) {3};
\node[red,above] at (4.5,0) {2};
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5); 
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.0);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline=-1cm]
\node[black,left] at (0,-.5) {1};
\node[red,left] at (0,-1.5) {2};
\node[orange,left] at (0,-2.5) {3};
\node[green,left] at (0,-3.5) {4};
\node[blue,left] at (0,-4.5) {5};
\node[black,above] at (.5,0) {1};
\node[blue,above] at (1.5,0) {5};
\node[green,above] at (2.5,0) {4};
\node[orange,above] at (3.5,0) {3};
\node[red,above] at (4.5,0) {2};
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0); 
\draw[boundaries] (0,-5) -- (1,-5) -- (1,-4) -- (2,-4) -- (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1) -- (5,-1) -- (5,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5); 
\draw[pipes, boundaries] (0.5,-5) -- (0.5,-4.5) -- (1,-4.5); 
\draw[pipes, boundaries] (1.5,-4) -- (1.5,-3.5) -- (2,-3.5); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, boundaries] (4.5,-1) -- (4.5,-0.5) -- (5,-0.5); 
\draw[pipes, color=black] (0.0,-0.5) -- (0.5,-0.5) -- (0.5,0.0);
\draw[pipes, color=red] (0.0,-1.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0);
\draw[pipes, color=orange] (0.0,-2.5) -- (0.5,-2.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0);
\draw[pipes, color=green] (0.0,-3.5) -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.0);
\draw[pipes, color=blue] (0.0,-4.5) -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0);
\end{tikzpicture}
\caption{The insertion algorithm with~$\omega = 15432$ and~$\pi = 15243$.}
\label{ex:triangular_insertion}
\end{center}
\end{figure}

We know from \cref{thm:triangular_congruence} that the fibers of~$\ins_\omega$ respect the lattice properties of the weak order on~$[\id, \omega]$. The following theorem shows that this application also send the weak order to the increasing flip graph on~$\Sigma(\omega)$.

\begin{theorem}\label{thm:triangular_suborder}
For any two pipe dreams~$P,P' \in \Sigma(\omega)$, there is a path from~$P$ to~$P'$ in the increasing flip graph on acyclic pipe dreams if and only if there exist linear extensions~$\pi$ of~$P$ and~$\pi'$ of~$P'$ such that~$\pi$ is below $\pi'$ in the weak order.

%For any two pipe dreams~$P,P' \in \Sigma(\omega)$, the following statements are equivalent:
%\begin{compactitem}
%\item there is a path from~$P$ to~$P'$ in the increasing flip graph on~$\Sigma(\omega)$;
%\item there exist linear extensions~$\pi$ of~$P$ and~$\pi'$ of~$P'$ such that~$\pi < \pi'$ in weak order.
%\end{compactitem}
\end{theorem}

\begin{rem}
The image of the weak order by~$\ins_\omega$ is not always the restriction of the increasing flip order on~$\Pi(\omega)$ to acyclic pipe dreams. An example is given in \cref{ex:triangular_flip_order}: a sequence of ascending flips from~$P_1$ to~$P_2$ is represented, therefore~$P_1 < P_2$ in the flip order. Moreover, we see that~$\lin(P_1) = \{ 123546 \}$ and~$\lin(P_2) = \{ 126453 \}$ so both~$P_1$ and~$P_2$ are acyclic. However, the only linear extension of~$P_1$ is not comparable to the only linear extension of~$P_2$ in the weak order, and thus~$P_1 \nless P_2$ in the image of the weak order; this is possible because the two middle pipe dreams are not acyclic, so the flips are not part of the increasing flip graph on~$\Sigma(126543)$.
\end{rem}

Combining \cref{thm:triangular_suborder} and \cref{thm:triangular_congruence} tells us that we can quotient~$[\id, \omega]$ by~$\equiv_\omega$ to obtain a lattice quotient whose elements are the fibers of~$\ins_\omega$, and we thus obtain the following result.

\begin{theorem}\label{thm:triangular_morphism}
The increasing flip graph on~$\Sigma(\omega)$ is isomorphic to the Hasse diagram of the lattice quotient~$[\id, \omega] / \equiv_\omega$. Moreover, the map~$\ins_\omega$ is a lattice morphism from the weak order on~$[\id, \omega]$ to the reflexive and transitive closure of the increasing flip graph on~$\Sigma(\omega)$.
\end{theorem}

\begin{figure}
\begin{center}
$P_1 =$
\begin{tikzpicture}[scale=0.35, anchor=base, baseline=-1cm, every node/.style={inner sep=1,outer sep=1}]
\draw[boundaries] (0,0); 
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0) -- (6,0); 
\draw[boundaries] (0,-6) -- (1,-6) -- (1,-5) -- (2,-5) -- (2,-4) -- (3,-4) -- (3,-3) -- (4,-3) -- (4,-2) -- (5,-2) -- (5,-1) -- (6,-1) -- (6,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5) -- (0,-6); 
\draw[pipes, boundaries] (0.5,-6) -- (0.5,-5.5) -- (1,-5.5); 
\draw[pipes, boundaries] (1.5,-5) -- (1.5,-4.5) -- (2,-4.5); 
\draw[pipes, boundaries] (2.5,-4) -- (2.5,-3.5) -- (3,-3.5); 
\draw[pipes, boundaries] (3.5,-3) -- (3.5,-2.5) -- (4,-2.5); 
\draw[pipes, boundaries] (4.5,-2) -- (4.5,-1.5) -- (5,-1.5); 
\draw[pipes, boundaries] (5.5,-1) -- (5.5,-0.5) -- (6,-0.5); 
\draw[pipes, black] (0.0,-0.5) node[left=-1pt] {1} -- (0.5,-0.5) -- (0.5,0.0) node[above=-1pt] {1};
\draw[pipes, violet] (0.0,-1.5) node[left=-1pt] {2} -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0) node[above=-1pt] {2};
\draw[pipes, red] (0.0,-2.5) node[left=-1pt] {3} -- (0.5,-2.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (5.5,-0.5) -- (5.5,0.0) node[above=-1pt] {3};
\draw[pipes, orange] (0.0,-3.5) node[left=-1pt] {4} -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (3.5,-2.5) -- (3.5,-1.5) -- (4.5,-1.5) -- (4.5,-0.5) -- (4.5,0.0) node[above=-1pt] {4};
\draw[pipes, green] (0.0,-4.5) node[left=-1pt] {5} -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0) node[above=-1pt] {5};
\draw[pipes, blue] (0.0,-5.5) node[left=-1pt] {6} -- (0.5,-5.5) -- (0.5,-4.5) -- (1.5,-4.5) -- (1.5,-3.5) -- (2.5,-3.5) -- (2.5,-2.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.0) node[above=-1pt] {6};
\node[black, scale=.7] (1) at (-1,-8) {1};
\node[violet, scale=.7] (2) at (.5,-8) {2};
\node[red, scale=.7] (3) at (2,-8) {3};
\node[green, scale=.7] (5) at (3.5,-8) {5};
\node[orange, scale=.7] (4) at (5,-8) {4};
\node[blue, scale=.7] (6) at (6.5,-8) {6};
\draw[->] (1) to (2);
\draw[->] (2) to (3);
\draw[->] (3) to (5);
\draw[->] (5) to (4);
\draw[->] (4) to (6);
\draw[->] (5) to [bend left=45] (6);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.35, anchor=base, baseline=-1cm, every node/.style={inner sep=1,outer sep=1}]
\draw[boundaries] (0,0); 
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0) -- (6,0); 
\draw[boundaries] (0,-6) -- (1,-6) -- (1,-5) -- (2,-5) -- (2,-4) -- (3,-4) -- (3,-3) -- (4,-3) -- (4,-2) -- (5,-2) -- (5,-1) -- (6,-1) -- (6,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5) -- (0,-6); 
\draw[pipes, boundaries] (0.5,-6) -- (0.5,-5.5) -- (1,-5.5); 
\draw[pipes, boundaries] (1.5,-5) -- (1.5,-4.5) -- (2,-4.5); 
\draw[pipes, boundaries] (2.5,-4) -- (2.5,-3.5) -- (3,-3.5); 
\draw[pipes, boundaries] (3.5,-3) -- (3.5,-2.5) -- (4,-2.5); 
\draw[pipes, boundaries] (4.5,-2) -- (4.5,-1.5) -- (5,-1.5); 
\draw[pipes, boundaries] (5.5,-1) -- (5.5,-0.5) -- (6,-0.5); 
\draw[pipes, black] (0.0,-0.5) node[left=-1pt] {1} -- (0.5,-0.5) -- (0.5,0.0) node[above=-1pt] {1};
\draw[pipes, violet] (0.0,-1.5) node[left=-1pt] {2} -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0) node[above=-1pt] {2};
\draw[pipes, red] (0.0,-2.5) node[left=-1pt] {3} -- (0.5,-2.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (5.5,-0.5) -- (5.5,0.0) node[above=-1pt] {3};
\draw[pipes, orange] (0.0,-3.5) node[left=-1pt] {4} -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (3.5,-2.5) -- (3.5,-1.5) -- (4.5,-1.5) -- (4.5,-0.5) -- (4.5,0.0) node[above=-1pt] {4};
\draw[pipes, green] (0.0,-4.5) node[left=-1pt] {5} -- (1.5,-4.5) -- (1.5,-3.5) -- (2.5,-3.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0) node[above=-1pt] {5};
\draw[pipes, blue] (0.0,-5.5) node[left=-1pt] {6} -- (0.5,-5.5) -- (0.5,-2.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-1.5) -- (2.5,0.0) node[above=-1pt] {6};
\node[black, scale=.7] (1) at (-1,-8) {1};
\node[violet, scale=.7] (2) at (.5,-8) {2};
\node[red, scale=.7] (3) at (2,-8) {3};
\node[blue, scale=.7] (6) at (3.5,-8) {6};
\node[green, scale=.7] (5) at (5,-8) {5};
\node[orange, scale=.7] (4) at (6.5,-8) {4};
\draw[->] (1) to (2);
\draw[->] (2) to (3);
\draw[->] (3) to (6);
\draw[->] (6) to (5);
\draw[->] (5) to (4);
\draw[->] (4) to [bend right=60] (5);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.35, anchor=base, baseline=-1cm, every node/.style={inner sep=1,outer sep=1}]
\draw[boundaries] (0,0); 
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0) -- (6,0); 
\draw[boundaries] (0,-6) -- (1,-6) -- (1,-5) -- (2,-5) -- (2,-4) -- (3,-4) -- (3,-3) -- (4,-3) -- (4,-2) -- (5,-2) -- (5,-1) -- (6,-1) -- (6,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5) -- (0,-6); 
\draw[pipes, boundaries] (0.5,-6) -- (0.5,-5.5) -- (1,-5.5); 
\draw[pipes, boundaries] (1.5,-5) -- (1.5,-4.5) -- (2,-4.5); 
\draw[pipes, boundaries] (2.5,-4) -- (2.5,-3.5) -- (3,-3.5); 
\draw[pipes, boundaries] (3.5,-3) -- (3.5,-2.5) -- (4,-2.5); 
\draw[pipes, boundaries] (4.5,-2) -- (4.5,-1.5) -- (5,-1.5); 
\draw[pipes, boundaries] (5.5,-1) -- (5.5,-0.5) -- (6,-0.5); 
\draw[pipes, black] (0.0,-0.5) node[left=-1pt] {1} -- (0.5,-0.5) -- (0.5,0.0) node[above=-1pt] {1};
\draw[pipes, violet] (0.0,-1.5) node[left=-1pt] {2} -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0) node[above=-1pt] {2};
\draw[pipes, red] (0.0,-2.5) node[left=-1pt] {3} -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (5.5,-0.5) -- (5.5,0.0) node[above=-1pt] {3};
\draw[pipes, orange] (0.0,-3.5) node[left=-1pt] {4} -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (3.5,-2.5) -- (3.5,-1.5) -- (4.5,-1.5) -- (4.5,-0.5) -- (4.5,0.0) node[above=-1pt] {4};
\draw[pipes, green] (0.0,-4.5) node[left=-1pt] {5} -- (1.5,-4.5) -- (1.5,-3.5) -- (2.5,-3.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0) node[above=-1pt] {5};
\draw[pipes, blue] (0.0,-5.5) node[left=-1pt] {6} -- (0.5,-5.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.0) node[above=-1pt] {6};
\node[black, scale=.7] (1) at (-1,-8) {1};
\node[violet, scale=.7] (2) at (.5,-8) {2};
\node[red, scale=.7] (6) at (2,-8) {6};
\node[blue, scale=.7] (3) at (3.5,-8) {3};
\node[green, scale=.7] (5) at (5,-8) {5};
\node[orange, scale=.7] (4) at (6.5,-8) {4};
\draw[->] (1) to (2);
\draw[->] (2) to (6);
\draw[->] (6) to (3);
\draw[->] (3) to (5);
\draw[->] (5) to (4);
\draw[->] (4) to [bend right=60] (5);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.35, anchor=base, baseline=-1cm, every node/.style={inner sep=1,outer sep=1}]
\draw[boundaries] (0,0); 
\draw[entrance path] (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4,0) -- (5,0) -- (6,0); 
\draw[boundaries] (0,-6) -- (1,-6) -- (1,-5) -- (2,-5) -- (2,-4) -- (3,-4) -- (3,-3) -- (4,-3) -- (4,-2) -- (5,-2) -- (5,-1) -- (6,-1) -- (6,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (0,-3) -- (0,-4) -- (0,-5) -- (0,-6); 
\draw[pipes, boundaries] (0.5,-6) -- (0.5,-5.5) -- (1,-5.5); 
\draw[pipes, boundaries] (1.5,-5) -- (1.5,-4.5) -- (2,-4.5); 
\draw[pipes, boundaries] (2.5,-4) -- (2.5,-3.5) -- (3,-3.5); 
\draw[pipes, boundaries] (3.5,-3) -- (3.5,-2.5) -- (4,-2.5); 
\draw[pipes, boundaries] (4.5,-2) -- (4.5,-1.5) -- (5,-1.5); 
\draw[pipes, boundaries] (5.5,-1) -- (5.5,-0.5) -- (6,-0.5); 
\draw[pipes, black] (0.0,-0.5) node[left=-1pt] {1} -- (0.5,-0.5) -- (0.5,0.0) node[above=-1pt] {1};
\draw[pipes, violet] (0.0,-1.5) node[left=-1pt] {2} -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.0) node[above=-1pt] {2};
\draw[pipes, red] (0.0,-2.5) node[left=-1pt] {3} -- (0.5,-2.5) -- (1.5,-2.5) -- (2.5,-2.5) -- (3.5,-2.5) -- (3.5,-1.5) -- (4.5,-1.5) -- (4.5,-0.5) -- (5.5,-0.5) -- (5.5,0.0) node[above=-1pt] {3};
\draw[pipes, orange] (0.0,-3.5) node[left=-1pt] {4} -- (0.5,-3.5) -- (1.5,-3.5) -- (1.5,-2.5) -- (1.5,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (4.5,-0.5) -- (4.5,0.0) node[above=-1pt] {4};
\draw[pipes, green] (0.0,-4.5) node[left=-1pt] {5} -- (0.5,-4.5) -- (1.5,-4.5) -- (1.5,-3.5) -- (2.5,-3.5) -- (2.5,-2.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (3.5,0.0) node[above=-1pt] {5};
\draw[pipes, blue] (0.0,-5.5) node[left=-1pt] {6} -- (0.5,-5.5) -- (0.5,-4.5) -- (0.5,-3.5) -- (0.5,-2.5) -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.0) node[above=-1pt] {6};
\node[black, scale=.7] (1) at (-1,-8) {1};
\node[violet, scale=.7] (2) at (.5,-8) {2};
\node[red, scale=.7] (6) at (2,-8) {6};
\node[blue, scale=.7] (4) at (3.5,-8) {4};
\node[green, scale=.7] (5) at (5,-8) {5};
\node[orange, scale=.7] (3) at (6.5,-8) {3};
\draw[->] (1) to (2);
\draw[->] (2) to (6);
\draw[->] (6) to (4);
\draw[->] (4) to (5);
\draw[->] (5) to (3);
\draw[->] (4) to [bend left=45] (3);
\end{tikzpicture}
$=P_2$
\end{center}
\caption{Two pipe dreams comparable in the flip order but not in the weak order.}
\label{ex:triangular_flip_order}
\end{figure}

%This study of triangular pipe dreams thus gives us a lattice quotient of any initial interval of the weak order (and thus of any interval, as an interval~$[\omega_1, \omega_2]$ is isomorphic to the initial interval~$[\id, \omega_1\pos \omega_2]$).

\begin{figure}[b]
\begin{center}
\begin{tikzpicture}[scale=0.5, anchor=base, baseline]
\node[red, scale=0.7] (1) at (-2,2) {1};
\node[orange, scale=0.7] (2) at (-2,0.6) {2};
\node[green, scale=0.7] (3) at (-2,-0.6) {3};
\node[blue, scale=0.7] (4) at (-2, -2) {4};
\draw[->] (2) to (1);
\draw[->] (1) to [bend right=45] (4);
\fill[yellow, semitransparent] (2,-1) rectangle (3,0) rectangle (4,1);
\draw[boundaries] (0,0) -- (0,1) -- (1,1) -- (1,2) -- (2,2); 
\draw[entrance path] (2,2) -- (2,1) -- (3,1) -- (4,1) -- (4,0); 
\draw[boundaries] (2,-2) -- (3,-2) -- (3,-1) -- (4,-1) -- (4,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (1,1.5) -- (1.5,1.5) -- (1.5,2); 
\draw[pipes, boundaries] (2.5,-2) -- (2.5,-1.5) -- (3,-1.5); 
\draw[pipes, boundaries] (3.5,-1) -- (3.5,-0.5) -- (4,-0.5); 
\draw[pipes, red] (0.0,-0.5) node[left=-3pt] {1} -- (0.5,-0.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (3.5,0.5) -- (4.0,0.5) node[right=-3pt] {1};
\draw[pipes, orange] (0.5,-1.0) node[below=-3pt] {2} -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (2.5,0.5) -- (2.5,1.0) node[above=-3pt] {2};
\draw[pipes, green] (1.5,-1.0) node[below left=-3pt] {3} -- (1.5,-0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.0,1.5) node[above right=-3pt] {3};
\draw[pipes, blue] (2.0,-1.5) node[left=-3pt] {4} -- (2.5,-1.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (3.5,0.5) -- (3.5,1.0) node[above=-3pt] {4};
\end{tikzpicture}
$\quad \rightarrow \quad$
\begin{tikzpicture}[scale=0.5, anchor=base, baseline]
\fill[yellow, semitransparent] (2,-1) rectangle (3,0) rectangle (4,1);
\draw[boundaries] (0,0) -- (0,1) -- (1,1) -- (1,2) -- (2,2); 
\draw[entrance path] (2,2) -- (2,1) -- (3,1) -- (4,1) -- (4,0); 
\draw[boundaries] (2,-2) -- (3,-2) -- (3,-1) -- (4,-1) -- (4,0); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (1,1.5) -- (1.5,1.5) -- (1.5,2); 
\draw[pipes, boundaries] (2.5,-2) -- (2.5,-1.5) -- (3,-1.5); 
\draw[pipes, boundaries] (3.5,-1) -- (3.5,-0.5) -- (4,-0.5); 
\draw[pipes, color=red] (0.0,-0.5) node[left=-3pt] {1} -- (0.5,-0.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (3.5,0.5) -- (4.0,0.5) node[right=-3pt] {1};
\draw[pipes, color=orange] (0.5,-1.0) node[below=-3pt] {2} -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (2.5,0.5) -- (2.5,1.0) node[above=-3pt] {2};
\draw[pipes, color=green] (1.5,-1.0) node[below left=-3pt] {3} -- (1.5,-0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.0,1.5) node[above right=-3pt] {3};
\draw[pipes, color=blue] (2.0,-1.5) node[left=-3pt] {4} -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.5) -- (3.5,0.5) -- (3.5,1.0) node[above=-3pt] {4};
\node[red, scale=0.7] (1) at (6,2) {1};
\node[orange, scale=0.7] (2) at (6,0.6) {2};
\node[green, scale=0.7] (3) at (6,-0.6) {3};
\node[blue, scale=0.7] (4) at (6, -2) {4};
\draw[->] (2) to [bend right=45] (4);
\draw[->] (4) to [bend right=45] (1);
\end{tikzpicture}
\caption{An ascending flip between two reduced pipe dreams on a 4-shape with exit permutation~$3241$ and their contact graphs.}
\label{ex:typeA_pipe_dream}
\end{center}
\end{figure}

\newpage

\section{Generalized pipe dreams}\label{sec:typeA}

%retravailler pour insister sur les pipe dreams

The previous section proved that increasing flip graphs on acyclic triangular pipe dreams were lattice quotients of weak order intervals. A similar result was given in \cite{Pilaud-brickAlgebra}, where we observe that cambrian lattices -- a generalization of the Tamari lattice introduced in \cite{Reading-CambrianLattices} -- can be realized with pipe dreams in some well-chosen shapes on the two dimensional cartesian grid. Here we consider even more general shapes inspired by this work.

To describe the boundaries of our shapes on this grid, we will describe \emph{paths} by their origin in~$\Z^2$ and a sequence of steps of length one given by their direction: the letters~$N$, $S$, $E$ and~$W$ correspond respectively to northward, southward, eastward and westward step. Moreover, for a path~$\pathh{P}$, the notation~$|\pathh{P}|_x$ denotes the numbers of steps in~$\pathh{P}$ with direction~$x$.

In general, we will define an~$n$-shape~$F$ for~$n \geqslant 2$ as a collection of cells on the two-dimensional cartesian grid delimited by four paths as follows:
\begin{compactitem}
\item a \emph{starting path}~$\pstart{F}$ from~$(0,0)$ to~$(|\pstart{F}|_E, -|\pstart{F}|_S)$ with~$n$ steps~$S$ or~$E$;
\item a \emph{NW stair path} from~$(0,0)$ to~$(t_F,t_F)$ of the form~$(NE)^{t_F}$ for some~$t_F \geqslant 0$;
\item a \emph{SE stair path} from~$(|\pstart{F}|_E, -|\pstart{F}|_S)$ to~$(|\pstart{F}|_E+b_F, -|\pstart{F}|_S+b_F)$ of the form~$(EN)^{b_F}$ for some~$b_F \geqslant 0$;
\item an \emph{ending path}~$\pend{F}$ from~$(t_F,t_F)$ to~$(|\pstart{F}|_E+b_F, -|\pstart{F}|_S+b_F)$ with~$n$ steps~$S$ or~$E$.
\end{compactitem}
An example is given in \cref{ex:typeA_pipe_dream}: the~4-shape is drawn in black, with the starting and ending path bolded and the stair paths drawn with finer lines.

A \emph{pipe dream} on the~$n$-shape~$F$ is then a filling of this shape with crosses~\cross{} and contacts~\elbow{} such that the figure contains~$n$ pipes starting on a step of the starting path and ending on a step of the ending path. The pipes are numbered in the natural order from north-west to south-east on the starting path, and the order in which they appear on the ending path from north-west to south-east is the \emph{exit permutation} of the pipe dream. As in the triangular case, we only consider \emph{reduced} pipe dreams, i.e those where any two pipes cross at most once. For an~$n$-shape~$F$ and a permutation~$\omega \in \fS_n$, we denote by~$\Pi_F(\omega)$ the set of reduced pipe dreams on~$F$ with exit permutation~$\omega$.

We note that the triangular shape used to create triangular pipe dreams is an~$n$-shape: the starting path only has~$S$ steps, the ending path only has~$E$ steps, the NW stair path has length 0 and the SE stair path has length~$2n$. Cambrian shapes in \cite{Reading-CambrianLattices} are another particular case of these shapes, where the starting and ending paths are opposite. %\vincent{attention}

Flips, increasing and decreasing flips, the increasing flip order and the contact graph of a pipe dream are defined the same way as in the triangular case, as illustrated in \cref{ex:typeA_pipe_dream}. We denote by~$\Sigma_F(\omega)$ the set of acyclic reduced pipe dreams on the~$n$-shape~$F$ for any permutation~$\omega \in \fS_n$.

Until now, the generalization of triangular pipe dreams to~$n$-shapes seems to be very simple, but some limitations appear very quickly. The first is that~$n$-shapes can be "too small", in the sense that one can find an~$n$-shape~$F$ and a permutation~$\omega \in \fS_n$ such that~$\Pi(\omega)$ is empty because there is not enough space in~$F$ for the pipes of a pipe dream to cross each other in a way to exit in order~$\omega$. %TODO illustration
In general, we will say that a permutation $\omega \in \fS_n$ is \emph{sortable} on an~$n$-shape~$F$ if~$\Pi(\omega)$ contains at least one pipe dream. In that case, it turns out that~$\Sigma(\omega)$ is also nonempty. Indeed, one can always find a reduced acyclic pipe dream from any pipe dream: first by removing pairs of crossings of the same two pipes, and then by doing descending flips on the result until no such flip is possible; the resulting pipe dream has~$\id_n \in \fS_n$ as a linear extension.

Moreover, even when considering a permutation sortable on a shape, the linear extensions of acyclic pipe dreams behave significantly less nicely than in the triangular case. The statement given by \cref{thm:triangular_partition} does not translate as is to general pipe dreams: some linear extensions lie outside of the weak order interval below the exit permutation. The closest true statement is the following.

\begin{theorem} \label{thm:typeA_partition}
Let~$F$ be an~$n$-shape and~$\omega \in \fS_n$ be a permutation sortable on~$F$, we denote by~$\lin_F(\omega)$ the set of all linear extensions of pipe dreams in~$\Sigma_F(\omega)$. Then:
\begin{compactitem}
\item the set~$\{ \lin(P) \mid P \in \Sigma_F(\omega) \}$ is a partition of~$\lin_F(\omega)$;
\item the set~$\lin_F(\omega)$ is a lower ideal of the weak order on~$\fS_n
$ that contains the interval~$[\id,\omega]$.
\end{compactitem}
\end{theorem}

While this theorem still allows for the definition of an equivalence relation and a map similar to~$\equiv_\omega$ and~$\ins_\omega$ in the triangular case, their relationship with the lattice properties of the weak order are limited by two aspects: one is that the maximal possible domain of this function, which is~$\lin_F(\omega)$, is not always an interval and as such is not always a lattice, and the second one is that if we only define our function on the interval~$[\id, \omega]$, some acyclic pipe dreams may not have any preimage, as is the case in the example in \cref{ex:typeA_bad_fiber}: the pipe dream has only one linear extension~$15234$ and it is not below its exit permutation~$31524$ in the weak order. We thus have to make a choice between lattice properties of the map and surjectivity on acyclic facets.

\begin{figure}
\begin{center}
\begin{minipage}{0.35\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.5]
\node[red, scale=.8, inner sep=1, outer sep=1] (1) at (-2, 2) {1};
\node[orange, scale=.8, inner sep=1, outer sep=1] (2) at (-2, .75) {2};
\node[green, scale=.8, inner sep=1, outer sep=1] (3) at (-2, -.5) {3};
\node[blue, scale=.8, inner sep=1, outer sep=1] (4) at (-2, -1.75) {4};
\node[violet, scale=.8, inner sep=1, outer sep=1] (5) at (-2, -3) {5};
\draw[->] (1) to (2);
\draw[->] (2) to (3);
\draw[->] (3) to (4);
\draw[->] (1) to [bend right=30] (5);
\draw[->] (5) to [bend right=30] (2);
\draw[->] (2) to [bend right=30] (4);
\draw[boundaries] (0,0) -- (0,1) -- (1,1) -- (1,2) -- (2,2); 
\draw[entrance path] (2,2) -- (2,1) -- (3,1) -- (4,1) -- (4,0) -- (4,-1); 
\draw[boundaries] (2,-3) -- (3,-3) -- (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (0,-2) -- (1,-2) -- (2,-2) -- (2,-3); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (1,1.5) -- (1.5,1.5) -- (1.5,2); 
\draw[pipes, boundaries] (2.5,-3) -- (2.5,-2.5) -- (3,-2.5); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\draw[pipes, red] (0.0,-0.5) node[left=-3pt] {1} -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (2.5,0.5) -- (2.5,1.0) node[above=-3pt] {1};
\draw[pipes, orange] (0.0,-1.5) node[left=-3pt] {2} -- (0.5,-1.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (3.5,-0.5) -- (3.5,0.5) -- (4.0,0.5) node[right=-3pt] {2};
\draw[pipes, green] (0.5,-2.0) node[below=-3pt] {3} -- (0.5,-1.5) -- (1.5,-1.5) -- (1.5,-0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.0,1.5) node[above right=-3pt] {3};
\draw[pipes, blue] (1.5,-2.0) node[below left=-3pt] {4} -- (1.5,-1.5) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-0.5) -- (4.0,-0.5) node[right=-3pt] {4};
\draw[pipes, violet] (2.0,-2.5) node[left=-3pt] {5} -- (2.5,-2.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (2.5,0.5) -- (3.5,0.5) -- (3.5,1.0) node[above=-3pt] {5};
\end{tikzpicture}
\caption{A reduced acyclic pipe dream that is not strongly acyclic.}
\label{ex:typeA_bad_fiber}
\end{center}
\end{minipage}
\begin{minipage}{0.60\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.5, baseline=0]
\fill[yellow] (0,-1) rectangle (1,0);
\fill[yellow] (3,1) rectangle (4,2);
\draw[boundaries] (0,0) -- (0,1) -- (1,1) -- (1,2) -- (2,2); 
\draw[entrance path] (2,2) -- (3,2) -- (4,2) -- (4,1); 
\draw[boundaries] (2,-1) -- (3,-1) -- (3,0) -- (4,0) -- (4,1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (1,1.5) -- (1.5,1.5) -- (1.5,2); 
\draw[pipes, boundaries] (2.5,-1) -- (2.5,-0.5) -- (3,-0.5); 
\draw[pipes, boundaries] (3.5,0) -- (3.5,0.5) -- (4,0.5); 
\draw[pipes, red] (0.0,-0.5) node[left=-3pt] {1} -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.5,1.5) -- (3.5,1.5) -- (4.0,1.5) node[right=-3pt] {1};
\draw[pipes, blue] (0.5,-1.0) node[below=-3pt] {2} -- (0.5,-0.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (3.5,0.5) -- (3.5,1.5) -- (3.5,2.0) node[above=-3pt] {2};
\draw[pipes, green] (1.5,-1.0) node[below=-3pt] {3} -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (2.5,1.5) -- (2.5,2.0) node[above=-3pt] {3};
\node[red, scale=.8] (1) at (-2, 2) {1};
\node[blue, scale=.8] (2) at (-2, .5) {2};
\node[green, scale=.8] (3) at (-2, -1) {3};
\draw[->] (1) to (2);
\draw[->] (1) to [bend right=45] (3);
\draw[->] (3) to (2);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.5, baseline=0]
\fill[yellow] (0,-1) rectangle (1,0);
\fill[yellow] (3,1) rectangle (4,2);
\draw[boundaries] (0,0) -- (0,1) -- (1,1) -- (1,2) -- (2,2); 
\draw[entrance path] (2,2) -- (3,2) -- (4,2) -- (4,1); 
\draw[boundaries] (2,-1) -- (3,-1) -- (3,0) -- (4,0) -- (4,1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (1,1.5) -- (1.5,1.5) -- (1.5,2); 
\draw[pipes, boundaries] (2.5,-1) -- (2.5,-0.5) -- (3,-0.5); 
\draw[pipes, boundaries] (3.5,0) -- (3.5,0.5) -- (4,0.5); 
\draw[pipes, red] (0.0,-0.5) node[left=-3pt] {1} -- (0.5,-0.5) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (3.5,0.5) -- (3.5,1.5) -- (4.0,1.5) node[right=-3pt] {1};
\draw[pipes, blue] (0.5,-1.0) node[below=-3pt] {2} -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.5,1.5) -- (3.5,1.5) -- (3.5,2.0) node[above=-3pt] {2};
\draw[pipes, green] (1.5,-1.0) node[below=-3pt] {3} -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (2.5,1.5) -- (2.5,2.0) node[above=-3pt] {3};
\node[red, scale=.8] (1) at (6, 2) {1};
\node[blue, scale=.8] (2) at (6, 0.5) {2};
\node[green, scale=.8] (3) at (6, -1) {3};
\draw[->] (2) to (3);
\draw[->] (3) to [bend left=45] (1);
\draw[->] (2) to (1);
\end{tikzpicture}
\caption{An increasing flip between two noncomparable acyclic pipe dreams.}
\label{ex:typeA_bad_flip}
\end{center}
\end{minipage}
\end{center}
\end{figure}

Since our goal is to study lattice quotients of weak order intervals in pipe dreams, we chose to limit ourselves to the interval~$[\id, \omega]$. We thus define \emph{strongly acyclic} pipe dreams as pipe dreams with at least one linear extension below their exit permutation in the weak order. The example in \cref{ex:typeA_bad_fiber} is an acyclic pipe dream that is not strongly acyclic. We denote by~$\Sigma'_F(\omega)$ the set of strongly acyclic pipe dreams on the~$n$-shape~$F$ with exit permutation~$\omega$. We note that when~$F$ is a triangular shape like in the previous section, since~$\lin_F(\omega)$ is~$[\id, \omega]$ for any permutation~$\omega \in \fS_n$, any acyclic pipe dream is also strongly acyclic and~$\Sigma'_F(\omega) = \Sigma_F(\omega)$.

We can now define the equivalence relation~$\equiv_{F,\omega}$ on~$[\id, \omega]$ for any~$n$-shape~$F$ and any permutation~$\omega \in \fS_n$ as the one defined on~$[\id, \omega]$ whose equivalence classes are the sets of~$\{ \lin(P) \cap [\id, \omega] \mid P \in \Sigma'(\omega) \}$. However, while the Cambrian congruences that define Cambrian lattices as weak order quotients can be defined by rules similar as the one in \cref{thm:triangular_rewriting} (see section 6 of \cite{Reading-CambrianLattices}), there is no known characterization of~$\equiv_{F,\omega}$ outside of triangular shapes, even on Cambrian shapes. We can  nevertheless still study the properties of~$\equiv_{F, \omega}$ to obtain the following theorem.

\begin{theorem}\label{thm:typeA_congruence}
For any~$n$-shape~$F$ and any permutation~$\omega \in \fS_n$ sortable on~$F$, the relation~$\equiv_{F, \omega}$ is a lattice congruence of the weak order interval~$[\id, \omega]$.
\end{theorem}

Therefore we can quotient~$[\id, \omega]$ by~$\equiv_{F, \omega}$ to obtain a lattice quotient whose elements are the fibers of~$\ins_{F,\omega}$.

We can also define the map~$\ins_{F, \omega}: [\id, \omega] \mapsto \Sigma'(\omega)$ which associate to any permutation in~$[\id,\omega]$ the pipe dream on~$F$ with exit permutation~$\omega$ that has this permutation as a linear extension of its contact graph. As illustrated in \cref{ex:typeA_sweeping,ex:typeA_insertion}, the sweeping algorithm and the insertion algorithm can be adapted to work on~$n$-shapes. %attention

The application~$\ins_{F,\omega}$ still shows a link between the weak order and increasing flips in~$\Sigma'_F(\omega)$ in the sense that for any two permutations~$\pi, \pi'$ in~$[\id, \omega]$, if~$\pi \leqslant \pi'$ then there is a path from~$\ins_{F,\omega}(\pi)$ to~$\ins_{F, \omega}(\pi')$ in the increasing flip graph. However, the converse is not true and \cref{thm:triangular_suborder} does not hold for any~$n$-shape. This is illustrated on \cref{ex:typeA_bad_flip}, where the only linear extension~$132$ of the left pipe dream is not comparable to the only linear extension~$231$ of the right pipe dream, while the two pipe dreams are connected by the flip on the yellow cells. Therefore, the image of the weak order by~$\ins_{F,\omega}$ in general is a suborder of the increasing flip order that cannot be determined by simply looking at the increasing flip graph of~$\Pi_F(\omega)$; we call this order the \emph{acyclic flip order} on~$\Sigma'(\omega)$. Combined with \cref{thm:typeA_congruence}, we get the following result.

\begin{theorem}\label{thm:typeA_morphism}
The acyclic flip order on~$\Sigma'_F(\omega)$ is isomorphic to the lattice quotient~$[\id, \omega] / \equiv_{F, \omega}$. Moreover, the map~$\ins_{F, \omega}$ is a lattice morphism from the weak order on~$[\id, \omega]$ to the acyclic flip order on~$\Sigma'_F(\omega)$.
\end{theorem}

While this acyclic flip order seems very artificial and ad-hoc, we can actually find its covers in an object introduced first in \cite{PilaudSantos-brickPolytope}
and extended to any subword complex in \cite{JahnStump}: the brick polyhedron of a subword complex. This object was behind the first introduction of acyclic pipe dreams: the brick polytope is defined on some subword complexes as the convex hull of the brick vectors associated with facets, and acyclic facets are the one associated to vertices of this polytope. The brick polyhedron is a generalization to non-spherical subword complexes. In both case, a flip between two strongly acyclic pipe dreams is associated to a cover of the acyclic flip order if and only if the brick vectors of those pipe dreams are linked by an edge of the brick polyhedron.

We can thus say that the quotient of the weak order interval obtained with~$\equiv_{F,\omega}$ is isomorphic to the restriction of an orientation of the skeleton of the brick polyhedron to strongly acyclic facets. However, the removal of acyclic facets that are not strongly acyclic makes this result weaker, leading to us trying to find some conditions under which all acyclic facets are also strongly acyclic, like in the triangular case. This lead to the following theorem.

\begin{theorem}\label{thm:typeA_complete}
Let~$F$ be an~$n$-shape such that the maximal permutation of size~$n$ is sortable on~$F$, then for any permutation~$\omega \in \fS_n$ we have~$\lin_F(\omega) = [\id, \omega]$ and all acyclic pipe dreams on~$F$ are strongly acyclic.
\end{theorem}

Therefore, if the~$n$-shape is big enough, we can remove the distinction between acyclic and strongly acyclic pipe dreams and consider the full brick polyhedron. This condition on~$F$ is necessary to obtain that for any~$\omega \in \fS_n$, the linear extensions of pipe dreams in~$\Sigma_F(\omega)$ are exactly~$[\id, \omega]$.

\begin{figure}
\centerline{
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-1);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (1,-0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1,0.5);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-1);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (1.5,-0.5) -- (1.5,0);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1,0.5);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2,-0.5);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-1);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (1.5,-0.5) -- (1.5,0);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1,0.5);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3,-0.5);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (1.5,-0.5) -- (1.5,0.5) -- (2,0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3,-0.5);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
$\!\!\!\rightarrow\!\!\!$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (3.0,0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.0);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (2.5,1.0);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3.0,-0.5);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
}
\caption{The sweeping algorithm on a~5-shape with~$\omega = 23145$ and~$\pi=21345$.}
\label{ex:typeA_sweeping}
\end{figure}

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (3.0,0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (3.0,0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.0);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (2.5,1.0);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (3.0,0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.0);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (2.5,1.0);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3.0,-0.5);
\end{tikzpicture}
$\rightarrow$
\begin{tikzpicture}[scale=0.4, anchor=base, baseline]
\draw[boundaries] (0,0) -- (0,1) -- (1,1); 
\draw[entrance path] (1,1) -- (2,1) -- (3,1) -- (3,0) -- (3,-1) -- (4,-1); 
\draw[boundaries] (3,-2) -- (4,-2) -- (4,-1); 
\draw[entrance path] (0,0) -- (0,-1) -- (1,-1) -- (2,-1) -- (2,-2) -- (3,-2); 
\draw[pipes, boundaries] (0,0.5) -- (0.5,0.5) -- (0.5,1); 
\draw[pipes, boundaries] (3.5,-2) -- (3.5,-1.5) -- (4,-1.5); 
\node[red, left=-2pt] at (0,-0.5) {1};
\node[red, right=-2pt] at (3,0.5) {1};
\node[orange, below=-2pt] at (0.5,-1) {2};
\node[orange, above=-2pt] at (1.5,1) {2};
\node[green, below left=-3pt] at (1.5,-1) {3};
\node[green, above=-2pt] at (2.5,1) {3};
\node[blue, below left=-3pt] at (2,-1.5) {4};
\node[blue, above right=-3pt] at (3,-0.5) {4};
\node[purple, below=-2pt] at (2.5,-2) {5};
\node[purple, above right=-3pt] at (3.5,-1) {5};
\draw[pipes, red] (0.0,-0.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,0.5) -- (2.5,0.5) -- (3.0,0.5);
\draw[pipes, orange] (0.5,-1.0) -- (0.5,-0.5) -- (0.5,0.5) -- (1.5,0.5) -- (1.5,1.0);
\draw[pipes, green] (1.5,-1.0) -- (1.5,-0.5) -- (2.5,-0.5) -- (2.5,0.5) -- (2.5,1.0);
\draw[pipes, blue] (2.0,-1.5) -- (2.5,-1.5) -- (2.5,-0.5) -- (3.0,-0.5);
\draw[pipes, purple] (2.5,-2.0) -- (2.5,-1.5) -- (3.5,-1.5) -- (3.5,-1.0);
\end{tikzpicture}
\end{center}
\caption{The insertion algorithm on a~5-shape with~$\omega = 23145$ and~$\pi=21345$.}
\label{ex:typeA_insertion}
\end{figure}

\section{Extension to Coxeter groups}\label{sec:Coxeter}

Let~$(W,S)$ be a finite Coxeter system and let~$(\Phi, \Delta)$ be a root system for~$(W,S)$. In the following section, for any simple reflection~$s \in S$ we will denote by~$\alpha_s$ the simple root associated to~$s$. For any~$w \in W$, we define the \emph{inversion set} of~$w$ as~$\inv(w) = w(\Phi^-) \cap \Phi^+$, and the noninversion set of~$w$ as~$\ninv(w) = \Phi^+ \setminus \inv(w)$. The \emph{right weak order} on~$W$ is the order defined by inclusion on the inversion sets and it is a lattice.

Let~$Q$ be any word on the alphabet~$S$ and denote by~$m$ its length. For~$w \in W$, we denote by~$\SC(Q,w)$ the \emph{subword complex} defined by~$w$ on~$Q$, i.e the simplicial complex with ground set~$[m]$ and whose faces are the sets of indices of~$Q$ whose complement contains a reduced expression of~$w$. This object was introduced in \cite{KnutsonMiller-GroebnerGeometry} and developed in \cite{KnutsonMiller-subwordComplex} to study combinatorial properties of Schubert polynomials. The facets of~$\SC(Q,w)$ are the complements of subwords of~$Q$ that are reduced expressions of~$w$. Two distinct facets~$I$ and~$J$ of the same subword complex are linked by a \emph{flip} if and only if there exist~$i \in I$ and~$j \in J$ such that~$I = J \setminus \{j\} \cup \{i\}$, and this flip is \emph{increasing from~$I$ to~$J$} if~$j < i$ and decreasing otherwise. The \emph{increasing flip graph} of~$\SC(Q,w)$ has the facets as vertices and an edge from~$I$ to~$J$ if and only if there is an increasing flip from~$I$ to~$J$, and the transitive closure of this graph defines the \emph{increasing flip order} on facets of~$\SC(Q,w)$.

Let~$Q$ be a word on~$S$ and~$w$ be an element of~$W$ with~$\SC(Q, w)$ nonempty. The \emph{root function}~$\rf(I,\cdot) : [m] \mapsto \Phi$ on a facet~$I$ of this subword complex, introduced in \cite{CeballosLabbeStump}, is defined by
\[ \rf(I,k) = \left( \prod_{i \in \{1,\ldots, k-1\} \setminus I} Q_i \right) (\alpha_{Q_k}) \]
i.e it is the application of the prefix of~$w$ written by facet~$I$ up to index~$k-1$ on~$Q$ to the root associated with the~$k^\text{th}$ letter of~$Q$. We note that for any facet~$I$ of~$\SC(Q,w)$, the values of the root function of the indices not in~$I$ are the inversions of~$w$, each appearing exactly once. Moreover, for~$i \in I$, there exists a flip from~$I$ to a facet~$J$ with~$i \notin J$ if and only if~$\rf(I,i) \in \pm \inv(w)$, and this flip is increasing if~$\rf(I,i) \in \Phi^+$ and decreasing otherwise.

The \emph{root configuration} of a facet~$I$, denoted by~$\rc(I)$, is the set~$\{ \rf(I, k) \mid k \in I \}$ of the values of the root function on the other indices of~$Q$. An element~$\pi$ of~$W$ is a \emph{linear extension} of~$I$ if~$\rc(I) \subseteq \pi(\Phi^+)$. A facet is \emph{acyclic} if the cone generated by its root configuration is pointed, or, equivalently, if it has at least one linear extension, and \emph{strongly acyclic} if it has a linear extension in~$[e, w]$. We note that the contact graph of pipe dreams defined in parts 2 and 3 give a representation of the root configuration of the facet of the associated subword complex, and therefore the following theorem is a direct generalization of \cref{thm:triangular_partition} and \cref{thm:typeA_partition}.

\begin{theorem}
Let~$Q$ be a word on~$S$ and~$w \in W$ be such that~$\SC(Q,w)$ is nonempty. Let $\lin_Q(w)$ be the set of linear extensions of facets of~$\SC(Q,w)$. Then:
\begin{compactitem}
\item the set $\{ \lin(I) \mid I \in \SC(Q,w) \}$ is a partition of~$\lin_Q(w)$;
\item the set~$\lin_Q(w)$ is a lower ideal of the right weak order on~$W$ and contains~$[e, w]$.
\end{compactitem}
\end{theorem}

As in \cref{sec:triangular} and \cref{sec:typeA}, we can therefore define an equivalence relation~$\equiv_{Q,w}$ whose equivalence classes are the~$\lin(I)$ and a map~$\ins_{Q,w}: [e, w] \mapsto \SC(Q,w)$ such that~$\pi \in \lin(\ins_{Q,w}(\pi))$ for any~$\pi \in [e, w]$. Moreover, we can prove that if~$\pi < \pi'$ are two elements of~$[e, w]$, then~$\ins_{Q,w}(\pi) \leqslant \ins_{Q,w}(\pi')$ in the increasing flip order. However, the restrictions on the properties of~$\ins_{F,\omega}$ defined in \cref{sec:typeA} are also true for~$\ins_{Q,\omega}$: it is not always surjective on the acyclic facets of~$\SC(Q,w)$ and the image of the weak order is included in the increasing flip order but can be strictly weaker. We can however still prove that the flips that are covers of the image of the weak order are linked to the edges of the brick polyhedron defined on~$\SC(Q,w)$ in \cite{JahnStump}, and give a generalization of the sweeping algorithm in type A that computes~$\ins_{Q,w}(\pi)$ when it exists.

\begin{algo}\label{algo:Coxeter_sweeping}
The \emph{sweeping algorithm} on subword complexes computes~$\ins_{Q,w}$ by considering the indices of~$Q$ from first to last and adding~$t$ or not to the facet according to the following rules:
\begin{compactenum}
\item if~$\rf(\ins_{Q, w}(\pi), t) \in w(\Phi^+)$ then~$t$ is added;
\item else if~$\rf(\ins_{Q, w}(\pi),t) \in \pi(\Phi^-)$ then~$t$ is not added;
\item else~$t$ if and only if the result can be completed into a facet of~$\SC(Q, w)$.
\end{compactenum}
\end{algo}

We have now defined the objects we need to conjecture a generalization to \cref{thm:typeA_congruence} and \cref{thm:typeA_morphism}. However, even in type A, the quotient of~$[e,w]$ by~$\equiv_{Q,w}$ is not always a lattice quotient, as illustrated in Figure 9 of \cite{PilaudStump-brickPolytope}. We thus need to restrict the conjecture to a specific category of words. The generalization of~$n$-shapes to general Coxeter groups are \emph{alternating words}, i.e words such that for any~$s \in S$, if~$Q_i = Q_j = s$ and~$i<j$, then for any~$t \in S$ such that~$st \neq ts$, the letter~$t$ appears in~$Q$ between indices~$i$ and~$j$. In type A, the alternating words are equivalent to the~$n$-shapes. This leads us to the following conjecture, tested extensively on various finite Coxeter groups.

\begin{conj}\label{conj:Coxeter_morphism}
Let~$Q$ be an alternating word on~$S$ and~$w \in W$ be such that~$\SC(Q,w)$ is nonempty, then the relation~$\equiv_{Q, w}$ is a lattice congruence of the right weak order interval~$[e, w]$. The quotient of~$[e, w]$ is isomorphic to the strongly acyclic part of the brick polyhedron of~$\SC(Q, w)$ oriented by ascending flips, and~$\ins_{Q,w}$ is a lattice morphism from~$[e,w]$ to this.
\end{conj}

Lastly, a generalization of \cref{thm:typeA_complete} was proven in \cite{JahnStump}, where an algorithm very similar to \cref{algo:Coxeter_sweeping} was also defined.

\begin{theorem}[\cite{JahnStump}]
Let~$Q$ be a word on~$S$ and~$w$ be any element of~$W$. If~$Q$ contains a reduced word of~$w_0$ the longest element of~$W$, then for any facet of~$\SC(Q,w)$, the noninversions of~$w$ are all in the cone generated by the root configuration of the facet, and thus any linear extension of the facet is in~$[e, w]$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\printbibliography
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
