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

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

\usepackage{enumerate, paralist, xargs, xcolor, dsfont}
\usepackage[shortlabels, inline]{enumitem}
%\usepackage[noabbrev,capitalise]{cleveref}
\graphicspath{{figures/}}
\makeatletter\def\input@path{{figures/}}\makeatother
\usepackage{ulem}\normalem
\usepackage{tikz}
\usetikzlibrary{trees, decorations, decorations.markings, shapes, arrows, matrix, calc, fit, intersections, patterns, angles}

% theorems
\newtheorem{theorem}{Theorem}%[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
%\theoremstyle{remark} - TCS
\newtheorem{example}[theorem]{Example}

% math special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\I}{\mathbb{I}} % set of integers
\newcommand{\HH}{\mathbb{H}} % hyperplane
\newcommand{\K}{\mathbb{K}} % field
\newcommand{\fA}{\mathfrak{A}} % alternating group
\newcommand{\fB}{\mathfrak{S}^\textsc{b}} % signed symmetric group
\newcommand{\cA}{\mathcal{A}} % algebra
\newcommand{\cC}{\mathcal{C}} % collection
\newcommand{\cS}{\mathcal{S}} % ground set
\newcommand{\uR}{\underline{R}} % underline set
\newcommand{\uS}{\underline{S}} % underline set
\newcommand{\uT}{\underline{T}} % underline set
\newcommand{\oS}{\overline{S}} % overline set
\newcommand{\ucS}{\underline{\cS}} % underline ground set
\renewcommand{\c}[1]{\mathcal{#1}} % caligraphic letters
\renewcommand{\b}[1]{\boldsymbol{#1}} % bold letters
\newcommand{\bb}[1]{\mathbb{#1}} % bb letters
\newcommand{\f}[1]{\mathfrak{#1}} % frak letters
\newcommand{\h}{\widehat} % hat letters

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} % big set notation
\newcommand{\Bigset}[2]{\Big\{ #1 \;\Big|\; #2 \Big\}} % Big set notation
\newcommand{\setangle}[2]{\left\langle #1 \;\middle|\; #2 \right\rangle} % set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\left\langle \, #1 \; \middle| \; #2 \, \right\rangle} % dot product
\newcommand{\bigdotprod}[2]{\big\langle \, #1 \; \big| \; #2 \, \big\rangle} % big dot product
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
\newcommand{\one}{\b{1}} % the all one vector
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:
\newcommand{\simplex}{\b{\triangle}} % simplex
\renewcommand{\implies}{\Rightarrow} % imply sign
\newcommand{\transpose}[1]{{#1}^t} % transpose matrix

% operators
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\vect}{vect} % linear span
\DeclareMathOperator{\cone}{cone} % cone hull
\DeclareMathOperator{\inv}{inv} % inversions
\DeclareMathOperator{\Binv}{inv^\textsc{b}} % inversions
\DeclareMathOperator{\Ima}{Im} % image
\DeclareMathOperator{\Vol}{Vol} % (mixed) volume

% others
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % exempli gratia
\newcommand{\apriori}{\textit{a priori}} % a priori
\newcommand{\viceversa}{\textit{vice versa}} % vice versa
\newcommand{\versus}{\textit{vs.}~} % versus
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\perse}{\textit{per se}} % per se
\newcommand{\ordinal}{\textsuperscript{th}} % th for ordinals
\newcommand{\ordinalst}{\textsuperscript{st}} % st for ordinals
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\definecolor{green}{RGB}{57,181,74} % darkblue color
\definecolor{violet}{RGB}{147,39,143} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\textsl{\darkblue #1}} % emphasis of a definition
\newcommand{\para}[1]{\paragraph{\noindent{\uline{#1.}}}} % paragraph
\newcommand{\paraspace}[1]{\bigskip\noindent\textbf{#1.}\medskip} % paragraph more space
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures
%\renewcommand\labelitemi{$\diamond$} % redefine itemize default symbol

% marginal comments
\usepackage{todonotes}
\newcommand{\vincent}[1]{\todo[color=blue!30]{\rm #1 \\ \hfill --- V.}}

% lattices
\newcommand{\meet}{\wedge} % meet
\newcommand{\join}{\vee} % join
\newcommand{\bigMeet}{\bigwedge} % meet
\newcommand{\bigJoin}{\bigvee} % join
\newcommandx{\projDown}[1][1={}]{\smash{\pi_\downarrow^{#1}}} % down projection map
\newcommandx{\projUp}[1][1={}]{\smash{\pi^\uparrow_{#1}}} % up projection map
\newcommand{\con}{\mathrm{con}} % congruence

% acyclic reorientation posets
\newcommandx{\RO}[1][1=D]{\mathcal{R}_{#1}} % reorientation lattice
\newcommandx{\AR}[1][1=D]{\mathcal{AR}_{#1}} % acyclic reorientation poset
\newcommandx{\restrictionMap}[1][1={D,D'}]{\phi_{#1}} % restriction map
\newcommandx{\inverseRestrictionMap}[1][1={D,D'}]{\psi_{#1}} % inverse restriction map

% ropes
\newcommand{\rope}{\rho} % rope
\newcommand{\diagram}{\delta} % rope diagram
\newcommand{\up}{\triangle} % triangle up
\newcommand{\down}{\bigtriangledown} % triangle down

% quotients
\newcommand{\decorationDown}{\mho} % decoration down
\newcommand{\decorationUp}{\Omega} % decoration up

% geometry
\newcommandx{\PR}[1][1={\c{H},\polytope{B}}]{\mathcal{R}_{#1}} % poset of regions
\newcommandx{\Arrang}[1][1=D]{\mathcal{H}_{#1}} % arrangement
\newcommandx{\Fan}[1][1=D]{\mathcal{F}_{#1}} % fan
\newcommand{\polytope}[1]{\mathds{#1}} % font polytope
\newcommandx{\Zono}[1][1=D]{\polytope{Z}_{#1}} % zonotope
\newcommandx{\Asso}[1][1=n]{\polytope{A}_{#1}} % associahedron
\newcommandx{\shardPolytope}[1][1=\rope]{\polytope{SP}_{#1}} % shard polytope
\newcommandx{\quotientope}[1][1=\equiv]{\polytope{Q}_{#1}} % quotientope
\newcommand{\shard}{\Sigma} % shard
\newcommand{\shards}{\b{\Sigma}} % shards

%% define your title in the usual way
\title{Acyclic Reorientation Lattices and Their Lattice Quotients}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[V.~Pilaud]{Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. Supp.~by ANR CAPPS~17\,CE40\,0018 and CHARMS~19\,CE40\,0017.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau, 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{
We consider acyclic reorientation posets of directed acyclic graphs.
We characterize those which are lattices and provide formulas to compute meets and joins in these lattices.
We next characterize those which are distributive, semidistributive, congruence normal, or congruence uniform lattices.
In the latter case, we introduce a combinatorial gadget to encode the join irreducibles acyclic reorientations and exploit it to describe the canonical representations, the congruence lattices, and the polytopal realizations of the quotients of these acyclic reorientation lattices.
}

%% put your French abstract here, or comment this out if you don't have one
\resumetitle{R\'esum\'e}
\resume{
Nous consid\'erons les ordres partiels sur les r\'eorientations acycliques des graphes orient\'es acycliques.
Nous caract\'erisons ceux qui sont des treillis et donnons des formules pour calculer les bornes inf\'erieures et sup\'erieures dans ces treillis.
Nous caract\'erisons ensuite ceux qui sont des treillis distributifs, semi-distributifs, congruence normaux, ou congruence uniformes.
Dans le dernier cas, nous introduisons des gadgets combinatoires qui encodent les r\'eorientations acycliques sup-irr\'eductibles et les exploitons pour d\'ecrire les repr\'esentations canoniques, les treillis de congruences, et les r\'ealisations polytopales des quotients de ces treillis de r\'eorientations acycliques.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{directed graphs, acyclic orientations, graphical zonotopes, lattices}

%% 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, ie. [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{acyclicReorientationLattices.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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Fix a (finite and simple) directed acyclic graph~$D$.
Consider the poset~$\AR$ of all acyclic reorientations of~$D$, ordered by inclusion of their sets of reversed arcs (with respect to~$D$).
Its minimal element is~$D$, its maximal element is the reverse of~$D$, its cover relations are given by flipping a single arc, and it is clearly self-dual under reversing all arcs.
For instance, $\AR$ is (isomorphic to) the boolean lattice when~$D$ is a forest, and the weak order on permutations when~$D$ is a tournament.
See \cref{fig:acyclicReorientationPosets}.

These acyclic reorientations posets and the underlying flip graphs have been extensively studied, in particular for counting~\cite{Stanley-acyclicOrientations}, traversing~\cite{SavageSquireWest}, and generating~\cite{BarbosaSzwarcfiter,Squire} all acyclic orientations of a graph.
Here, we consider acyclic reorientation posets from a lattice theoretic perspective: after characterizing the directed acyclic graphs~$D$ for which~$\AR$ is a lattice, we explore lattice properties of~$\AR$, in particular the combinatorics and geometry of the lattice quotients of~$\AR$ when it is semidistributive.
The prototypical example is the Tamari lattice~\cite{Tamari} seen as quotient of the weak order, its connection with non-crossing partitions, and its realization by the associahedron \mbox{of~\cite{Loday,ShniderSternberg}}.

Many details and all proofs omitted in this extended abstract can be found in~\cite{Pilaud-acyclicReorientationLattices}.

\begin{figure}
	\centerline{
		\begin{tabular}{c@{\;}c@{\;}c@{\;}c}
			boolean lattice & 
			weak order lattice &
			another lattice & 
			not a lattice
			\\
			\includegraphics[scale=.84]{acyclicReorientationPoset1} & 
			\includegraphics[scale=.84]{acyclicReorientationPoset7} &
			\includegraphics[scale=.84]{acyclicReorientationPoset5} & 
			\includegraphics[scale=.84]{acyclicReorientationPoset6}
		\end{tabular}
	}
	\caption{Some acyclic reorientation posets. The first three are lattices while the fourth is not. The first is boolean as $D$ is a forest, the second is the weak order as $D$ is a tournament. The red arcs are reversed while the green arcs are not.}
	\label{fig:acyclicReorientationPosets}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Acyclic reorientation lattices}

Recall that the \defn{transitive reduction} (resp.~\defn{transitive closure}) of~$D$ is the directed graph obtained by deleting from (resp.~adding to) $D$ all arcs whose endpoints are connected by a directed path in~$D$ of length at least~$2$.
These operations clearly play an important role for acyclic reorientations: for instance, note that an arc in an acyclic reorientation~$E$ of~$D$ is flippable if and only it belongs to the transitive reduction of~$E$.

In this paper, we say that $D$ is \defn{vertebrate} when the transitive reduction of any induced subgraph of~$D$ is a forest.
For instance, any forest and any tournament is vertebrate.
%Note that it is important to check all induced subgraphs of~$D$: there are directed acyclic graphs whose transitive reduction is a forest, but containing an induced subgraph whose transitive reduction is not a forest.
Our starting observation is the following result illustrated in \cref{fig:acyclicReorientationPosets}.

\begin{theorem}
\label{thm:characterizationLattice}
The acyclic reorientation poset~$\AR$ is a lattice if and only if $D$ is vertebrate.
\end{theorem}

There are at least two possible proofs of \cref{thm:characterizationLattice}.
The first is to observe that the acyclic reorientation poset of a vertebrate directed acyclic graph can be obtained from the acyclic reorientation lattice of its transitive reduction by a sequence of convex doublings~\cite{Day}.
The second is to characterize the sets of arcs of~$D$ whose reorientation is acyclic, and to use it to describe the join and meet operations in the acyclic reorientation lattice of a vertebrate directed acyclic graph.
We now sketch the second approach.

It is classical that a subset~$B$ of~$\smash{\binom{[n]}{2}}$ is the inversion set of a permutation of~$[n]$ if and only if both~$B$ and~$\smash{\binom{[n]}{2}} \ssm B$ are transitive.
% This generalizes to the following characterization of the reversed sets of the acyclic reorientations of~$D$.
We say that a subset~$B$ of arcs of~$D$ is 
\begin{enumerate*}[(i)]
\item \defn{closed} if all arcs of~$D$ in the transitive closure of~$B$ belong to~$B$, 
\item \defn{coclosed} if its complement is closed, and 
\item \defn{biclosed} if it is both closed and coclosed.
\end{enumerate*}
%We obtain the following.
%For instance:
%\begin{itemize}
%\item when~$D$ is a forest, any subset of~$A$ is biclosed, and 
%\item when~$D$ is a tournament, $B \subseteq A$ is biclosed if and only if both~$B$ and~$A \ssm B$ are transitive.
%\end{itemize}
%The latter is a classical characterization of inversion sets of permutations, which generalizes to vertebrate directed acyclic graphs as follows.

\begin{proposition}
\label{prop:biclosed}
If~$D$ is vertebrate, a set of edges is biclosed if and only if its reorientation is~acyclic.
\end{proposition}

%Note that when $D$ is not vertebrate, any set whose reorientation is acyclic is still biclosed, but the converse fails.
%See for instance \cref{fig:acyclicReorientationPosets}. %, where each of the two directed paths from the source to the sink of~$D$ forms a biclosed set whose reorientation is not acyclic.
%
With \cref{prop:biclosed} at hand, we can refine \cref{thm:characterizationLattice} as follows.
For the weak order on permutations, it is well-known that, for any permutations~$\pi_1, \dots, \pi_k$ of~$[n]$, the inversion set of $\pi_1 \join \cdots \join \pi_k$ (resp.~of $\pi_1 \meet \cdots \meet \pi_k$) is the transitive closure (resp.~the complement of the transitive closure) of the inversion sets (resp.~of the complements of the inversion sets) of~$\pi_1, \dots, \pi_k$.
This generalizes for vertebrate directed acyclic graphs. % as follows.
%We shall in fact refine this statement, providing an explicit description of the join and the meet of a subset~$E_1, \dots, E_k$ of acyclic reorientations of~$D$.
%Let us start with two classical examples:
%\begin{itemize}
%\item when~$D$ is a forest, the reversed set of~$E_1 \join \dots \join E_k$ (resp.~unvreversed set of~$E_1 \meet \dots \meet E_k$) is the union of the reversed (resp.~unreversed) sets of~$E_1, \dots, E_k$, so that~$\AR$ is boolean, % $\inv(E_1 \join \dots \join E_k) = \inv(E_1) \cup \dots \cup \inv(E_k)$ and $\inv(E_1 \meet \dots \meet E_k) = \inv(E_1) \cap \dots \cap \inv(E_k)$. 
%\item when~$D$ is a tournament, the reversed set of~$E_1 \join \dots \join E_k$ (resp.~unreversed set of~${E_1 \meet \dots \meet E_k}$) is the transitive closure of the union of the reversed (resp.~unreversed) sets of~$E_1, \dots, E_k$.
%\end{itemize}
%This generalizes to vertebrate directed acyclic graphs as follows.

\begin{theorem}
\label{thm:joinMeet}
If $D$ is vertebrate, then the join (resp.~meet) of some acyclic reorientations~$E_1, \dots, E_k$ of~$D$ is obtained by reversing all arcs of~$D$ that belong (resp.~do not belong) to the transitive closure of the arcs reversed (resp.~not reversed) in at least one of the reorientations~$E_1, \dots, E_k$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Lattice properties}

In this section, we assume that~$D$ is vertebrate and we study classical lattice properties of the acyclic reorientation lattice~$\AR$, illustrated in \cref{fig:distributiveSemidistributive}.
We refer to~\cite{GratzerWehrung-LatticeTheory} for a detailed reference on these lattice properties and just briefly recall the needed definitions. % and characterizations of these properties.

\begin{figure}[b]
	\centerline{
		\begin{tabular}{c@{\qquad}c@{\qquad}c}
			distributive &
			semidistributive &
			not semidistributive
			\\
			\includegraphics[scale=.84]{acyclicReorientationPoset1} &
			\includegraphics[scale=.84]{acyclicReorientationPoset4} &
			\includegraphics[scale=.84]{acyclicReorientationPoset5}
		\end{tabular}
	}
	\caption{Some acyclic reorientation lattices. The first is distributive, the second is not distributive but semidistributive, the third is not semidistributive. They are all congruence normal, hence the first two are also congruence uniform.}
	\label{fig:distributiveSemidistributive}
\end{figure}

%%%%%%%%%%%
%
%\subsection{Join and meet irreducibles}
%\label{subsec:joinMeetIrreducibles}
%
Before starting, recall first that an element~$x$ is \defn{join} (resp.~\defn{meet}) \defn{irreducible} if it covers (resp.~is covered by) a unique element denoted~$x_\star$ (resp.~$x^\star$).
For instance, the join (resp.~meet) irreducibles of the boolean lattice are the singletons (resp.~complements of singletons), and the join (resp.~meet) irreducibles in the weak order on permutations are the permutations with a single descent (resp.~ascent).
More generally, it is immediate that an acyclic reorientation~$E$ of~$D$ is join (resp.~meet) irreducible in~$\AR$ if and only if the transitive reduction of~$E$ contains a single reversed (resp.~not reversed) arc.

%These examples generalize as follows.
%
%\begin{proposition}
%\label{prop:joinIrreducibles}
%The following assertions are equivalent for an acyclic reorientation~$E$ of~$D$:
%\begin{compactenum}[(i)]
%\item $E$ is a join (resp.~meet) irreducible of~$\AR$,
%\item the transitive reduction of~$E$ contains a single reversed (resp.~not reversed) arc.
%%\item there is an arc~$a$ of~$D$ such that~$E$ is a minimal (resp.~maximal) element of the fiber of the reverse of~$a$ (resp.~of~$a$) under the restriction map~$\restrictionMap[a]$ from~$D$ to~$\{a\}$.
%\end{compactenum}
%%Fix an arc~$a$ of~$D$, with reverse~$\overline a$, and let~$\restrictionMap[a]$ be the restriction map from~$D$ to~$\{a\}$.
%%Each minimal (resp.~maximal) element in the fiber of~$\overline a$ (resp.~of~$a$) under~$\restrictionMap[a]$ is a join (resp.~meet) irreducible of~$\AR$.
%%Moreover, all join and meet irreducibles of~$\AR$ are obtained this way.
%\end{proposition}
%
%%\begin{corollary}
%%\label{coro:numberJoinMeetIrreducibles}
%%The number of join (resp.~meet) irreducible elements of~$\AR$ is at least~$|A|$.
%%\end{corollary}

%%%%%%%%%%

\subsection{Distributivity and semidistributivity}
\label{subsec:semidistributivity}

A finite lattice~$(L, \le, \meet, \join)$ is \defn{distributive} if~$x \join (y \meet z) = (x \join y) \meet (x \join z)$ (or equivalently $x \meet (y \join z) = (x \meet y) \join (x \meet z)$) for any~$x, y, z \in L$.
%The fundamental theorem for distributive lattices affirms that $L$ is distributive if and only if it is isomorphic to the lattice of lower ideals of its join irreducible poset. % (or equivalently of upper ideals of its meet irreducible poset).
The following statement says that an acyclic reorientation lattice is distributive if and only if it is a boolean lattice.

\begin{proposition}
\label{prop:distributive}
The poset~$\AR$ is a distributive lattice if and only if~$D$ is a forest.
\end{proposition}

%We now discuss semidistributivity and its characterizations.
%For any cover relation~$x \lessdot y \in L$, we define~$K_\join(x,y) \eqdef \set{z \in L}{x \join z = y}$.
%Note that any minimal element of~$K_\join(x,y)$ is join irreducible.
A finite lattice~$(L, \le, \meet, \join)$ is \defn{join semidistributive} if the equality $x \join y = x \join z$ implies the distributivity law~${x \join (y \meet z) = x \join y}$ for any~$x, y, z \in L$.
Equivalently, $L$ is join semidistributive if for any cover relation~$x \lessdot y$ in~$L$, the set~$K_\join(x,y) \eqdef \set{z \in L}{x \join z = y}$ has a unique minimal element~$k_\join(x,y)$.
Note that~$k_\join(x,y)$ is join irreducible.
%Note that the maximal elements of $K_\join(x,y)$ are always join irreducible.
%In particular we define~$\kappa_\join(m) \eqdef k_\join(m, m^\star)$ for a meet irreducible~$m$ of~$L$.
%Equivalently, $L$ is join semidistributive if for any meet irreducible~$m$ of~$L$, the set~$\set{x \in L}{x \join m = m^\star}$ has a unique minimum element denoted~$\uline{\kappa}(m)$.
The \defn{meet semidistributivity} and the maps~$K_\meet$ and $k_\meet$ are defined dually.
A lattice~$L$ is \defn{semidistributive} if it is both join and meet semidistributive.
%In this case, the maps~$\kappa_\join$ and~$\kappa_\meet$ are inverse bijections between the meet irreducible and the join irreducible elements of~$L$.

Our next statement characterizes semidistributivity for acyclic reorientation lattices.
%We say that~$D$ is \defn{filled} when the following equivalent conditions are fulfilled:
%\begin{compactitem}
%\item for any directed path~$\pi$ in~$D$, if the arc joining the endpoints of~$\pi$ belongs to~$D$, then all arcs joining any two vertices of~$\pi$ also belong~to~$D$,
%\item the transitive support of any arc~$a$ of~$D$ induces a tournament in~$D$,
%\item for any arc~$(u,v)$ in~$D$ and any vertex~$w$ in the transitive support of~$(u,v)$ minus~$\{u,v\}$, both arcs~$(u,w)$ and~$(w,v)$ also belong to~$D$,
%\end{compactitem}
%where the \defn{transitive support} of an arc~$a$ of~$D$ is the set of vertices of~$D$ that appear along a directed path in~$D$ joining the endpoints of~$a$ (or equivalently along the directed path in the transitive reduction of~$D$ joining the endpoints of~$a$).
We say that~$D$ is \defn{filled} when for any directed path~$\pi$ in~$D$, if the arc joining the endpoints of~$\pi$ belongs to~$D$, then all arcs joining any two vertices of~$\pi$ also belong~to~$D$.
From now on, we abbreviate vertebrate and filled by \defn{skeletal}.
%Note that chordful (meaning that any cycle induces a clique) implies skeletal, and that skeletal implies chordal (meaning that there is no induced cycle of length at least~$4$), but that both reverse implications are wrong.
For instance, any forest and any tournament is skeletal.
In fact, it is not difficult to check that the skeletal directed acyclic graphs are precisely the directed forests on which some directed paths are replaced by tournaments.
For example, the first two graphs of \cref{fig:distributiveSemidistributive} are skeletal.

\begin{proposition}
\label{prop:semidistributive}
The poset~$\AR$ is a semidistributive lattice if and only if~$D$ is skeletal.
\end{proposition}

%\begin{figure}
%	\centerline{
%		\begin{tabular}{c@{\quad}c@{\quad}c}
%			\includegraphics[scale=.9]{acyclicReorientationPoset2} &
%%			\includegraphics[scale=.9]{acyclicReorientationPoset3} &
%			\includegraphics[scale=.9]{acyclicReorientationPoset4} &
%			\includegraphics[scale=.9]{acyclicReorientationPoset7}
%			\\[.2cm]
%			\includegraphics[scale=.9]{canonicalJoinComplex2} &
%%			\includegraphics[scale=.9]{canonicalJoinComplex3} &
%			\includegraphics[scale=.9]{canonicalJoinComplex4} &
%			\includegraphics[scale=.9]{canonicalJoinComplex7}
%%			\\[.2cm]
%%			\includegraphics[scale=.9]{canonicalJoinComplexRopes2} &
%%			\includegraphics[scale=.9]{canonicalJoinComplexRopes3} &
%%%			\includegraphics[scale=.9]{canonicalJoinComplexRopes4} &
%%			\includegraphics[scale=.9]{canonicalJoinComplexRopes7}
%		\end{tabular}
%	}
%	\caption{Three semidistributive acyclic reorientation lattices (top) and their canonical join complexes (bottom). The rightmost lattice is isomorphic to the weak order on permutations.}
%	\label{fig:canonicalJoinComplexes}
%\end{figure}

Semidistributivity enables to consider canonical representations.
A \defn{join representation} of~$x \in L$ is a subset~$J \subseteq L$ such that~$x = \bigJoin J$.
Such a representation is \defn{irredundant} if~${x \ne \bigJoin J'}$ for any strict subset~$J' \subsetneq J$.
The irredundant join representations of an element~$x \in L$ are ordered by containement of the lower ideals of their elements, \ie~$J \le J'$ if and only if for any~$y \in J$ there exists~$y' \in J'$ such that~$y \le y'$ in~$L$.
The \defn{canonical join representation} of~$x$ is the minimal irredundant join representation of~$x$ for this order when it exists.
%The \defn{meet representation} and \defn{canonical meet representations} are defined dually.
Its elements are called \defn{canonical joinands} of~$x$.
The \defn{canonical meet representations} and the \defn{canonical meetands} are defined dually.

A classical result affirms that a finite lattice~$L$ is join (resp.~meet) semidistributive if and only if any element of~$L$ admits a canonical join (resp.~meet) representation.
Moreover, in a join (resp.~meet) semidistributive lattice, the canonical join (resp.~meet) representation of~$y \in L$ is~$y = \bigJoin_{x \lessdot y} k_\join(x, y)$ (resp.~$y = \bigMeet_{y \lessdot z} k_\meet(y, z)$).
%, where~$k_\join(x,y)$ is the minimal element of~$K_\join(x,y) \eqdef \set{z \in L}{x \join z = y}$ (resp.~$k_\meet(y,z)$ is the maximal element of~$K_\meet(y,z) \eqdef \set{x \in L}{x \meet y = z}$).
%
Combining this description with \cref{prop:semidistributive}, we obtain the following description generalizing~\cite{Reading-arcDiagrams}.
%join (resp.~meet) canonical representations in the acyclic reorientation lattice, generalizing the description of~\cite{Reading-arcDiagrams}.
%An alternative description is presented later in \cref{prop:canonicalJoinMeetComplex} in terms of ropes.

\begin{proposition}
\label{prop:canonicalJoinMeetRepresentation}
Assume that~$D$ is skeletal.
The canonical join (resp.~meet) representation of an acyclic reorientation~$E$ of~$D$ is given by~$E = \bigJoin_a E_a$ (resp.~$E = \bigMeet_a E_a$) where:
\begin{compactitem}
\item $a$ runs over all arcs of~$D$ reversed (resp.~not reversed) in the transitive reduction of~$E$,
\item $E_a$ is the acyclic reorientation of~$D$ where an arc is reversed (resp.~not reversed) if and only if it is the only arc reversed (resp.~not reversed) in~$E$ along a directed path in~$D$ joining the endpoints of~$a$.
\end{compactitem}
\end{proposition}

%%%%%%%%%%

\subsection{Congruence normality and uniformity}
\label{subsec:congruenceNormality}

%We now switch to congruence normality and congruence uniformity.
A \defn{congruence} of a finite lattice~$(L, \le, \meet, \join)$ is an equivalence relation on~$L$ such that $x \equiv x'$ and $y \equiv y'$ implies $x \join y \equiv x' \join y'$ and $x \meet y \equiv x' \meet y'$.
The \defn{lattice quotient}~$L/{\equiv}$ is the lattice on the classes of~$\equiv$, where for any two classes~$X$ and~$Y$, the order is given by~$X \le Y$ if and only if $x \le y$ for some~${x \in X}$ and~${y \in Y}$, and the join~$X \join Y$ (resp.~meet~$X \meet Y$) is the class of~$x \join y$ (resp.~${x \meet y}$) for any~$x \in X$ and~$y \in Y$.
%In other words, the projection map sending an element of~$L$ to its congruence class is a lattice map.
The lattice quotient~$L/{\equiv}$ is isomorphic to the subposet of~$L$ induced by the minimal elements in their classes.

The set~$\con(L)$ of all congruences of~$L$, ordered by refinement, forms itself a distributive lattice where the meet is the intersection of relations and the join is the transitive closure of union of relations.
For any $x, y \in L$, there is a unique minimal congruence~$\con(x,y)$ in which~$x \equiv y$.
For a join irreducible element~$j$ of~$L$, the congruence~$\con(j_\star,j)$ is join irreducible in the congruence lattice~$\con(L)$.
% Similarly, for any meet irreducible element~$m$ of~$L$, the congruence~$\con(m, m^\star)$ is meet irreducible in~$\con(L)$.
The lattice~$L$ is called:
\begin{compactitem}
\item \defn{congruence normal} if $\con(j_\star, j) \ne \con(m, m^\star)$ for any join irreducible $j$ and meet irreducible $m$ such that~$j \le m$,
\item \defn{congruence uniform} if the map~$j \mapsto \con(j_\star,j)$ (resp.~$m \mapsto \con(m, m^\star)$) is a bijection between the join (resp.~meet) irreducible elements of~$L$ and that of~$\con(L)$.
\end{compactitem}
A lattice is congruence uniform if and only if it is congruence normal and semidistributive.
Using a standard characterization of congruence normal (resp.~uniform) lattices in terms of convex (resp.~interval) doublings~\cite{Day}, we obtain the following statements.
%
%In the sequel, we will use an alternative characterization of congruence normality and congruence uniformity in terms of convex and interval doublings in the sense of~\cite{Day}.
%Given a poset~$P$ and a subset~$X$ of~$P$, the \defn{doubling} of~$X$ in~$P$ is the poset~$P[X]$ on~$(P \ssm X) \sqcup (X \times \{0,1\})$ defined by:
%\begin{compactitem}
%\item $a \le b$ in~$P[X]$ if~$a, b \notin X$ and~$a \le b$ in~$P$,
%\item $(a,i) \le b$ in~$P[X]$ if~$a \in X$, $b \notin X$, $i \in \{0,1\}$, and $a \le b$ in~$P$,
%\item $a \le (b,j)$ in~$P[X]$ if~$a \notin X$, $b \in X$, $j \in \{0,1\}$, and $a \le b$ in~$P$,
%\item $(a,i) \le (b,j)$ in~$P[X]$ if~$a,b \in X$, $i,j \in \{0,1\}$, and $a \le b$ in~$P$ and~$i \le j$.
%\end{compactitem}
%This construction is illustrated in \cref{fig:doublingLattices}.
%It was observed that if~$L$ is a lattice and $C \subseteq L$ is order convex (\ie $x \le y \le z$ and~$x,z \in C$ implies~$y \in C$), then~$L[C]$ is again a lattice.
%A lattice is congruence normal (resp.~uniform) if and only if it can be obtained from a distributive lattice by a sequence of doublings of order convex sets (resp.~of intervals).

%\begin{figure}
%	\centerline{\includegraphics[scale=.9]{doublingLattices}}
%	\caption{A sequence of order convex doublings in a lattice. The two blue segments in the first lattice are doubled into four blue segments connected by four green segments in the second lattice, and the four red segments in the second lattice are doubled into height red segments connected by six orange segments in the third lattice. The first step could be decomposed into two interval doublings, the second cannot.}
%	\label{fig:doublingLattices}
%\end{figure}

\begin{proposition}
\label{prop:congruenceNormal}
The poset~$\AR$ is a congruence normal lattice for any vertebrate acyclic~$D$.
\end{proposition}

\begin{proposition}
\label{prop:congruenceUniform}
The poset~$\AR$ is a congruence uniform lattice if and only if~$D$ is skeletal.
\end{proposition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Ropes}
\label{sec:ropes}

Assume that~$D$ is skeletal, so that~$\AR$ is a congruence uniform lattice.
We introduce ropes, non-crossing rope diagrams, and the subrope order, generalizing~\cite{Reading-arcDiagrams}. % on arcs and non-crossing arc diagrams.
% In our setting, we prefer the word ``rope'' rather than ``arc'' to avoid the possible confusions with the arcs of the directed graphs.
They provide models for the irreducibles, canonical representations, and congruences of~$\AR$.

\begin{figure}[h]
	\centerline{
			\includegraphics[scale=1.4]{canonicalJoinComplex4} \qquad
			\includegraphics[scale=1.4]{canonicalJoinComplexRopes4}
	}
%	\centerline{\includegraphics[scale=1.7]{joinIrreducibles4}}
%	\centerline{\includegraphics[scale=1.7]{ropes4}}
	\caption{Correspondence between join irreducibles of~$\AR$ and ropes of~$D$.} % To represent a rope~$(u, v, \down, \up)$, we highlight in red the arc~$(u,v)$ and we mark with down and up triangles the vertices of~$\down$ and~$\up$.}
	\label{fig:bijectionCanonicalJoinComplexes}
\end{figure}

%%%%%%%%%%

\subsection{Ropes and irreducibles}
\label{subsec:ropes}

A \defn{rope} of~$D$ is a quadruple~$(u, v, \down, \up)$ where~$(u,v)$ is an arc of~$D$ and~$\down \sqcup \up$ is a partition of the vertices that appear in the interior of a path from~$u$ to~$v$ in~$D$ (or equivalently since~$D$ is filled, the vertices~$w$ so that both~$(u,w)$ and~$(w,v)$ belong to~$D$).

For an acyclic reorientation $E$ of~$D$ and an arc~$(u,v) \in D$, set $\rope_{u,v}^E \eqdef (u, v, \down_{u,v}^E, \up_{u,v}^E)$ where $\down_{u,v}^E$ and $\up_{u,v}^E$ are defined by $\down_{u,v}^E \eqdef \! \set{w \in V}{(u,w) \in D \! \ssm \! E \text{ and } (w,v) \in D \cap E}$ and $\up_{u,v}^E \eqdef \! \set{w \in V}{(u,w) \in D \cap E \text{ and } (w,v) \in D \! \ssm \! E}$.
%\begin{align*}
%\down_{u,v}^E & \eqdef \set{w \in V}{(u,w) \in D \ssm E \text{ and } (w,v) \in D \cap E} \\
%\text{and} \qquad
%\up_{u,v}^E & \eqdef \set{w \in V}{(u,w) \in D \cap E \text{ and } (w,v) \in D \ssm E},
%\end{align*}
%We note that~$\rope_{u,v}^E$ is a rope of~$D$ as soon as~$(u,v)$ or~$(v,u)$ appears in the transitive reduction of~$E$.
This map enables us to connect the ropes of~$D$ with the join and meet irreducibles of~$\AR$:
\begin{compactitem}
\item for a join (resp.~meet) irreducible~$I$ of~$\AR$, let~$\rope_\join(I)$ (resp.~$\rope_\meet(I)$) be the rope~$\rope_{u,v}^I$ where~$(u,v)$ is the only arc reversed (resp.~not reversed) in the transitive restriction~of~$I$,
\item for a rope~$\rope \eqdef (u, v, \down, \up)$ on~$D$, let~$I_\join(\rope)$ (resp.~$I_\meet(\rope)$) be the reorientation of~$D$ where an arc~$(w,w')$ of~$D$ is reversed (resp.~not reversed) if and only if~$w \in \up \cup \{u\}$ and~$w' \in \down \cup \{v\}$ (resp.~$w \in \down \cup \{u\}$ and~$w' \in \up \cup \{v\}$).
\end{compactitem}
%For an illustration of these maps, compare \cref{fig:canonicalJoinComplexes}\,(bottom) with \cref{fig:canonicalJoinComplexesRopes}.
These maps are illustrated in \cref{fig:bijectionCanonicalJoinComplexes}. To represent a rope~$(u, v, \down, \up)$, we highlight in red the arc~$(u,v)$ and we mark with down and up triangles the vertices of~$\down$ and~$\up$.

\begin{proposition}
\label{prop:bijectionsRopes}
If~$D$ is skeletal, the two maps~$\rope_\join$ and~$I_\join$ (resp.~$\rope_\meet$ and~$I_\meet$) are inverse bijections between the join (resp.~meet) irreducibles of~$\AR$ and the ropes of~$D$.
\end{proposition}

%%%%%%%%%%

\subsection{Non-crossing rope diagrams and canonical representations}
\label{subsec:ropeDiagrams}

%For a rope~$\rope \eqdef (u, v, \down, \up)$ consider the order~$\prec_\rope$ on~$\{u,v\} \cup \up \cup \down$ where any element of~$\down$ is smaller than both~$u$ and~$v$ which are both smaller than any element of~$\up$.
%%by $w_\down \prec_\rope w \prec_\rope w_\up$ for any~$w_\down \in \down$ and~$w \in \{u,v\}$ and~$w_\up \in \up$.
%We say that two ropes~$\rope$ and~$\rope'$ are \defn{crossing} if there are~$w, w' \in V$ such that~$w \prec_\rope w'$ while~$w' \prec_{\rope'} w$.
%We say that two ropes~$(u, v, \down, \up)$ and~$(u', v', \down', \up')$ are \defn{crossing} if 
%\begin{itemize}
%\item either both~$(\up \cup \{u\}) \cap (\down' \cup \{u'\})$ and $(\down \cup \{v\}) \cap (\up' \cup \{v'\})$ are non-empty, 
%\item or both~$(\down \cup \{u\}) \cap (\up' \cup \{u'\})$ and $(\up \cup \{v\}) \cap (\down' \cup \{v'\})$ are non-empty.
%\end{itemize}

Two ropes~$(u, v, \down, \up)$ and $(u', v', \down', \up')$ are \defn{crossing} if there are distinct vertices~$w \ne w'$ such that~$w \in (\down \cup \{u,v\}) \cap (\up' \cup \{u',v'\})$ and ${w' \in (\up \cup \{u,v\}) \cap (\down' \cup \{u',v'\})}$.
A \defn{non-crossing rope diagram} is a collection of pairwise non-crossing ropes of~$D$.
%The \defn{non-crossing rope complex} of~$D$ is the simplicial complex of non-crossing rope diagrams of~$D$.

We now connect the non-crossing rope diagrams of~$D$ with the elements of~$\AR$:
\begin{compactitem}
\item for an acyclic reorientation~$E$ of~$D$, let~$\diagram_\join(E)$ (resp.~$\diagram_\meet(E)$) be the set of ropes~$\rope_{u,v}^E$ for all arcs~$(u,v)$ reversed (resp.~not reversed) in the transitive reduction of~$E$,
\item for a non-crossing rope diagram~$\diagram$ of~$D$, define the reorientation $E_\join(\diagram) \eqdef \bigJoin_{\rope \in \diagram} I_\join(\rope)$ (resp.~$E_\meet(\diagram) \eqdef \bigMeet_{\rope \in \diagram} I_\meet(\rope)$) of~$D$.
\end{compactitem}

\begin{proposition}
\label{prop:bijectionsNonCrossingRopeDiagrams}
If~$D$ is skeletal, the two maps~$\diagram_\join$ and~$E_\join$ (resp.~$\diagram_\meet$ and~$E_\meet$) are inverse bijections between acyclic reorientations of~$D$ and non-crossing rope diagrams of~$D$.
\end{proposition}

%As a consequence of \cref{prop:canonicalJoinMeetRepresentation,prop:bijectionsNonCrossingRopeDiagrams}, we obtain the canonical join and meet representations in~$\AR$ in terms of ropes of~$D$. %, and the canonical join (resp.~meet) complex in terms of non-crossing rope diagrams of~$D$.
%For an illustration of the following two statements, compare \cref{fig:canonicalJoinComplexes}\,(bottom) with \cref{fig:canonicalJoinComplexesRopes}.

%\begin{figure}
%	\centerline{
%			\includegraphics[scale=.9]{canonicalJoinComplexRopes2} \qquad
%%			\includegraphics[scale=.9]{canonicalJoinComplexRopes3} \qquad
%			\includegraphics[scale=.9]{canonicalJoinComplexRopes4} \qquad
%			\includegraphics[scale=.9]{canonicalJoinComplexRopes7}
%	}
%	\caption{The canonical join complexes of \cref{fig:canonicalJoinComplexes} as non-crossing rope complexes. To represent a rope~$(u, v, \down, \up)$, we highlight the arc~$(u,v)$ in red, and we mark the vertices of~$\down$ and~$\up$ by down and up triangles respectively. The rightmost complex is the non-crossing arc complex of~\cite{Reading-arcDiagrams}.}
%	\label{fig:canonicalJoinComplexesRopes}
%\end{figure}

\cref{prop:bijectionsNonCrossingRopeDiagrams} enables us to rewrite \cref{prop:canonicalJoinMeetRepresentation} in terms of ropes, hence to connect the canonical join complex of~$\AR$ (\ie the simplicial complex of canonical join representations of~$\AR$ \cite{Reading-arcDiagrams}) to the noncrossing rope complex of~$D$ (\ie the simplicial complex of non-crossing rope diagrams of~$D$).
These complexes are illustrated in \cref{fig:bijectionCanonicalJoinComplexes}.

\begin{corollary}
\label{prop:canonicalJoinMeetComplex}
Assume that~$D$ is skeletal.
The canonical join (resp.~meet) representation of any acyclic reorientation~$E$ of~$D$ is $E = \bigJoin_{\rope \in \diagram_\join(E)} I_\join(\rope)$ (resp.~$E = \bigMeet_{\rope \in \diagram_\meet(E)} I_\meet(\rope)$).
Hence, the canonical join (resp.~meet) complex of~$\AR$ is isomorphic to the non-crossing rope complex of~$D$.
\end{corollary}

%%%%%%%%%%

\subsection{Subrope order and congruences}
\label{subsec:subropes}

Recall from \cref{subsec:congruenceNormality} that the set~$\con(L)$ of congruences of a lattice~$L$, ordered by refinement, is a distributive lattice.
When~$L$ is congruence uniform, $\con(L)$ is isomorphic to the set of lower ideals of the \defn{forcing order} on join irreducibles of~$L$, defined by~$j \prec j'$ if $\con(j'_\star, j')$ refines $\con(j_\star, j)$.
Moreover, for a congruence~$\equiv$ of~$L$ corresponding to a lower ideal~$\bb{I}$ of the forcing order,
\begin{compactitem}
\item an element of~$L$ is minimal in its $\equiv$-class if and only if all the join irreducibles in its canonical join representation belong to~$\bb{I}$,
\item the canonical joinands of a congruence class~$X$ in~$L/{\equiv}$ are the classes of the canonical joinands of the minimal element in~$X$.
\end{compactitem}
Dual statements hold using meets instead of joins.
In view of these statements, understanding the congruences and quotients of a congruence uniform lattice amounts to understanding the forcing order on the join irreducibles of~$L$ and its lower ideals.

For acyclic reorientation lattices, the forcing order is not difficult to describe in terms of ropes.
A rope~$\rope \eqdef (u,v, \down, \up)$ is a \defn{subrope} of a rope~$\rope' \eqdef (u', v', \down', \up')$ if and only if~${\{u,v\} \subseteq \{u',v'\} \cup \down' \cup \up'}$ and~$\down \subseteq \down'$ while~$\up \subseteq \up'$.
The \defn{subrope order} is the order on ropes of~$D$ defined by~$\rope \prec \rope'$ if $\rope$ is a subrope of~$\rope'$.
%Examples of subrope orders are illustrated in \cref{fig:subropeOrder}.
%
%\begin{figure}
%	\centerline{
%			\includegraphics[scale=.9]{subropeOrder2} \qquad
%%			\includegraphics[scale=.9]{subropeOrder3} \qquad
%			\includegraphics[scale=.9]{subropeOrder4} \qquad
%			\raisebox{-.5cm}{\includegraphics[scale=.9]{subropeOrder7}}
%	}
%	\caption{The subrope orders on the directed acyclic graphs of \cref{fig:canonicalJoinComplexes}. To represent a rope~$(u, v, \down, \up)$, we highlight the arc~$(u,v)$ in red, and we mark the vertices of~$\down$ and~$\up$ by down and up triangles respectively. The rightmost order is the subarc order of~\cite{Reading-arcDiagrams}.}
%	\label{fig:subropeOrder}
%\end{figure}

\begin{proposition}
\label{prop:subropeOrder}
Assume that~$D$ is skeletal.
For any two join irreducibles~$J$ and~$J'$ of the acyclic reorientation lattice~$\AR$, $J$ forces $J'$ if and only if $\rope_\join(J)$ is a subrope of~$\rope_\join(J')$.
\end{proposition}

\begin{corollary}
\label{coro:ropeIdeals}
If~$D$ is skeletal, the congruence lattice of~$\AR$ is isomorphic to the lattice of lower ideals of the subrope order for~$D$.
\end{corollary}

Throughout the end of this paper, we denote by~$\bb{I}_\equiv$ the lower ideal of the subrope order corresponding to a congruence~$\equiv$ of~$\AR$.%,  and conversely by~$\equiv_\bb{I}$ the congruence of~$\AR$ corresponding to a lower ideal~$\bb{I}$ of the subrope order.
%In other words, $\bb{I}_\equiv$ is the set of ropes~$\rope_\join(J)$ for the join irreducibles~$J$ of~$\AR$ uncontracted by~$\equiv$, and~$\equiv_\bb{I}$ contracts the join irreducibles~$I_\join(\rope)$ for~$\rope$ not in~$\bb{I}$.

\begin{corollary}
\label{coro:minimalElementsIdeal}
Assume that~$D$ is skeletal.
For any congruence~$\equiv$ of~$\AR$,
\begin{compactitem}
\item an acyclic reorientation~$E$ of~$D$ is minimal in its $\equiv$-class if and only if~$\diagram_\join(E) \subseteq~\bb{I}_\equiv$,
\item $\AR/{\equiv}$ is isomorphic to the subposet of~$\AR$ induced by $\set{E \in \AR}{\diagram_\join(E) \subseteq~\bb{I}_\equiv}$.
\end{compactitem}
A symmetric statement holds for maximal elements and~$\diagram_\meet$.
\end{corollary}

\begin{example}
\label{exm:coherentCongruences}
Fix a pair~$(\decorationDown, \decorationUp)$ of subsets of vertices of~$D$.
The \defn{coherent congruence}~$\equiv_{(\decorationDown, \decorationUp)}$ is the congruence of~$\AR$ whose rope ideal is the set~$\bb{I}_{(\decorationDown, \decorationUp)}$ of ropes~$(u,v, \down, \up)$ of~$D$ with~$\down \subseteq \decorationDown$ and~$\up \subseteq \decorationUp$.
In particular, we call 
\begin{compactitem}
\item \defn{sylvester congruence} of~$\AR$ the congruence~$\equiv_{(V,\varnothing)}$, and \defn{Tamari lattice} of~$D$ the quotient~$\AR/{\equiv_{(V,\varnothing)}}$, generalizing~\cite{Tamari}. See \cref{fig:subropeOrder}.
\item \defn{Cambrian congruences} of~$\AR$ the coherent congruences~$\equiv_{(\decorationDown, \decorationUp)}$ such that~$\decorationDown \sqcup \decorationUp = V$, and \defn{Cambrian lattices} of~$D$ the corresponding quotients of~$\AR$, generalizing~\cite{Reading-CambrianLattices}.
\end{compactitem}
The coherent congruences of~$\AR$ are the analogues of the permutree congruences of the weak order~\cite{PilaudPons-permutrees}.
They share many interesting properties developed in~\cite[Sect.~5.4]{Pilaud-acyclicReorientationLattices}.
We conjecture that:
\begin{compactitem}
\item the graph of the Tamari lattice is regular if and only if $D$ has no induced\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph1}}}\,or\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph2}}}\,or\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph3}}},
\item the Cambrian lattices of~$D$ are equinumerous if and only if $D$ has no induced\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph1}}}.
\end{compactitem}
%
\begin{figure}
	\centerline{
			\raisebox{1.5cm}{\includegraphics[scale=1.4]{subropeOrder4}} \,
			\includegraphics[scale=.84]{sylvesterCongruence4} \,
			\includegraphics[scale=.84]{TamariTrees4}
	}
	\caption{The subrope order, the sylvester congruence, and the Tamari lattice on~$D$.}
	\label{fig:subropeOrder}
\end{figure}
%
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Quotient fans and quotientopes}
\label{sec:quotientFansQuotientopes}

We now switch to the geometric side of this paper.
As originally observed in~\cite{Greene}, the acyclic reorientation poset~$\AR$ can be interpreted geometrically on the graphical fan of~$D$ or on the graphical zonotope of~$D$.
%(The poset of regions of an arbitrary hyperplane arrangement will be discussed later in \cref{sec:posetRegions}.)
When~$D$ is skeletal, we consider the quotient fans of the congruences of~$\AR$ and show that they are normal fans of quotientopes.

%%%%%%%%%%

\subsection{Graphical fan, shards, and quotient fans}
\label{subsec:graphicalFanShardsQuotientFans}

\para{Graphical fan}
%
We work in the vector space~$\R^V$ indexed by the vertex set~$V$ of~$D$.
We denote the standard basis by~$(\b{e}_v)_{v \in V}$, and let~$\one_U \eqdef \sum_{u \in U} \b{e}_u$ for~${U \subseteq V}$.
The \defn{graphical arrangement}~$\c{H}_D$ of~$D$ is the arrangement of the hyperplanes $\bb{H}_{uv} \eqdef \set{\b{x} \in \R^V}{x_u = x_v}$ for all arcs~$(u,v) \in D$.
It defines the \defn{graphical fan}~$\Fan$ of~$D$, whose chambers are the closures of the connected components of~$\smash{\R^V \ssm \bigcup_{(u,v) \in D} \bb{H}_{uv}}$.
See \cref{fig:geometricRealizations}.
%Note that~$\Fan$ is complete but not essential since all its cones contain the linear subspace~$\K$ generated by the characteristic vectors of the connected components of~$D$.
%The intersection~$\Fan \cap \K^\perp$ of~$\Fan$ with the orthogonal complement~$\K^\perp$ of~$\K$ is an essential fan with the same combinatorics as~$\Fan$.
%
The cones of~$\Fan$ are in bijection with \defn{ordered partitions} of~$D$, \ie pairs~$(\mu, \omega)$~where
\begin{compactitem}
\item $\mu$ is a partition of~$V$ where each part induces a connected subgraph of~$D$,
\item $\omega$ is an acyclic reorientation on the quotient graph~$D/\mu$.
\end{compactitem}
In particular, the chambers of~$\Fan$ correspond to the acyclic reorientations of~$D$, and the rays of~$\Fan$ correspond to the \defn{biconnected subsets} of~$D$ (\ie a non-empty connected subset of~$V$ whose complement in its connected component of~$D$ is also non-empty and connected).
The Hasse diagram of~$\AR$ is isomorphic to the dual graph of the graphical fan~$\Fan$, oriented by~${\b{\omega}_D \eqdef \sum_{(u,v) \in A} \b{e}_v - \b{e}_u}$.

For instance, when~$D$ is a tournament on~$[n]$, the graphical fan~$\Fan$ is the braid fan, defined by the hyperplanes~$\bb{H}_{ij}$ for~$1 \le i < j \le n$.
Its cones correspond to ordered partitions of~$[n]$, its regions to permutations of~$[n]$, its rays to proper subsets of~$[n]$, and its dual graph is isomorphic to the Hasse diagram of the weak order on~$\f{S}_n$.

%As observed in~\cite{Greene}, the Hasse diagram of the acyclic reorientation poset~$\AR$ can be interpreted geometrically~as 
%\begin{compactitem}
%\item the dual graph of the \defn{graphical fan}~$\Fan$, defined by the \defn{graphical arrangement} of~$D$ containing the hyperplanes~$\bigset{\b{x} \in \R^V}{x_u = x_v}$ for all arcs~$(u,v) \in D$, oriented in the linear direction~$\b{\omega}_D \eqdef \sum_{(u,v) \in A} \b{e}_v - \b{e}_u$, or
%\item the graph of the \defn{graphical zonotope}~$\Zono$, defined as the Minkowski sum of all segments~$[\b{e}_u, \b{e}_v]$ for all arcs~$(u,v)$ of~$D$, oriented in the linear direction~$\b{\omega}_D$.
%\end{compactitem}
%Note that the graphical fan and the graphical zonotope are dual to each other, and that their codimension is the number of connected components of~$D$.
%For instance, when~$D$ is the increasing tournament on~$[n]$, the graphical fan~$\Fan$ is the braid fan and the graphical zonotope is the classical permutahedron.
%Another example is illustrated in \cref{fig:geometricRealizations}.

\para{Shards and quotient fan}
%
Assume that~$D$ is skeletal, so that~$\AR$ is a congruence uniform lattice.
Generalizing~\cite{Reading-latticeCongruences,Reading-HopfAlgebras}, define the \defn{shard} of a rope~$\rope \eqdef (u,v, \down, \up)$~of~$D$~as
\[
\shard_\rope \eqdef \bigset{\b{x} \in \R^V}{x_{w} \le x_u = x_v \le x_{w'} \text{ for any } w \in \down \text{ and } w' \in \up}.
\]
%Some examples of shards are represented on the bottom of \cref{fig:graphicalArrangements}.
%
For a congruence~$\equiv$ of~$\AR$, the \defn{quotient fan}~$\Fan[\equiv]$ is then defined equivalently as follows:
\begin{compactitem}
\item the chambers of~$\Fan[\equiv]$ are obtained by glueing the chambers of the graphical arrangement of~$D$ corresponding to acyclic reorientations in the same class of~$\equiv$,
\item the union of the walls of~$\Fan[\equiv]$ is the union of the shards~$\shard_\rope$ for~$\rope$ in the rope ideal~$\bb{I}_\equiv$.
\end{compactitem}
The Hasse diagram of the quotient~$\AR/{\equiv}$ is isomorphic to the dual graph of the quotient fan~$\Fan[\equiv]$, oriented in the direction~$\b{\omega}_D \eqdef \sum_{(u,v) \in A} \b{e}_v - \b{e}_u$.

We call \defn{sylvester fan} of~$D$ the quotient fan for the sylvester congruence.
See \cref{fig:geometricRealizations}.
%
\begin{figure}[b]
	\centerline{
			\includegraphics[scale=.47]{graphicalArrangementAcyclicReorientations4} \!\!\!
			\raisebox{-.27cm}{\input{zonotope4}} \!\!\!\!\!\!
			\includegraphics[scale=.47]{quotientFan4} \!\!\!
			\raisebox{-.27cm}{\input{associahedron4}}
	}
	\caption{The graphical arrangement, the graphical zonotope, the sylvester fan, and the associahedron of a skeletal directed acyclic graph~$D$.}
	\label{fig:geometricRealizations}
\end{figure}

%%%%%%%%%%

\subsection{Graphical zonotope, shard polytopes, and quotientopes}
\label{subsec:graphicalZonotopeAssociahedraShardPolytopesQuotientopes}

\para{Graphical zonotope}
%
%Consider the \defn{graphical zonotope}~$\Zono$, defined as the Minkowski sum of the segments~$[\b{0}, \b{e}_u-\b{e}_v]$ for all~${(u,v) \in A}$.
%Note that~$\Zono$ is not full-dimensional as it lies in the orthogonal complement~$\K^\perp$ of the linear subspace~$\K$ generated by the characteristic vectors of the connected components of~$D$.
The \defn{graphical zonotope}~$\Zono$ is the Minkowski sum of the segments $[\b{e}_u,\b{e}_v]$ for all~${(u,v) \in A}$.
%Note that~$\Zono$ is not full-dimensional as it is orthogonal to the linear subspace~$\K$ generated by the characteristic vectors of the connected components of~$D$.
%More precisely, the translate~$\Zono - \sum_{(u,v) \in A} \b{e}_u$ lies in the linear space~$\K^\perp$.
The graphical fan~$\Fan$ is the normal fan of the graphical zonotope~$\Zono$.
%Therefore, the faces (resp.~vertices, resp.~facets) of~$\Zono$ are in bijection with ordered partitions (resp.~acyclic reorientations, biconnected subsets) of~$D$.
%More precisely,
Hence, the faces of~$\Zono$ are in bijection with ordered partitions of~$D$.
In particular, the vertices of~$\Zono$ correspond to the acyclic reorientations of~$D$, and the facets of~$\Zono$ correspond to the biconnected subsets of~$D$.
%In particular,
%\begin{itemize}
%%\item each acyclic reorientation~$E$ of~$D$ corresponds to a vertex~$\sum_{(u,v) \in E \ssm D} \b{e}_u - \b{e}_v$ of~$\Zono$,
%%\item each biconnected subset~$U$ of~$D$ corresponds to a facet with inequality~$\dotprod{\one_U}{\b{x}} \le \iota_U$, where~$\iota_U \eqdef |\set{a \in A}{|a \cap U| = 1}|$ counts the arcs of~$D$ with exactly one endpoint in~$U$.
%\item each acyclic reorientation~$E$ of~$D$ corresponds to a vertex~$\sum_{(u,v) \in E} \b{e}_v$ of~$\Zono$,
%\item each biconnected subset~$U$ of~$D$ corresponds to a facet with inequality~$\dotprod{\one_U}{\b{x}} \ge \iota_U$, where~$\iota_U \eqdef |\set{a \in A}{|a \cap U| = 2}|$ counts the arcs of~$D$ with both endpoints in~$U$.
%\end{itemize}
The Hasse diagram of~$\AR$ isomorphic to the graph of~$\Zono$, oriented in the direction~${\b{\omega}_D \eqdef \sum_{(u,v) \in A} \b{e}_v - \b{e}_u}$.

For instance, when~$D$ is a tournament on~$[n]$, the graphical zonotope~$\Zono$ coincides up to a translation of vector~$\one$ with the classical \defn{permutahedron}, defined equivalently as:
\begin{compactitem}
\item the convex hull of the points~$\sum_{i \in [n]} \sigma_i \, \b{e}_i$ for all permutations~$\sigma$ of~$[n]$,
\item the intersection of the hyperplane~$\bigset{\b{x} \in \R^n}{\dotprod{\one}{\b{x}} = \binom{n+1}{2}}$ with the halfspaces ${\bigset{\b{x} \in \R^n}{\dotprod{\one_U}{\b{x}} \ge \binom{|U|+1}{2}}}$ for all proper subsets~$\varnothing \ne U \subsetneq [n]$,
\item the Minkowski sum of the vector~$\one$ and the segments~$[\b{e}_i, \b{e}_j]$ for all~$1 \le i < j \le n$.
\end{compactitem}

\para{Quotientopes and associahedra}
%
Assume that~$D$ is skeletal, so that~$\AR$ is a congruence uniform lattice.
The main result of this section is the following statement.

\begin{theorem}
\label{thm:existenceQuotientopes}
Assume that $D$ is skeletal.
For any congruence~$\equiv$ of~$\AR$, the quotient fan~$\Fan[\equiv]$ is the normal fan of a polytope.
\end{theorem}

We call \defn{quotientope} any polytopal realization of the quotient fan~$\Fan[\equiv]$.
We provide two general approaches to construct quotientopes in \cref{thm:MinkowskiSumAssociahedra,thm:MinkowskiSumShardPolytopes}, and we discuss a third approach specific to the sylvester, Cambrian, and coherent congruences in \cref{prop:associahedraRemovahedra}.

We call \defn{associahedron} for~$D$ any quotientope for the sylvester congruence~$\equiv_{(V,\varnothing)}$.
See \cref{fig:geometricRealizations}.
Following \cref{exm:coherentCongruences}, we conjecture that:
\begin{compactitem}
\item the associahedron for~$D$ is simple if and only if $D$ has no induced\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph1}}}\,or\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph2}}}\,or\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph3}}},
\item the quotientopes of all Cambrian congruences have isomorphic face lattices if and only if $D$ has no induced\,\smash{\raisebox{-.25cm}{\includegraphics[scale=.9]{digraph1}}}.
\end{compactitem}
%To avoid any confusion, let us insist that the associahedron of the directed acyclic graph~$D$ is not the associahedron of the underlying undirected graph~$G$ as defined by M.~Carr and S.~Devadoss in~\cite{CarrDevadoss}, except if~$D$ is a disjoint union of tournaments.
%In fact, as suggested in \cref{pb:TamariRegular} and illustrated in \cref{fig:associahedra}\,(middle), the associahedron of~$D$ is not even always a simple polytope.

\para{Quotientopes from classical associahedra}
%
Our first approach to realize the quotient fan~$\Fan[\equiv]$ as a polytope is based on the associahedra~\cite{ShniderSternberg, Loday, HohlwegLange}.
Recall first that when~$D$ is the increasing tournament on~$[n]$, the sylvester fan is the normal fan of the classical associahedron, defined equivalently~as:
\begin{compactitem}
\item the convex hull of the points~$\sum_{j \in [n]} \ell(T,j) \, r(T,j) \, \b{e}_j$ for all binary trees~$T$ on~$n$ nodes, where $\ell(T,j)$ and~$r(T,j)$ respectively denote the numbers of leaves in the left and right subtrees of the node~$j$ of~$T$ (labeled in inorder), see~\cite{Loday},
\item the intersection of the hyperplane~$\bigset{\b{x} \in \R^n}{\dotprod{\one}{\b{x}} = \binom{n+1}{2}}$ with the halfspaces ${\bigset{\b{x} \in \R^n}{\bigdotprod{\one_{[a,b]}}{\b{x}} \ge \binom{b-a+2}{2}}}$ for all intervals~$1 \le a \le b \le n$, see~\cite{ShniderSternberg},
\item the Minkowski sum of~$\simplex_{[a,b]}$ for all intervals ${1 \le a \le b \le n}$, where for~${I \subseteq [n]}$, $\simplex_I \eqdef \! \conv\set{\b{e}_i}{i \in I}$ is the face of the standard simplex~$\simplex_{[n]}$ labeled by~$I$, see~\cite{Postnikov}.
\end{compactitem}
Similar polytopal realizations were constructed for the quotient fans of the Cambrian congruences of the weak order in~\cite{HohlwegLange}. % and of the permutree congruences in~\cite{PilaudPons-permutrees} of the weak order, using analogous vertex and facet descriptions.
%The resulting associahedra and permutreehedra can also be written as Minkowski sums and differences of faces of the standard simplex, though the description is not as simple, see \eg \cite{Lange}.
Here, we skip the precise vertex, facet, and Minkowski descriptions of these associahedra and refer to \cite{HohlwegLange} for details.
We just need to observe that, for the principal congruence whose rope ideal is the lower ideal generated by a rope~$\rope$ of~$D$, the quotient fan~$\Fan[\rope]$ is the normal fan of an associahedron~$\Asso[\rope]$ obtained by embedding a Cambrian associahedron of~\cite{HohlwegLange} in~$\R^V$.
Mimicking~\cite[Theorem~1]{PadrolPilaudRitter}, we now observe that any quotient fan can be realized as a Minkowski sum of (low dimensional) Cambrian associahedra of~\cite{HohlwegLange}.

\begin{theorem}
\label{thm:MinkowskiSumAssociahedra}
Assume that~$D$ is skeletal.
Consider any congruence~$\equiv$ of~$\AR$, and let~$\rope_1, \dots, \rope_p$ denote the ropes generating the lower ideal~$\bb{I}_\equiv$ of the subrope order.
Then the quotient fan~$\Fan[\equiv]$~is
\begin{compactitem}
\item the common refinement of the Cambrian fans~$\Fan[\rope_1], \dots, \Fan[\rope_p]$,
\item the normal fan of the Minkowski sum of the Cambrian associahedra~$\Asso[\rope_1], \dots, \Asso[\rope_p]$.
\end{compactitem}
\end{theorem}

\para{Quotientopes from shard polytopes}
%
%As already mentioned, the Cambrian associahedra can still be decomposed further into Minkowski sums and differences of faces of the standard simplex.
%Following~\cite{PadrolPilaudRitter}, we next consider elementary Minkowski summands to realize all quotient fans.
Our second approach to realize the quotient fan~$\Fan[\equiv]$ as a polytope is based on the shard polytopes introduced in~\cite{PadrolPilaudRitter}.
Consider a rope~$\rope \eqdef (u, v, \down, \up)$ and let~$\pi$ denote the directed path from~$u$ to~$v$ in the transitive reduction of~$D$.
Define a \defn{$\rope$-alternating matching} as a pair~$(M_\down, M_\up)$ with~$M_\down \subseteq \{u\} \cup \down$ and ${M_\up \subseteq \up \cup \{v\}}$ such that~$M_\down$ and~$M_\up$ are alternating along~$\pi$.
The \defn{shard polytope}~$\shardPolytope$ is the polytope of~$\R^V$ defined as the convex hull of the vectors~$\one_{M_\down} - \one_{M_\up}$ for all $\rope$-alternating matchings~$(M_\down, M_\up)$.
For instance, the shard polytope~$\shardPolytope$ of a rope of the form~$\rope \eqdef (u, v, \down, \varnothing)$ is the face~$\simplex_{\{u,v\} \cup \down}$ of the standard simplex, translated by the vector~$-\b{e}_v$.
% We refer to~\cite{PadrolPilaudRitter} for an alternative definition of the shard polytope~$\shardPolytope$ as the matroid polytope of a series-parallel graph associated to~$\rope$.
The following statement is the fundamental property of shard polytopes.

\begin{proposition}
\label{prop:shardPolytopes}
Assume that~$D$ is skeletal.
For any rope~$\rope$ of~$D$, the union of the walls of the normal fan of the shard polytope~$\shardPolytope$ contains the shard~$\shard_\rope$ and is contained in the union of the shards~$\shard_{\rope'}$ for all subropes~$\rope'$ of~$\rope$.
\end{proposition}

Based on \cref{prop:shardPolytopes}, we obtain polytopal realizations of all lattice quotients of~$\AR$ as Minkowski sums of shard polytopes.

\begin{theorem}
\label{thm:MinkowskiSumShardPolytopes}
Assume that~$D$ is skeletal.
For any congruence~$\equiv$ of~$\AR$ and any positive coefficients~${\b{s} \in (\R_{>0})^{\bb{I}_\equiv}}$, the quotient fan~$\Fan[\equiv]$ is the normal fan of the Minkowski sum~$\sum_{\rope \in \bb{I}_\equiv} \b{s}_\rope \, \shardPolytope$.
\end{theorem}

\para{Associahedra as removahedra}
%
Finally, we focus on quotientopes for coherent congruences and more specifically on associahedra.
The following statement, visible in \cref{fig:geometricRealizations}, generalizes~\cite{ShniderSternberg, Postnikov}.

\begin{proposition}
\label{prop:associahedraRemovahedra}
Assume that~$D$ is skeletal.
The sylvester fan~$\Fan[(V,\varnothing)]$ is the normal fan of the associahedron~$\Asso[D]$ defined equivalently as
\begin{compactitem}
\item the polytope obtained from the graphical zonotope~$\Zono$ by deleting all facet inequalities corresponding to biconnected subsets~$U$ of~$D$ not connected in the transitive reduction~of~$D$,
\item the Minkowski sum of the faces~$\simplex_\pi$ of the standard simplex~$\simplex_V$, for all directed paths~$\pi$ in the transitive reduction of~$D$ whose endpoints are connected by an arc of~$D$.
\end{compactitem}
\end{proposition}

In contrast, we are still missing a  simple vertex description of the associahedron~$\Asso[D]$ similar to that of~\cite{Loday} for the classical associahedron.

Note that the construction of \cref{prop:associahedraRemovahedra} cannot provide a quotientope for any congruence of~$\AR$.
However, based on computer experiments, we conjecture that:
\begin{compactitem}
\item For any coherent congruence~$\equiv_{(\decorationDown, \decorationUp)}$, the quotient fan~$\Fan[(\decorationDown, \decorationUp)]$ is the normal fan of the polytope obtained by deleting from the facet description of the graphical zonotope~$\Zono$ the inequalities normal to the rays of the graphical fan~$\Fan$ that are not rays of the quotient fan~$\Fan[(\decorationDown, \decorationUp)]$. This would extend the permutreehedra of~\cite{PilaudPons-permutrees}.
\item For a Cambrian congruence (\ie with~$\decorationDown \sqcup \decorationUp = V$), the resulting polytope coincides with the Minkowski sum of the shard polytopes of the ropes of~$\bb{I}_{(\decorationDown, \decorationUp)}$. This would extend the case of Cambrian congruences of the weak order treated in~\cite{PadrolPilaudRitter}.
\end{compactitem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
