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

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

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\usepackage{lipsum}
\usepackage{cleveref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{thmtools}
\usepackage[all]{xy}
\usepackage{mathrsfs}
\usepackage{algorithm}% http://ctan.org/pkg/algorithm
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows,fit,calc,math}

% Custom commands
\newcommand\ba{\mathbf{a}}
\newcommand\bb{\mathbf{b}}
\newcommand\bd{\mathbf{d}}
\newcommand\be{\mathbf{e}}
\newcommand\bp{\mathbf{p}}
\newcommand\bq{\mathbf{q}}
\newcommand\br{\mathbf{r}}
\newcommand\bs{\mathbf{s}}
\newcommand\bt{\mathbf{t}}
\newcommand\bu{\mathbf{u}}
\newcommand\bv{\mathbf{v}}
\newcommand\bw{\mathbf{w}}
\newcommand\bx{\mathbf{x}}
\newcommand\by{\mathbf{y}}
\newcommand\bz{\mathbf{z}}

\newcommand\bbB{\mathbb{B}}
\newcommand\bbC{\mathbb{C}}
\newcommand\bbF{\mathbb{F}}
\newcommand\bbG{\mathbb{G}}
\newcommand\bbI{\mathbb{I}}
\newcommand\bbK{\mathbb{K}}
\newcommand\bbN{\mathbb{N}}
\newcommand\bbP{\mathbb{P}}
\newcommand\bbQ{\mathbb{Q}}
\newcommand\bbR{\mathbb{R}}
\newcommand\bbS{\mathbb{S}}
\newcommand\bbZ{\mathbb{Z}}

\newcommand\calA{\mathcal{A}}
\newcommand\calB{\mathcal{B}}
\newcommand\calC{\mathcal{C}}
\newcommand\calD{\mathcal{D}}
\newcommand\calE{\mathcal{E}}
\newcommand\calF{\mathcal{F}}
\newcommand\calG{\mathcal{G}}
\newcommand\calH{\mathcal{H}}
\newcommand\calI{\mathcal{I}}
\newcommand\calJ{\mathcal{J}}
\newcommand\calK{\mathcal{K}}
\newcommand\calL{\mathcal{L}}
\newcommand\calM{\mathcal{M}}
\newcommand\calN{\mathcal{N}}
\newcommand\calO{\mathcal{O}}
\newcommand\calP{\mathcal{P}}
\newcommand\calQ{\mathcal{Q}}
\newcommand\calR{\mathcal{R}}
\newcommand\calS{\mathcal{S}}
\newcommand\calT{\mathcal{T}}
\newcommand\calU{\mathcal{U}}
\newcommand\calV{\mathcal{V}}
\newcommand\calW{\mathcal{W}}
\newcommand\calX{\mathcal{X}}
\newcommand\calY{\mathcal{Y}}
\newcommand\calZ{\mathcal{Z}}

\newcommand\scrB{\mathscr{B}}
\newcommand\scrC{\mathscr{C}}
\newcommand\scrE{\mathscr{E}}
\newcommand\scrF{\mathscr{F}}
\newcommand\scrI{\mathscr{I}}
\newcommand\scrL{\mathscr{L}}
\newcommand\scrO{\mathscr{O}}
\newcommand\scrP{\mathscr{P}}
\newcommand\scrR{\mathscr{R}}
\newcommand\scrS{\mathscr{S}}

\newcommand\horiz{\mathrm{horiz}}
\newcommand\inedge{\mathrm{in}}
\newcommand\outedge{\mathrm{out}}
\newcommand\In{\mathrm{In}}
\newcommand\Out{\mathrm{Out}}
\newcommand\inv{^{-1}}
\newcommand\precccwrot{\prec_{\mathrm{rot}}^{\mathrm{ccw}}}
\newcommand\leqccwrot{\leq_{\mathrm{rot}}^{\mathrm{ccw}}}
\newcommand\cw{\mathrm{cw}}
\newcommand\ccw{\mathrm{ccw}}

% GRAPHS EXAMPLES
\newcommand{\oruga}[1]{\mathrm{Oruga}(#1)}
\newcommand{\multioruga}[1]{G_{#1}}
\newcommand{\cambrianCaracolGraph}[1]{G_{#1}}
\newcommand{\crossGridGraph}[1]{G_{#1}}



\newcommand{\defn}[1]{{\color{green!50!black}\textbf{\emph{#1}}}}

%\newcommand{\cesar}[1]{\todo[size=\footnotesize,color=orange!30,inline]{#1  \hfill --- C.}}
%\newcommand{\cesarm}[1]{\todo[size=\footnotesize,color=orange!30]{#1  \hfill --- C.}}
%\newcommand{\cesarformatias}[1]{\todo[size=\footnotesize,color=red!30,inline]{For Matias: #1  \hfill --- C.}}

%\newcommand{\matias}[1]{\todo[size=\footnotesize,color=blue!20,inline]{#1  \hfill --- M.}}
%\newcommand{\matiasm}[1]{\todo[size=\footnotesize,color=blue!20]{#1  \hfill --- M.}}
%\newcommand{\matiasforcesar}[1]{\todo[size=\footnotesize,color=green!20,inline]{For Cesar: #1  \hfill --- M.}}

\DeclareMathOperator{\hor}{hor}
\DeclareMathOperator{\ver}{ver}
\DeclareMathOperator{\car}{car}
\DeclareMathOperator{\Cat}{Cat}
\DeclareMathOperator{\Nar}{Nar}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\row}{row}
\DeclareMathOperator{\grid}{grid}
\DeclareMathOperator{\Tam}{Tam}
\DeclareMathOperator{\Rem}{Rem}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\rev}{rev}

% custom theorem environments
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}

%custom colours
\definecolor{ForestGreen}{cmyk}{0.91,0,0.88,0.12}
\definecolor{myYellow}{rgb}{249,166,3}
\definecolor{Cerulean}{RGB}{20,0,150}
\definecolor{NavyBlue}{cmyk}{0.94,0.54,0,0}
\definecolor{cof}{RGB}{219,144,71}
\definecolor{pur}{RGB}{186,146,162}
\definecolor{greeo}{RGB}{91,173,69}
\definecolor{greet}{RGB}{52,111,72}
\definecolor{LimeGreen}{cmyk}{0.50,0,1,0}
\definecolor{RawSienna}{cmyk}{0,0.72,1,0.45}
\definecolor{RedViolet}{cmyk}{0.07,0.90,0,0.34}

%Colors for colorblind equity 
%redone for grayscale 
%there's lots of ways to convert to gray, this is evenly distributing along 0.299R+0.587G+0.114B
\definecolor{blue}{rgb}{0, 0.445, 0.695}
\definecolor{bluishgreen}{rgb}{0, 0.626, 0.456}
\definecolor{red}{rgb}{0.896, 0.395, 0}
\definecolor{purple}{rgb}{0.783, 0.464, 0.640}
\definecolor{skyblue}{rgb}{0.359, 0.752, 0.973}
\definecolor{orange}{rgb}{0.999, 0.706, 0.0}
\definecolor{yellow}{rgb}{0.937, 0.890, 0.258}



%even more colors, generated by 'colorgorical' using the previous colors as inputs
%http://vrl.cs.brown.edu/color
\definecolor{olive}{RGB}{116,141,19}
\definecolor{green}{RGB}{108,208,48}
\definecolor{teal}{RGB}{47,77,62}
\definecolor{turquoise}{RGB}{86,235,211}
\definecolor{lightblue}{RGB}{150,178,153}
\definecolor{blue2}{RGB}{25,50,191}
\definecolor{indigo}{RGB}{142,128,251}
\definecolor{indigo2}{RGB}{114,32,246}
\definecolor{lightpurple}{RGB}{243,197,250}
\definecolor{purple2}{RGB}{105,66,131}
\definecolor{magenta}{RGB}{206,43,188}
\definecolor{brown}{RGB}{110,57,13} 
\definecolor{darkblue}{rgb}{0.0, 0.0, 0.7}

%% define your title in the usual way
\title{Framing lattices and flow polytopes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
Matias von Bell\thanks{\href{mailto:matias.vonbell@gmail.com}{matias.vonbell@gmail.com}. Both authors were supported by the Austrian Science Fund FWF, Project~P~33278, and by the \mbox{ANR-FWF} International Cooperation Project \mbox{PAGCAP}, FWF Project I 5788.}\addressmark{1} \and 
Cesar Ceballos\addressmark{1}  
}


%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1} Institute of Geometry, Graz University of Technology, Austria 
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
We introduce the framing lattice of a framed graph, a new lattice whose Hasse diagram is the dual graph of a framed triangulation of a flow polytope.
We show that every framing lattice is an HH lattice, hence polygonal, semidistributive, and congruence uniform. We also study lattice congruences determined by simple operations called M-moves. Framing lattices provide a unifying framework for the study of many remarkable lattice structures, and several well known results about them are straight forward corollaries of our results.   
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Flow polytope, framed triangulation, Tamari lattice, weak order, Cambrian lattice, cross-Tamari lattice.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{bibliography.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
Flow polytopes of acyclic oriented graphs are fundamental objects in the study of combinatorial optimization.
In recent years, there has been an explosion of interest in these objects due to their connections with other areas such as representation theory~\cite{BV08}, diagonal harmonics~\cite{LMMdiagonal2019}, and Grothendieck polynomials~\cite{MD2020}. 
From the combinatorial and geometric perspective, a special focus on flow polytopes concentrates on their volumes and triangulations. 
A novel method for triangulating flow polytopes using a framing of the graph was developed in~\cite{DKK12}. 

Since then, various families of combinatorial objects have revealed tight connections with triangulations of flow polytopes. Examples of this include the Boolean lattice, the Tamari lattice, and the weak order on permutations, each of which is a partially ordered set whose Hasse diagram appears as the dual graphs of a framed triangulation of a flow polytope. 
On the other hand, flow polytopes serve as a powerful tool to approach open problems about the combinatorial objects involved. For instance, certain framed triangulations of flow polytopes were used in~\cite{GMPTY23} to solve an open conjecture about geometric realizations of $s$-permutahedra.  
These recent developments motivate the following question: 
\begin{quote}
    \emph{Is the dual graph of any framed triangulation the Hasse diagram of a lattice?}
\end{quote}
In this paper, we give a positive answer to this question. For any directed graph $G$ and any framing $F$ of $G$, we define a lattice structure called the \emph{framing lattice} $\scrL_{G,F}$, whose Hasse diagram is the dual graph of the corresponding framed triangulation. The family of framing lattices captures many important lattices appearing in the literature, including those shown in Figure~\ref{fig_framing_lattices_zoo}.
Four explicit examples are shown in~\Cref{fig.graphs_and_lattices}, including a new family of lattices that we call cross-Tamari lattices. 

\begin{figure}[htb]
    \centering 
    %\include{fpsac_framing_lattices_zoo}
    \includegraphics[page=1, scale=1.3]{fpsac_allfigures.pdf}
    \caption{Some lattices captured by the theory of framing lattices.}
    \label{fig_framing_lattices_zoo}
\end{figure}

We prove several structural results about framing lattices. 
We show that every framing lattice is an HH lattice, hence polygonal, semidistributive,
and congruence uniform, and study lattice congruences determined by simple operations on framed graphs called M-moves. We remark that these properties are usually non-trivial results proven in several research works for the special classes outlined in Figure~\ref{fig_framing_lattices_zoo}; and they all follow from our global uniform results. 

\begin{figure}[htb]
    \centering
    %\include{fpsac_graphs_and_lattices}
    \includegraphics[page=2, scale=0.95]{fpsac_allfigures.pdf}
    \caption{Four framed graphs and the Hasse diagrams of their framing lattices. 
    The first is the Boolean lattice~$\scrB_3$. 
    The second is the lattice of multipermutations of $1^22^23$. The third is the $\varepsilon$-cambrian lattice with $\varepsilon = -\,-\,+\, -$. 
    The fourth is a cross-Tamari lattice of the cross-shaped grid shown below the right-most graph.}
    \label{fig.graphs_and_lattices}
\end{figure}



\section{Framed triangulations of flow polytopes}
Let $G$ be a directed acyclic graph on vertex set $V(G) = [n]$ and edge multiset $E(G)$ such that 
all edges are directed from smaller vertices to larger vertices and $G$ has a unique source $s=1$ and sink $t=n$.
We call such a graph $G$ a \defn{flow graph}.
A path from the source to the sink is said to be a \defn{route}.
For a vertex $v$ in a flow graph $G$ with vertex set $[n]$, let $\In(v)$ and $\Out(v)$ respectively denote the (possibly empty) incoming and outgoing edges at $v$. 
A \defn{unit flow} on~$G$ is then a tuple $(x_e)_{e\in E(G)} \in \bbR^{|E(G)|}_{\geq0}$ satisfying
$\sum_{e \in \Out(j)} x_e - \sum_{e \in \In(j)}  x_e = u_j,$
where $u_1 = 1$, $u_n = -1$, and $u_j = 0$ for $1 < 
j < n$.
The \defn{flow polytope} of $G$ is the set~$\calF_G$ of unit flows on $G$ and its dimension is given by $|E(G)| - |V(G)| +1$. 
The vertices of $\calF_G$ can be characterized as the unit flows on $G$ which have value one on the edges of a route and value zero on the remaining edges.
Thus $\calF_G$ can be described as the convex hull of the indicator vectors of the routes of $G$.

\begin{example}[The oruga graph and the cube]\label{example_running_oruga}
    Let $G_n=\oruga{n}$ be the \defn{oruga graph} on the vertex set~$[n+1]$ containing two edges $e_{2i-1}$ and~$e_{2i}$ between $i$ and $i+1$ for $i \in [n]$. 
    % An example of the oruga graph is illustrated on the left of~\Cref{fig_oruga_graph}. 

    \begin{figure}[htb]
        \centering
        %\include{fpsac_oruga}
        \includegraphics[page=3, scale=1]{fpsac_allfigures.pdf}
        \caption{An example of the oruga graph, its flow polytope, and a framed triangulation.}
        \label{fig_oruga_graph}
    \end{figure}

    The flow polytope $\calF_{G_n}$ is combinatorially a cube of dimension $n$, whose vertices are of the form 
    $
    e_{i_1}+\dots+e_{i_n},
    $
    where $e_i\in \bbR^{2n}$ denote the standard basis vectors and $i_k=2k-1$ or~$i_k=2k$, for each value $k\in [n]$. 
    These are the indicator vectors of the routes of~$G_n$.
\end{example}


We now recall the framed triangulations of flow polytopes introduced in~\cite{DKK12}.
A \defn{framing} at the vertex $v$ is a pair of linear orders $(\leq_{\In(v)}, \leq_{\Out(v)})$ on the incoming and outgoing edges at~$v$.
A \defn{framed graph}, denoted $(G,F)$, is a flow graph with a framing $F$ at every vertex.
An example of a framing of the $\oruga{2}$ graph is shown in~\Cref{fig_oruga2_coherent_example}, where the labels indicate the order of the incoming and outgoing edges at every vertex.

For a path $P$ containing a vertex $v$, let $Pv$ (resp. $vP$) denote the maximal subpath of~$P$ ending (resp. beginning) at $v$.
Furthermore, let $\scrI(v)$ (resp. $\scrO(v)$) denote the set of paths in~$G$ ending (resp. beginning) at $v$.
Our notation $\scrI$ stands for ``incoming'' and $\scrO$ for ``outgoing''. 
% We consider $\scrI(s)$ as containing only the path of length $0$ at vertex $s$, and $\scrO(t)$ as containing only the path of length $0$ at vertex $t$. 
We define the \defn{relations $\leq_{\scrI(v)}$} and \defn{$\leq_{\scrO(v)}$} on $\scrI(v)$ and~$\scrO(v)$ as follows.

Given paths $Pv, Qv\in\scrI(v)$, let $w\leq v$ be the first vertex after which $Pv$ and $Qv$ coincide. 
If $w$ is the first vertex of $Pv$ or $Qv$, we say that $Pv=_{\scrI(v)} Qv$.
Otherwise let $e_P$ be the edge of $P$ entering $w$ and let $e_Q$ be the edge of $Q$ entering $w$.
Then $Pv <_{\scrI(v)} Qv$ if and only if~$e_P <_{\In(w)} e_Q$.
% Similarly for $vP, vQ\in\scrO(v)$, let $w'\geq v$ be the last vertex before which $vP$ and $vQ$ coincide.
% If $w'$ is the largest vertex of $vP$ or $vQ$, then $vP =_{\scrO(v)} vQ$.
% Otherwise let $e_P'$ be the edge of $P$ leaving $w'$ and let~$e_Q'$ be the edge of $Q$ leaving $w'$.
% Then $vP <_{\scrO(v)} vQ$ if and only if $e_P' <_{\Out(w')} e_Q'$.
The relation~$\scrO(v)$ is defined similarly.

Note that if $Pv$ is a subpath of $Qv$, then $Pv =_{\scrI(v)} Qv$. But, if they do not start at the same vertex, then they are different paths. Therefore, the relation $\leq_{\scrI(v)}$ is not even a partial order. However, if we restrict $\leq_{\scrI(v)}$ (resp. $\leq_{\scrO(v)}$) to the set of paths starting at the source~$s$ (resp. $v$) and ending at $v$ (resp. the sink $t$), then it is a \emph{linear order}.

% \begin{lemma}
% The following hold:
% \begin{enumerate}
%     \item The restriction of $\leq_{\scrI(v)}$ to the set of paths starting at the source $s$ and ending at $v$ is a linear order. 
%     \item The restriction of $\leq_{\scrO(v)}$ to the set of paths starting at $v$ and ending at the sink $t$ is a linear order. 
% \end{enumerate}
% \end{lemma}
% \begin{proof}
% For the proof of (1), it is straight forward to check that the restriction of $\leq_{\scrI(v)}$ to the set of paths starting at the source $s$ and ending at $v$ is reflexive, transitive and antisymmetric, which implies that the relation is a partial order.
% Furthermore, since every pair of paths $Pv$ and $Qv$ starting at the source~$s$ are comparable in the order $\leq_{\scrI(v)}$, we deduce that $\leq_{\scrI(v)}$ is a linear order. 
% A similar argument shows part (2).
% \end{proof}

We say that a vertex $v$ of a path $P$ is an \defn{inner vertex} if $v$ is not the first or last vertex of the path.
If $v$ is an inner vertex of paths $P$ and $Q$, we say that $P$ and $Q$ are \defn{incoherent at $v$} if $Pv <_{\scrI(v)} Qv$ and $vQ <_{\scrO(v)} vP$, or if $Qv <_{\scrI(v)} Pv$ and $vP <_{\scrO(v)} vQ$, and we say that they are \defn{coherent at $v$} otherwise.
Paths $P$ and $Q$ are then said to be \defn{coherent} if they are coherent at each common inner vertex and they are \defn{incoherent} otherwise.
A set of pairwise coherent routes is called a \defn{clique}.
We denote by \defn{$\calC$} the \defn{collection of maximal cliques}. 
Examples of these concepts are illustrated in~\Cref{fig_oruga2_coherent_example}.

\begin{figure}[htb]
    \centering
    %\include{fpsac_oruga2_coherent_example}
    \includegraphics[page=4]{fpsac_allfigures.pdf}
    \caption{Examples of coherent and incoherent routes, and a maximal clique for the given framing of the $\oruga{2}$ graph.}
    \label{fig_oruga2_coherent_example}
\end{figure}

% Given a framed graph $(G,F)$, the convex hull of the indicator vectors of the routes in a maximal clique induced by the framing form a simplex inside the flow polytope~$\calF_{G}$. 
% In the example in~\Cref{fig_oruga2_coherent_example}, there are exactly two maximal cliques;  they correspond to the two triangles of the triangulation of $\calF_{G_2}$ on the left of~\Cref{fig_oruga2_frame_triangulations}. 
% Changing the framing changes the coherence relation and therefore the triangles.
% The right of ~\Cref{fig_oruga2_frame_triangulations} shows the two triangles corresponding to the maximal cliques induced by the other shown framing of the graph.

% The motivation for the definition of a framed graph $(G,F)$ and the induced coherent relation in the set of routes of $G$, is that the collection of simplices associated to cliques give a nice triangulation of the flow polytope $\calF_G$. 
% This is stated in the following proposition, where $\Delta_C$ denotes the convex hull of the indicator vectors of the routes in a maximal clique~$C$.

% \begin{proposition}[{Danilov et al.~\cite{DKK12}}]
% Let $(G,F)$ be a framed graph. 
% The set $\{\Delta_C \mid C \in \calC\}$ is the set of the top-dimensional simplices in a regular unimodular triangulation of $\calF_G$.
% 
% \end{proposition}

The motivation for the definition of a framed graph is that the maximal cliques determined by the framing induce a triangulation of the flow polytope.  
We denote by $\Delta_C$ the convex hull of the indicator vectors of the routes in a maximal clique~$C$.

\begin{proposition}[{Danilov et al.~\cite{DKK12}}]
Let $(G,F)$ be a framed graph. 
The set $\{\Delta_C \mid C \in \calC\}$ is the set of the top-dimensional simplices in a regular unimodular triangulation of $\calF_G$.

\end{proposition}


A triangulation of $\calF_G$ whose facets are the maximal cliques of $(G,F)$ for some framing~$F$ is called a \defn{framed triangulation of $\calF_G$}. 
The framed triangulation of the framing in~\Cref{fig_oruga2_coherent_example} is shown in~\Cref{fig_oruga_graph}.
The following lemma gives properties about adjacent facets of the triangulation. 

\begin{lemma}\label{lem.incoherent_only_on_one_path}
    Let $C\neq C'$ be maximal cliques satisfying $C\smallsetminus \{R\}= C'\smallsetminus \{R'\}$. Then,
    \begin{itemize}
        \item[(i)] The routes $R$ and $R'$ incoherent at some vertex $v$. Furthermore, they are incoherent at every vertex in the maximal path $P_v$ in $R\cap R'$ that contains $v$, and coherent everywhere else. 
        \item[(ii)] The routes $RvR'$ and $R'vR$ are contained in $C\cap C'$.
        % \item[(iii)] The routes $R$ and $R'$ are incoherent only on the vertices of $P_v$.
    \end{itemize}
\end{lemma}

From now on, unless otherwise specified, we draw the framed graphs $(G,F)$ in such a way that the order of the framing of the incoming and outgoing edges at every vertex is \defn{increasing from top to bottom}. 
This has two advantages: we do not need to include the labels of a framing for the incoming and outgoing edges to the figure, and the coherence relation becomes very intuitive because two paths are coherent at a vertex $v$ if they ``\defn{do not cross}'' at $v$, as illustrated in~\Cref{fig_coherent_crossing}. 

\begin{figure}[htb]
    \centering
    %\include{fpsac_coherent_crossing}
    \includegraphics[page=5, scale=1]{fpsac_allfigures.pdf} 
    \caption{The coherence and cw relation between two routes at $v$. }
    \label{fig_coherent_crossing}
\end{figure}


This convention motivates the following definition.
We say that a route $R$ is \defn{clockwise~(cw)} from $R'$ at $v$ 
if $Rv <_{\scrI (v)} R'v$ and $vR' <_{\scrO (v)} vR$. 
We use the \defn{notation~$R <_v^{\cw}R'$} when $R$ is cw from $R'$ at~$v$. 
In particular, $R$ and $R'$ are incoherent at $v$ if and only if $R <_v^{\cw} R'$ or $R' <_v^{\cw} R$.
Note also that $<_v^{\cw}$ is a transitive relation, i.e. if $R <_v^{\cw} R'$ and $R' <_v^{\cw} R''$, then $R <_v^{\cw} R''$. 

\begin{example}[A framed triangulation of the oruga graph]
Let $G_n=\oruga{n}$ be the oruga graph from~\Cref{example_running_oruga}, and let $F$ be the framing that orders the incoming and outgoing edges of $G_n$ from top to bottom. 
The maximal cliques of $(G,F)$ are in bijective correspondence with permutations of $[n]$ as follows.

Given a permutation $[i_1,\dots,i_n]$ of $[n]$, construct a maximal clique consisting of $n+1$ routes $R_0,\dots,R_n$, where $R_k$ is the route containing the top edges $e_{2i_j-1}$ for $1\leq j \leq k$, and the bottom edges $e_{2i_j}$ for $k< j \leq n$. That is, $R_k$ is the route with top edges at positions $i_1,\dots, i_k$ and bottom edges at the positions $i_{k+1},\dots, i_n$. 

The resulting set of routes is a maximal clique, and all the maximal cliques are of this form. 
Moreover, two facets are adjacent if and only if the corresponding permutations can be obtained from each other by swapping two consecutive numbers. 
Thus, the dual graph of this framed triangulation of $\calF_{G_n}$ is the Hasse diagram of the classical weak order of permutations of $[n]$.
\end{example}








\section{Framing lattices}
The weak order from the previous example is known to be a lattice. 
The purpose of this section is to introduce a lattice structure whose Hasse diagram is the dual graph of a framed triangulation of a flow polytope for any framed graph. 
% We will see that this includes many well known examples of remarkable lattices in the literature, providing a unifying framework to study them.


Let $C\neq C'$ be maximal cliques satisfying $C\smallsetminus \{R\}= C'\smallsetminus \{R'\}$.
By~\Cref{lem.incoherent_only_on_one_path}, the routes
$R$ and~$R'$ are incoherent at some point $v$.
If $R <_v^{\cw} R'$, then we say that $R'$ is obtained from $R$ by a \defn{ccw rotation} at $v$. 
In this case, we say that $C'$ is obtained from~$C$ by a \defn{ccw rotation}.
The \defn{framing poset} $\scrL_{G,F} = (\calC, \leqccwrot)$ is the poset on maximal cliques where $C\leqccwrot C'$ if $C'$ can be obtained from $C$ by a sequence of ccw rotations. 
We simply write $C \leq C'$ when the partial order is clear from context.

A \defn{polygon} in a lattice is an interval $[x,y]$ that is the union of two finite maximal chains from $x$ to $y$ that are disjoint except at $x$ and $y$. 
A lattice is said to be \defn{polygonal} if the following two conditions hold: (1) If $y_1$ and $y_2$ are distinct and cover an element $x$, then $[x,y_1\vee y_2]$ is a polygon; and (2) if $y_1$ and $y_2$ are distinct and are covered by an element $x$, then $[y_1\wedge y_2,x]$ is a polygon.

\begin{theorem}
\label{thm.framing_lattice}
    If $(G,F)$ be a framed graph then $\scrL_{G,F}$ is a poset. Moreover, it is a polygonal lattice whose polygons consist of squares, pentagons, or hexagons.
\end{theorem}


Given a lattice $\scrL$, let $E(\scrL)$ denote the set of covering relations of $\scrL$. 
We say that $\scrL$ is an \defn{$\calH\calH$-lattice} if it is finite, semidistributive, polygonal, and there exist a labeling function $\ell: E(\scrL) \to \calL$ where $\calL$ is a set of labels, and a ranking function
$r: \calL \to \mathbb{N}$ satisfying the following condition on every polygon $[x,y]$ of $\scrL$.
Let $x_1$ and $x_2$ denote the two elements covering $x$, and let $y_1$ and $y_2$ denote the two elements covered by $y$, such that $x_1$ and $y_1$ (resp. $x_2$ and $y_2$) belong to the same maximal chain. 
The labeling $\ell$ and rank function $r$ must satisfy: (1) $\ell(x,x_1) = \ell(y_2,y)$ and $\ell(x,x_2) = \ell(y_1,y)$; and
(2) if $t_1,\ldots, t_k$ is a maximal chain in a polygon, then
$$ r(t_1), r(t_k) < r(t_2), r(t_{k-1}) < \cdots < r(t_{\frac{k+1}{2}}) \,\, \text{ if $k$ is odd; and} $$
$$ r(t_1), r(t_k) < r(t_2), r(t_{k-1}) < \cdots < r(t_{\frac{k}{2}}),r(t_{\frac{k}{2}+1}) \,\, \text{ if $k$ is even.} $$

% A lattice is \defn{congruence uniform} if it can be obtained from the one element lattice
% by a sequence of \textit{Day doublings} of intervals. %\cite{Day77}

It is known that every $\calH\calH$-lattice is \defn{congruence uniform}~\cite{CdPBM04}, 
i.e. it can be obtained from the one element lattice
by a sequence of \textit{doublings of intervals}, a simple operation introduced by Alan Day in the seventies, see~\cite{CdPBM04} and the references therein. %\cite{Day77}


%\cite{CdPBM04}

\begin{theorem}\label{thm_HHlattice}
    The framing poset $\scrL_{G,F}$ is an HH lattice. In particular, it is semidistributive and congruence uniform.  
\end{theorem}

The following lemma due to Bj\"orner, Edelman, and Ziegler and the tools developed below are central to prove the above results. We skip most of the details due to space constraints. 

\begin{lemma}(BEZ Lemma \cite[Lemma 9-2.2]{GW16}) \label{lem.BEZ}
Let $P$ be a finite poset with $\widehat{0}$. 
If the join $x\vee y$ exists for every $x,y\in P$ such that $x$ and $y$ cover a common element $z$, then $P$ is a lattice. 
\end{lemma}

To apply the BEZ lemma, we need a characterization of comparability in $\scrL_{G,F}$. 
We say that \defn{$C$ is cw from $C'$} if for all $R \in C$, $R'\in C'$, and $v \in R\cap R'$ we have that $R$ and $R'$ are coherent at $v$ or $R <_v^{\cw} R'$.

\begin{proposition}\label{lem.ccw}
    Let $C$ and $C'$ be maximal cliques. 
    Then $C \leq C'$ if and only if $C$ is cw from~$C'$. 
\end{proposition}

Given two maximal cliques covering a common maximal clique, we construct their join algorithmically. 
Given a set $S$ of pairwise coherent routes, we construct a maximal clique $C_{\max}(S)$ containing $S$ and the ccw-most routes that are coherent with the routes in $S$.
Informally, $C_{\max}(S)$ is obtained by adding the ccw-most routes at each vertex until a maximal clique is formed.
The formal construction is described in Algorithm~\ref{alg.CmaxS}, where~$\leq_{\scrI(v)}^{\rev}$ denotes the reverse order of the linear order $\leq_{\scrI(v)}$.
Similarly, we construct a maximal clique $C_{\min}(S)$ containing $S$ whose routes are as clockwise as possible.
% The algorithm is otherwise the same, but the orders in which $\scrI(v)$ and $\scrO(v)$ are read in Algorithm~\ref{alg.CmaxS} are reversed. That is, we replace $\leq_{\scrI(v)}^{\rev}$ with $\leq_{\scrI(v)}$ and replace $\leq_{\scrO(v)}$ with $\leq_{\scrO(v)}^{\rev}$, where $\leq_{\scrO(v)}^{\rev}$ denotes the reverse order to $\leq_{\scrO(v)}$.
 
\begin{algorithm}
  \caption{The construction of $C_{\max}(S)$}\label{alg.CmaxS}
  {\small
  \begin{algorithmic}[1]
    \State $C_{\max}(S) := S$
    \For{$v \in V(G)$ (in increasing order)}
        \For{$Pv \in \scrI(v)$ (in the order $\leq_{\scrI(v)}^{\rev}$)} \Comment{$Pv$ possibly empty}
            \For{$vQ \in \scrO(v)$ (in the order $\leq_{\scrO(v)}$)} \Comment{$vQ$ possibly empty}
                \If{$PvQ$ is coherent with all routes of $C_{\max}(S)$}
                    \State $C_{\max}(S) := C_{\max}(S) \cup \{PvQ\}$
                    \State \textbf{break} \Comment{This terminates the innermost loop}
                \EndIf
            \EndFor
        \EndFor
    \EndFor  
  \end{algorithmic}
  }
\end{algorithm}


%The maximal clique $C_{\max}(\emptyset)$ for $\mathrm{Oruga}(2)$ is shown on the right of Figure~\ref{fig_oruga2_maxclique_permutation}, and is obtained with Algorithm~\ref{alg.CmaxS} by adding the routes $R_2$, $R_1$, and $R_0$ in that order.




\begin{lemma}\label{lem.CmaxS_is_ccw_maximal}
    The clique $C_{\max}(S)$ is the unique maximal clique with the following property. If a route $R \notin S$ is coherent with all routes in $S$, then for any $R' \in C_{\max}(S)$ and $v \in R\cap R'$ either $R$ and $R'$ are coherent at $v$ or $R' <_v^{\cw} R$. 
    The dual statement holds for $C_{\min}(S)$. 
\end{lemma}



When $S = \emptyset$, we abbreviate $C_{\min} = C_{\min}(\emptyset)$ and $C_{\max} = C_{\max}(\emptyset)$. 
The maximal cliques $C_{\min}$ and $C_{\max}$ are respectively the $\widehat{0}$ and $\widehat{1}$ of $\scrL_{G,F}$. 
The proof of Theorem~\ref{thm.framing_lattice} follows from the next lemma together with the BEZ lemma. 
\begin{lemma}
    Let $C_1$ and $C_2$ be distinct maximal cliques covering a maximal clique $Q$ in $\scrL_{G,F}$ and let $S = C_1\cap C_2$. 
    Then, the following statements hold.
    \begin{itemize}
        \item[(i)] The set of maximal cliques containing $S$ is an interval $I_S = [C_{\min}(S), C_{\max}(S)]$, with $Q = C_{\min}(S)$, $C_1 \neq C_{\max}(S)$, and $C_2 \neq C_{\max}(S)$. 
        \item[(ii)] The interval $I_S$ is a square, pentagon, or a hexagon.
        \item[(iii)] $C_1 \vee C_2$ exists and is $C_{\max}(S)$. 
    \end{itemize}
\end{lemma}

\begin{remark}
    The join of two arbitrary maximal cliques $C$ and $C'$ in $\scrL_{G,F}$ is not $C_{\max}(S)$ for $S = C\cap C'$.
    However, it is possible to compute it with a modified version of Algorithm~\ref{alg.CmaxS}.
\end{remark}

Our proof of~\Cref{thm_HHlattice} relies on a characterization of semidistributive lattices and HH lattices based on the polygons of the lattice. The congruence uniform property follows from being an HH lattice.  

The following result concerns lattice quotients of the framing lattice. It is based on an operation discovered by Yip called an M-move, and was proved independently by González D'León and Yip\footnote{Personal communication.}. 
%
Given a framed graph $(G,F)$ and an oriented edge $(v,w)$ such that $v\neq s$ and $w \neq t$, an M-move applied to $(v,w)$ is the framed graph $(G_{v,w},F_{v,w})$ obtained by replacing the edge $(v,w)$ by the two edges $(s,w)$ and $(v,t)$, while keeping the order of the incoming edges at $w$ and the outgoing edges at $v$. 

\begin{theorem}
    The framing lattice~$\scrL_{G_{v,w},F_{v,w}}$ is a lattice quotient of~$\scrL_{G,F}$.
\end{theorem}

We finish this section with the following enumerative conjecture, which is motivated by~\Cref{sec_crossTamari} and a result in~\cite{CC23}, and is supported by computational evidence.

\begin{conjecture}
    Let $F_1$ and $F_2$ be two framings of $G$. Then, the framing lattices~$\scrL_{G,F_1}$ and~$\scrL_{G,F_2}$ have the same number of linear intervals of length $k$ for every $k\geq 0$.
\end{conjecture}

\section{Examples}

\subsection{The Boolean lattice}

The Boolean lattice $\scrB_n$ is the lattice on the subsets of $[n]$ ordered by inclusion.
We now describe how to obtain $\scrB_n$ as a framing lattice.
Let $G_{B_n}$ be the flow graph with vertex set $\{s,t\}\cup [n]$ and edge set constructed as follows.
For each vertex $i\in [n]$ we add a pair of edges $(s,i)$ and $(s,i)'$ and a pair of edges $(i,t)$ and $(i,t)'$.
All framing lattices of $G_{B_n}$ will be isomorphic, so the choice of framing does not matter. 
However, for convenience we choose $F$ to be a framing with $(s,i) <_{\scrI(i)} (s,i)'$ and $(s,i) <_{\scrO(i)} (s,i)'$ at each $i \in [n]$. 
See the left-most graph and lattice in Figure~\ref{fig.graphs_and_lattices} for an example of $G_{B_3}$ and $\scrB_3$.


    A maximal clique of $(G_{B_n},F)$ contains the routes $\{(s,i),(i,t)\}$ and $\{(s,i)',(i,t)'\}$, and either the route $R_i:=\{(s,i),(i,t)'\}$ or the route $R_i':=\{(s,i)',(i,t)\}$ for each $i\in [n]$.
    For a set $S\subseteq [n]$, define the maximal clique $C_S$ to be the unique maximal clique with routes $R_i'$ with $i\in S$, and $R_i$ with $i\notin S$.
    The map $S\mapsto C_S$ is an order preserving bijection between $\scrB_n$ and $\scrL_{G_{B_n},F}$.
    Therefore, 
    the framing lattice $\scrL_{G_{B_n},F}$ is the Boolean lattice $\scrB_n$. 



\subsection{The lattice of multipermutations}
Given $n$ positive integers $m_1,\dots,m_n$, the set of multipermutations $[a_1,\dots,a_{m_1+\dots+m_n}]$ of $1^{m_1}\cdots n^{m_n}$ forms a lattice whose cover relations are given by interchanging two consecutive values $a_k<a_{k+1}$. The special case $m_i=1$ for all $i$ recovers the classical weak order on permutations.

We define the multioruga graph $\multioruga{m_1,\dots,m_n}$ as the graph on the vertex set $[n+1]$ containing $m_i+1$ edges $e_{i,0},\dots,e_{i,m_i}$ which are drawn from bottom to top between~$i$ and~$i+1$ for $i\in [n]$. The framing $F$ is induced by this drawing (edges ordered from top to bottom). 

The associated flow polytope is a product of simplices $\calF_{\multioruga{m_1,\dots,m_n}}= \Delta_{m_1}\times\dots\times \Delta_{m_n}$ where $\Delta_{m_i}=\conv\{e_{i,0},\dots,e_{i,m_i}\}$. Maximal cliques of the framed triangulation are in bijection with multipermutation as follows. 

Given a multipermutation  $[a_1,\dots,a_{m_1+\cdots+m_n}]$ of $1^{m_1}\cdots n^{m_n}$ and an integer $k$ satisfying \mbox{$0\leq k \leq m_1+\cdots+m_n$}, we let $R_k$ be the route consisting of the edges $e_{1,j_1(k)},\dots,e_{n,j_n(k)}$, where 
$
j_i(k) := |\{k'\leq k:\, a_{k'}=i\}|. 
$
In other words, $j_i(k)$ counts the number of appearances of $i$ up to position $k$ in the multipermutation. 
The collection of routes $R_0$,$\dots$, $R_{m_1+\cdots+m_n}$ is a maximal clique, and all maximal cliques are of this form. A counterclockwise rotation of a route $R_k$ in a maximal clique corresponds to interchanging two consecutive values $a_k<a_{k+1}$ in the multipermutation. 
Thus, the framing lattice $\scrL_{\multioruga{m_1,\dots,m_n},F}$ is the lattice of multipermutations of~$1^{m_1}\cdots n^{m_n}$. 
An example is shown in~\Cref{fig.graphs_and_lattices}.


\subsection{The Cambrian lattice}
Reading's type $A$ $\varepsilon$-Cambrian lattices~\cite{Rea06} are lattices on triangulations of a polygon. 
The parameter $\varepsilon$ is a map 
$\varepsilon: [n] \to \{\pm\}$
that assigns a positive or negative sign to each element of $[n]$.  
We define the polygon $P_{\varepsilon}(n)$ as a convex $(n+2)$-gon with vertices $0,1,\dots,n+1$ ordered from left to right, such that $0$ and $n+1$ are on a horizontal line and $i$ is above this line if $\varepsilon(i)=+$, or below if $\varepsilon(i)=-$.   
The \mbox{$\varepsilon$-Cambrian} lattice is the poset on triangulations of $P_{\varepsilon}(n)$ whose cover relations are increasing slope diagonal flips.

\begin{figure}[htb]
    \centering
    %\include{fpsac_cambrian}
    \includegraphics[page=6, scale=1.1]{fpsac_allfigures.pdf}
    \caption{The polygon $P_\varepsilon(3)$ and the Cambrian caracol graph $\cambrianCaracolGraph{\varepsilon}$ for $\varepsilon = -+-$.}
    \label{fig_fpsac_cambrian}
\end{figure}

Let the \defn{Cambrian caracol graph} $\cambrianCaracolGraph{\varepsilon}$ be the graph with vertex set $\{s,0,1,\dots,n,t\}$ and the following three kinds of edges: 
\begin{itemize}
    \item horizontal edges $(s,0),(0,1),(1,2),\dots,(n-1,n),(n,t)$,
    \item positive edges $(s,a)^+,(a-1,t)^+$ when $\varepsilon(a)=+$ (above the horizontal line), and
    \item negative edges $(s,a)^-,(a-1,t)^-$ when $\varepsilon(a)=-$ (below the horizontal line).
\end{itemize}
The graph $\cambrianCaracolGraph{\varepsilon}$ is independent of $\varepsilon$. 
The framing $F_{\varepsilon}$ is the one induced by the drawing, which depends on $\varepsilon$. 
The routes of $\cambrianCaracolGraph{\varepsilon}$ are in bijection with the diagonals of the polygon~$P_{\varepsilon}(n)$. More precisely, diagonal $ij$ corresponds to the route entering at $i$ exiting at~$j-1$. Under this bijection, two routes are coherent if and only if the corresponding diagonals do not cross; see~\Cref{fig_fpsac_cambrian}. 
Moreover, the framing lattice~$\scrL_{\cambrianCaracolGraph{\varepsilon},F_{\varepsilon}}$ is the $\varepsilon$-Cambrian lattice.
An example is shown in~\Cref{fig.graphs_and_lattices}.


% The $\varepsilon$-Cambrian lattice was generalized to $(\varepsilon,I,\overline{J})$-Cambrian lattices by V. Pilaud~\cite{Pil20}. These more general lattices can also be obtained as framing lattices, and the description will be explained in a longer version of this manuscript.




\subsection{The cross-Tamari lattice}\label{sec_crossTamari}

The cross-Tamari lattice is a new poset structure introduced in this paper which generalizes the alt $\nu$-Tamari lattices of Ceballos and Chenevi\`ere~\cite{CC23}. 

% Let $D$ be a set lattice points in $\bbZ^2$. 
% We say that $D$ is \defn{horizontally connected} if for any pair of points $(x,y)$ and $(x',y)$ in $D$ we have $(z,y) \in D$ for all $x< z < x'$. 
% Similarly, we say that $D$ is \defn{vertically connected} if for any pair of points $(x,y)$ and $(x,y')$ in $D$ we have $(x,z) \in D$ for all $y< z < y'$. 
% Let $\row_D(z)$ denote the set of points in $D$ with $y$-coordinate $z$ and let $\col_D(z)$ denote the set of points with $x$-coordinate $z$. 
% We say that~$D$ is \defn{vertically nested} if the $y$-coordinates of the points in $\col_D(v)$ are a subset of the $y$-coordinates of the points in $\col_D(w)$ whenever $|\col_D(v)|\leq |\col_D(w)|$.
% Similarly, we say that $D$ is \defn{horizontally nested} if the $x$-coordinates of the points in $\row_D(v)$ are a subset of the $x$-coordinates of the points in $\row_D(w)$ whenever $|\row_D(v)|\leq |\row_D(w)|$.
% A set of lattice points $D \subseteq \bbZ^2$ is a \defn{cross-shaped grid} if it is both horizontally and vertically connected, and horizontally and vertically nested.

Let $D$ be a set lattice points in $\bbZ^2$. 
We say that $D$ is \defn{horizontally connected} if for any pair of points $(x,y)$ and $(x',y)$ in $D$ we have $(z,y) \in D$ for all $x< z < x'$. 
Let $\row_D(z)$ denote the set of points in $D$ with $y$-coordinate $z$. 
We say that $D$ is \defn{horizontally nested} if the $x$-coordinates of the points in $\row_D(v)$ are a subset of the $x$-coordinates of the points in $\row_D(w)$ whenever $|\row_D(v)|\leq |\row_D(w)|$.
Similarly, we define \defn{vertically connected} and \defn{vertically nested}. 
A set of lattice points $D \subseteq \bbZ^2$ is a \defn{cross-shaped grid} if it is both horizontally and vertically connected, and horizontally and vertically nested.


If $D$ has $a$ columns and $b$ rows, 
it is convenient to assign positions to the points in~$D$ according to a relabeling of the columns with the numbers $1,\dots ,a$ and the rows with $\overline{1},\dots, \overline{b}$, in some order. We identify a point $p\in D$ with its \defn{position} $p=(v,\overline{w})$ where $v$ is the label of column and $\overline{w}$ is the label of the row of the point. 
We denote by $\ell(v)$ (resp.~$\ell(\overline{w})$) the number of elements of $D$ in column $v$ (resp. row $\overline{w}$). A \defn{proper labeling} of the rows and columns of $D$ is a labeling satisfying the following conditions: 
\begin{itemize}
    \item the column labels form a unimodular sequence\footnote{increases and then decreases} and $\ell(v)<\ell(v')$ implies $v<v'$
    \item the row labels form a unimodular sequence and $\ell(\overline{w})<\ell(\overline{w}')$ implies $w<w'$
\end{itemize}

Intuitively, this means that we label the rows and columns from shortest to longest from the outside towards the center. Such a labeling is not unique if $D$ has rows or columns of the same length, but any proper labeling will be good for our purposes. 
An example of a cross-shaped grid and a proper labeling of its rows and columns is shown in~\Cref{fig_fpsac_crossTamari_grid_graph}. In this example, the bottom-left corner (colored blue) has position $(4,\overline{2})$.

\begin{figure}[htb]
    \centering
    %\include{fpsac_crossTamari_grid_graph}
    \includegraphics[page=7, scale=1.05]{fpsac_allfigures.pdf}
    \caption{A cross-shaped grid $D$ with a proper labeling $L$ of its rows and columns (left). The $(D,L)$-caracol graph $\crossGridGraph{D,L}$ with the routes corresponding to the marked points in $D$ highlighted (right).}
    \label{fig_fpsac_crossTamari_grid_graph}
\end{figure}


Let $D$ be a cross-shaped grid.
Two distinct points $p,p'\in D$ are \defn{incompatible} if one of them is strictly north-east of the other and every lattice point in the smallest rectangle containing $p$ and $p'$ belongs to $D$.  
Two points are \defn{compatible} if they are not incompatible. 
A \defn{maximal filling} of a cross-shaped grid is a maximal set of pairwise compatible points.
If two maximal fillings $M\neq M'$ differ by one single element $M\smallsetminus\{p\}=M'\smallsetminus\{p'\}$ where $p'$ is located strictly north-east of $p$, then we say the $M'$ is obtainable from $M$ by an \defn{increasing flip}.
The \defn{cross-Tamari order} $\Tam(D)$ is the poset of maximal fillings of $D$ where $M\preceq_D M'$ if $M'$ can be obtained from $M$ by a sequence of increasing flips.    

% \begin{definition}
% The \defn{cross-Tamari order} $\Tam(D)$ is the poset of maximal fillings of $D$ where $M\preceq_D M'$ if $M'$ can be obtained from $M$ by a sequence of increasing flips.    
% \end{definition}

The case where $D$ is the set of lattice points weakly above a staircase shape recovers the classical Tamari lattice. If $D$ is the set of lattice points weakly above a given lattice path~$\nu$ then we recover of $\nu$-Tamari lattice of Pr\'eville-Ratelle and Viennot~\cite{PV17}. Cross-Tamari lattices also include the alt $\nu$-Tamari lattices~\cite{CC23} and the $\varepsilon$-Cambrian lattices~\cite{Rea06}.   

Next, we will show that the cross-Tamari order can be obtained as a framing lattice. In particular, this implies that it is a lattice, a non-trivial fact. 

Let $D$ be a cross-shaped grid and $L$ be a proper labeling of its columns and rows with the numbers $[a]$ and $[\overline b]$. 
We define the \defn{$(D,L)$-caracol graph} $\crossGridGraph{D,L}$ as the graph on the vertex set $\{s,t\}\sqcup [a] \sqcup [\overline b]$, whose edges are given as follows.

First we define a linear order $\prec$ on the vertices, whose minimal element is $s$, maximal element is $t$, and the following three relations hold: 
$i_2\prec i_1$ when $i_1<i_2$,
$\overline{j}_1\prec \overline{j}_2$ when $j_1<j_2$, and
$x\prec \overline{y}$ when $(x,\overline{y})\in D$. 
% \begin{itemize}
%     \item $b\prec a$ when $a<b$,
%     \item $\overline{a}\prec \overline{b}$ when $a<b$, and
%     \item $x\prec \overline{y}$ when $(x,\overline{y})\in D$. 
% \end{itemize}
The fact that $\prec$ is a linear order follows from the conditions on $D$ and $L$. We place the vertices $\{s,t\}\sqcup [a] \sqcup [\overline b]$ in a horizontal line following the linear order $\prec$ and draw an edge between each pair of consecutive elements. This looks like $s - a - \dots - \overline{b} - t$.
We add additional edges $(s,i)$ and $(\overline{j},t)$ as follows.
For $i \in [a-1]$, we draw an edge $(s,i)$ below the horizontal line if column label $i$ is on the right of column label $a$, and above if it is on the left. 
For $j\in [b-1]$,  we draw an edge $(\overline{j},t)$ below the horizontal line if row label $\overline{j}$ is below of row label $\overline{b}$, and above if it is above. The resulting graph is $\crossGridGraph{D,L}$, and the framing $F_{D,L}$ is the framing induced by our drawing; see~\Cref{fig_fpsac_crossTamari_grid_graph} for an example.

The points in $D$ are in bijection with the routes of $\crossGridGraph{D,L}$. More precisely, the point $(i,\overline{j})$ corresponds to the route entering at $i$ and exiting at $\overline{j}$. 
Under this bijection, two points in $D$ are incompatible if and only if the corresponding routes are incoherent. 
Moreover, the framing lattice~$\scrL_{\crossGridGraph{D,L},F_{D,L}}$ is the cross-Tamari lattice~$\Tam(D)$.  
An example is shown in~\Cref{fig.graphs_and_lattices}.






\subsection{Other examples}
The previous examples are only a small selection of well studied lattices that appear as examples of framing lattices. Other examples include the Grassmann-Tamari lattices of Santos, Stump, and Welker, the grid Tamari lattices of McConville, the $(\varepsilon,I,\overline{J})$-Cambrian lattices of Pilaud, the permutree lattices of Pilaud and Pons, the $s$-weak order of Ceballos and Pons, and tau-Tilting posets for certain gentle algebras. The description of these lattices as framing lattices essentially follows from bijections presented in other works, and will be discussed in more detail in a longer version of this manuscript. 

% Other examples include Grassmann-Tamari lattices, grid Tamari lattices, $(\varepsilon,I,\overline{J})$-Cambrian lattices, permutree lattices, the $s$-weak order, and tau-Tilting posets for certain gentle algebras. The description as framing lattices essentially follows from bijections presented in other works, and will be discussed in a longer version of this manuscript. 


\printbibliography



\end{document}
