%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{3}
\addbibresource{3.bib}

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

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{corollary}[theorem]{Corollary}

\usepackage{shuffle}
\usepackage{paralist}
\usepackage{xargs}
\usepackage{overpic}
\usepackage{ulem}\normalem

\graphicspath{{figures/}}

%%%%% AUTHOR'S COMMANDS %%%%%

% special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\fS}{\mathfrak{S}} % symmetric group
\renewcommand{\b}[1]{\mathbf{#1}} % bold letters
\renewcommand{\c}[1]{\mathcal{#1}} % calligraphic letters
\newcommand{\f}[1]{\mathfrak{#1}} % frak letters

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;|\; #2 \big\}} % big set notation
\newcommand{\biggset}[2]{\bigg\{ #1 \;\bigg|\; #2 \bigg\}} % bigg set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\langle \, #1 \; | \; #2 \, \rangle} % dot product
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
\newcommand{\one}{{1\!\!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:}} }} % =:

% LATTICE QUOTIENTS
% lattices
\newcommand{\meet}{\wedge} % meet in lattice
\newcommand{\join}{\vee} % join in lattice
\newcommand{\bigMeet}{\bigwedge} % meet
\newcommand{\bigJoin}{\bigvee} % join
\newcommand{\JI}{\mathsf{JI}} % join-irreducible
\newcommand{\MI}{\mathsf{MI}} % meet-irreducible
\newcommand{\Cong}{\mathsf{Cong}} % congruence lattice
\newcommand{\con}{\mathrm{con}} % congruence contracting a cover relation
\newcommand{\ji}{\mathsf{ji}} % join irreducible
\newcommand{\mi}{\mathsf{mi}} % meet irreducible
\newcommand{\projDown}{\pi^{\equiv}_{\!\downarrow\!}} % down projection lattice congruence
\newcommand{\projUp}{\pi_{\equiv}^{\!\uparrow\!}} % up projection lattice congruence
% arc diagrams
\DeclareMathOperator{\inv}{inv} % inversions
\newcommand{\arcs}{\Psi} % arc ideal

% QUOTIENTOPES
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\vect}{vect} % linear span
\DeclareMathOperator{\cone}{cone} % cone hull
\newcommandx{\Perm}[1][1=n]{\mathsf{Perm}(#1)} % permutahedron
\newcommandx{\Asso}[2][1=n]{\mathsf{Asso}(#1)} % associahedron
\newcommandx{\Zono}[2][1=n]{\mathsf{Zono}(#1)} % zonotope
\newcommandx{\Fan}[1][1=F]{\mathcal{#1}} % fan
\newcommandx{\ray}[1][1=r]{\mathbf{#1}} % ray
\newcommandx{\rays}[1][1=R]{\mathbf{#1}} % rays
\newcommand{\shard}{\Sigma}
\newcommand{\hs}{\mathbf{H}^{\le}} % half space
\newcommand{\HS}[1]{\mathbf{H}^{\le}(#1)} % half space
\newcommand{\hyp}{\mathbf{H}} % hyperplane
\newcommand{\Hyp}[1]{\mathbf{H}_{#1}} % hyperplane
\newcommand{\HA}{\mathcal{H}} % hyperplane arrangement

% HOPF ALGEBRAS
% classical Hopf algebras
\newcommand{\FQSym}{\mathsf{FQSym}} % quasi-symmetric functions
\newcommand{\PBT}{\mathsf{PBT}} % PBT (Loday-Ronco)
\newcommand{\MR}{\mathsf{MR}} % Malvenuto-Reutenauer
\newcommand{\LR}{\mathsf{LR}} % Loday-Ronco
% operations
\newcommand{\product}{\cdot} % product
\newcommand{\coproduct}{\triangle} % coproduct
\newcommand{\shiftedShuffle}{\,\bar\shuffle\,} % shifted shuffle
\newcommand{\convolution}{\star} % convolution
\newcommand{\underprod}[2]{{#1}\backslash{#2}} % #1 under #2
\newcommand{\overprod}[2]{{#1}\slash{#2}} % #1 over #2
% decorated algebras
\newcommand{\eP}{\mathfrak{P}} % decorated permutations
\newcommand{\eD}{\mathfrak{D}} % decorated diagrams
\newcommand{\juxta}[2]{#1#2} % concatenation
\newcommand{\concatf}{\mathsf{conc}} % concatenation
\newcommand{\selectf}{\mathsf{sel}} % selection
\newcommand{\stdf}{\mathsf{std}} % standardization
\newcommand{\concat}[2]{\concatf(#1,#2)} % concatenation
\newcommand{\select}[2]{\selectf(#1,#2)} % selection
\newcommand{\std}[2]{\stdf(#1,#2)} % standardization
\newcommand{\stdpos}[2]{\mathsf{stdp}(#1,#2)} % standardization positions
\newcommand{\stdval}[2]{\mathsf{stdv}(#1,#2)} % standardization values
\newcommand{\Id}{\mathrm{Id}} % identity
% bases
\newcommand{\F}{\mathbb{F}} % F-basis of FQSym
\newcommand{\G}{\mathbb{G}} % G-basis of FQSym
\newcommand{\HFQSym}{\mathbb{H}} % H-basis of FQSym
\newcommand{\EFQSym}{\mathbb{E}} % E-basis of FQSym
\newcommand{\PPT}{\mathbb{P}} % P-basis of PT
\newcommand{\QPT}{\mathbb{Q}} % Q-basis of PT*
\newcommand{\HPT}{\mathbb{H}} % H-basis of PT
\newcommand{\EPT}{\mathbb{E}} % E-basis of PT

% others
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\viceversa}{\textit{vice versa}} % exempli gratia
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\red}{\color{red}} % red command
\newcommand{\blue}{\color{blue}} % blue command
%<\newcommand{\defn}[1]{\uline{\textit{#1}}} % emphasis of a definition
\newcommand{\defn}[1]{\emph{\darkblue #1}} % emphasis of a definition


%%%%% END AUTHOR'S COMMANDS %%%%%

%% define your title in the usual way
\title{Polytopal realizations and Hopf algebra structures for lattice quotients of the weak order}%noncrossing arc diagrams}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. \newline\indent\;\; Partially supported by the French ANR grants SC3A~(15\,CE40\,0004\,01) and CAPPS~(17\,CE40\,0018). \newline\indent\;\;\;I warmly thank F. Santos for our collaboration~\cite{PilaudSantos-quotientopes} whose results are presented in \cref{subsec:quotientopes}.}}

%% then use \addressmark to match authors to institutions here
\address{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{
Noncrossing arc diagrams provide a powerful combinatorial model for the equivalence classes of the lattice congruences of the weak order on permutations.
In this extended abstract, we use these models to construct geometric and algebraic structures on weak order quotients.
On the geometric side, we construct, for any given congruence, a polytope whose normal fan is the quotient fan obtained by gluing together the cones of the braid fan that belong to the same congruence class.
%prove that for any weak order congruence, the quotient fan (obtained by gluing together the cones of the braid fan that belong to the same congruence class) is the normal fan of a convex polytope.
On the algebraic side, we define Hopf algebra structures which extend classical structures, including the Malvenuto--Reutenauer algebra, the Loday--Ronco algebra, and the Cambrian algebra.
}

%% put your French abstract here, or comment this out if you don't have one
\resumetitle{R\'{e}sum\'{e}}
\resume{
Les diagrammes d'arcs sans croisements fournissent un mod\`{e}le combinatoire efficace pour les classes d'\'{e}quivalence des congruences de treillis de l'ordre faible sur les permutations.
Dans ce r\'{e}sum\'{e} \'{e}tendu, nous utilisons ces mod\`{e}les pour construire des structures alg\'{e}briques et g\'{e}om\'{e}triques sur les quotients de l'ordre faible.
C\^{o}t\'{e} g\'{e}om\'{e}trique, nous construisons pour toute congruence un polytope dont l'\'{e}ventail normal est l'\'{e}ventail quotient obtenu en collant ensemble les c\^{o}nes de l'\'{e}ventail de tresses qui appartiennent \`{a} une m\^{e}me classe de congruence.
C\^{o}t\'{e} alg\'{e}brique, nous d\'{e}finissons des structures d'alg\`{e}bres de Hopf qui g\'{e}n\'{e}ralisent les structures classiques, notamment les alg\`{e}bres de Malvenuto--Reutenauer, de \mbox{Loday--Ronco}, et Cambrienne.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Weak order, lattice quotient, arc diagrams, quotientopes, Hopf algebras}

%% 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, firstinits=true]{biblatex}
%\DeclareFieldFormat[article,inbook,incollection,inproceedings,patent,thesis,unpublished]{title}{\textit{#1}\isdot}
%\renewbibmacro{in:}{}
%\addbibresource{arcDiagramsv2.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}

The weak order is a fundamental lattice structure on the set~$\fS_n$ of permutations of~$[n]$, defined by inclusion of inversion sets: $\sigma \le \tau$ if and only if $\inv(\sigma) \subseteq \inv(\tau)$ where $\inv(\sigma) \eqdef \set{(\sigma(i), \sigma(j))}{i < j \text{ and } \sigma(i) > \sigma(j)}$.
We focus on two of its many properties:
\begin{compactitem}
\item Its Hasse diagram can be seen geometrically as the graph of the permutahedron $\Perm \eqdef \conv \set{\big( \sigma^{-1}(1), \dots, \sigma^{-1}(n) \big)}{\sigma \in \fS_n}$, oriented in a linear direction.
\item Its intervals encode the product in C.~Malvenuto and C.~Reutenauer's Hopf algebra on permutations~\cite{MalvenutoReutenauer}.
\end{compactitem}

The objective of this extended abstract is to present similar polytopal realizations and Hopf algebra structures for lattice quotients of the weak order on~$\fS_n$.
The fundamental example is the Tamari lattice.
It can be defined as the transitive closure of right rotations on binary trees.
It can also be interpreted as the quotient of the weak order by the Sylvester congruence~\cite{HivertNovelliThibon-algebraBinarySearchTrees} on~$\fS_n$ defined as the transitive closure of the rewriting rule~$UacVbW \equiv^\textrm{sylv} UcaVbW$ where~${a < b < c}$ are letters while~$U,V,W$ are words of~$[n]$.
Other relevant lattice quotients of the weak order include the (type~$A$) Cambrian lattices~\cite{Reading-CambrianLattices, ChatelPilaud}, the boolean lattice, the permutree lattices~\cite{PilaudPons-permutrees}, the increasing flip lattice on acyclic twists~\cite{Pilaud-brickAlgebra}, the rotation lattice on diagonal rectangulations~\cite{LawReading}, etc.
N.~Reading provided in~\cite{Reading-arcDiagrams} a powerful combinatorial description of the lattice congruences of the weak order and of their congruence classes in terms of collections of certain arcs and noncrossing arc diagrams that we recall in \cref{sec:arcDiagrams}.

On the geometric side, N.~Reading observed that ``\emph{lattice congruences on the weak order know a lot of combinatorics and geometry}'' \cite[Sect.\,10.7]{Reading-surveyChapters}. He proved that each lattice congruence~$\equiv$ of the weak order is realized by the quotient fan~$\Fan_\equiv$, whose maximal cones are obtained by gluing together the cones of the braid fan corresponding to permutations that belong to the same congruence class of~$\equiv$. However, as observed in~\cite{Reading-HopfAlgebras}, ``\emph{this theorem gives no means of knowing when~$\Fan_\equiv$ is the normal fan of a polytope}''. For the above-mentioned examples of lattice congruences, this problem was settled by specific constructions of polytopes realizing the quotient fan~$\Fan_\equiv$: J.-L.~Loday's associahedron~\cite{Loday} for the Tamari lattice, C.~Hohlweg and C.~Lange's associahedra~\cite{HohlwegLange} for the Cambrian lattices, cubes for the boolean lattices, permutreehedra~\cite{PilaudPons-permutrees} for the permutree lattices, brick polytopes~\cite{PilaudSantos-brickPolytope} for increasing flip lattices on acyclic twists, Minkowski sums of opposite associahedra for rotation lattices on diagonal rectangulations~\cite{LawReading}, etc. 
Reporting on a joint work with F.~Santos~\cite{PilaudSantos-quotientopes}, we describe in \cref{sec:quotientopes} a general method to construct a polytope~$P_\equiv$ whose normal fan is the quotient fan~$\Fan_\equiv$ for any lattice congruence~$\equiv$ of the weak order on~$\fS_n$.

On the algebraic side, the search for Hopf algebra structures on congruence classes of lattice quotients of the weak order was also pioneered by N.~Reading.
In~\cite{Reading-HopfAlgebras}, he studied Hopf subalgebras of~$\MR$ generated by sums of permutations over the classes of a fixed lattice congruence~$\equiv_n$ on each~$\fS_n$ for~${n \ge 0}$.
This approach produces relevant Hopf algebras such as C. Malvenuto and C.~Reutenauer's algebra~$\MR$ on permutations~\cite{MalvenutoReutenauer}, \mbox{J.-L.~Loday} and M.~Ronco's algebra~$\LR$ on binary trees~\cite{LodayRonco}, V.~Pilaud's algebra on \mbox{$k$-twists}~\cite{Pilaud-brickAlgebra}, and N.~Reading and S.~Law's algebra on diagonal rectangulations~\cite{LawReading}.
A more recent approach, initiated by G.~Chatel and V.~Pilaud for the Cambrian algebra~\cite{ChatelPilaud} and extended by V.~Pilaud and V.~Pons for the permutree algebra~\cite{PilaudPons-permutrees}, consists of constructing subalgebras of decorated versions of the algebra~$\MR$ studied by J.-C.~Novelli and \mbox{J.-Y.~Thibon} in~\cite{NovelliThibon-coloredHopfAlgebras}.
Reporting on~\cite{Pilaud-arcDiagramAlgebra}, we discuss in \cref{sec:HopfAlgebras} how this new approach can be extended to obtain Hopf algebra structures on all lattice congruences of the weak~order.

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

\section{Lattice quotients of the weak order and arcs diagrams}
\label{sec:arcDiagrams}

%%%%%%%

\subsection{Canonical representations and noncrossing arc diagrams}

Consider a finite lattice~$(L,\le,\meet,\join)$.
A \defn{join representation} of~$x \in L$ is a subset~$J \subseteq L$ such that~${x = \bigJoin J}$.
It is \defn{irredundant} if~$x \ne \bigJoin J'$ for~$J' \subsetneq J$.
Irredundant join representations of~$x \in L$ are ordered by~$J \le J'$ if and only if for any~$y \in J$ there exists~$y' \in J'$ with~${y \le y'}$.
The minimal element of this order, if it exists, is the \defn{canonical join representation} of~$x$.
The lattice is \defn{semidistributive} if any element admits canonical join and meet representations.
The weak order on~$\fS_n$ is a semidistributive lattice, whose canonical join and meet representations were explicitly described by N.~Reading in~\cite{Reading-arcDiagrams}.
A \defn{descent} (resp.~\defn{ascent}) in~${\sigma = \sigma_1 \dots \sigma_n \in \fS_n}$ is a position~$i \in [n-1]$ such that~$\sigma_i > \sigma_{i+1}$~(resp.~${\sigma_i < \sigma_{i+1}}$).
For a descent~$i$ of~$\sigma$, consider the permutation~$\underline{\lambda}(\sigma, i)$ with entries~$1, \dots, (\sigma_{i+1} - 1)$ followed by~$\set{\sigma_j}{j < i, \, \sigma_j \in {]\sigma_{i+1}, \sigma_i[}}$ increasingly, then~$\sigma_i \sigma_{i+1}$, then~$\set{\sigma_j}{j > i+1, \, \sigma_j \in {]\sigma_{i+1}, \sigma_i[}}$ increasingly, and finally~$(\sigma_i + 1), \dots, n$.
Define dually ~$\overline{\lambda}(\sigma, i) \eqdef \omega_\circ \underline{\lambda}(\omega_\circ\sigma,i)$ for each ascent~$i$ of~$\sigma$, where~$\omega_\circ \eqdef [n, n-1, \dots, 2, 1]$ is the longest permutation of~$\fS_n$.

\begin{theorem}[{\cite[Thm.\,2.4]{Reading-arcDiagrams}}]
\label{thm:joinMeetRepresentationsPermutations}
The canonical join and meet representations of a permutation ${\sigma = \sigma_1 \dots \sigma_n}$ are given by~$\bigJoin \set{\underline{\lambda}(\sigma, i)}{\sigma_i > \sigma_{i+1}}$ and~$\bigMeet \set{\overline{\lambda}(\sigma, i)}{\sigma_i < \sigma_{i+1}}$.
\end{theorem}

As observed in~\cite{Reading-arcDiagrams}, the permutation~$\underline{\lambda}(\sigma, i)$ is determined by the values~$\sigma_i$ and~$\sigma_{i+1}$ and by the set~$\set{\sigma_j}{j < i, \, \sigma_j \in {]\sigma_{i+1}, \sigma_i[}}$.
This data can be recorded in the following combinatorial gadgets.
%
An \defn{arc} is a quadruple~$(a, b, n, S)$ where~${1 \le a < b \le n}$ are integers and~${S \subseteq {]a,b[}}$.
Let~$\c{A}_n \eqdef \set{(a, b, n, S)}{1 \le a < b \le n \text{ and } S \subseteq {]a,b[}}$, and~$\c{A} \eqdef \bigsqcup_{n \in \N} \c{A}_n$.
Let~$\underline{\alpha}(i, i+1, \sigma) \eqdef (\sigma_{i+1}, \sigma_i, n, \set{\sigma_j}{j < i \text{ and } \sigma_j \in {]\sigma_{i+1}, \sigma_i[} \,})$ denote the arc associated to a descent~$i$ of a permutation~$\sigma$ and~$\underline{\delta}(\sigma) \eqdef \set{\underline{\alpha}(i, i+1, \sigma)}{\sigma_i > \sigma_{i+1}}$ be the set of arcs corresponding to all descents of~$\sigma$. Define~$\overline{\alpha}$ and~$\overline{\delta}$ dually for ascents.

An arc~$(a, b, n, S)$ is visually represented as an $x$-monotone continuous curve wiggling around the horizontal axis, with endpoints~$a$ and~$b$, and passing above the points of~$S$ and below the points of~${]a,b[} \ssm S$.
With this representation, N.~Reading provided a convenient visual interpretation of~$\underline{\delta}$ and~$\overline{\delta}$.
For this, represent the permutation~$\sigma$ by its \defn{permutation table}~$(\sigma_i, i)$.
Draw arcs between any two consecutive dots~$(\sigma_i, i)$ and~$(\sigma_{i+1}, i+1)$, colored green if~$\sigma_i < \sigma_{i+1}$ is an ascent and red if~$\sigma_i > \sigma_{i+1}$ is a descent.
Then move all dots down to the horizontal axis, allowing the segments to curve, but not to cross each other nor to pass through any dot.
The set of red (resp.~green) arcs is then the set~$\underline{\delta}(\sigma)$ (resp.~$\overline{\delta}(\sigma)$) corresponding to the canonical join (resp.~meet) representation~of~$\sigma$.
See \cref{fig:arcDiagramsForcingOrder}\,(left). 

Two arcs \defn{cross} if the interior of the two curves representing these arcs intersect.
A \defn{noncrossing arc diagram} is a set~$\c{D}$ of arcs of~$\c{A}_n$ such that any two arcs of~$\c{D}$ do not cross and have distinct left (resp.~right) endpoints.
\cref{thm:joinMeetRepresentationsPermutations} yields the following.

\begin{theorem}[{\cite[Thm.\,3.1]{Reading-arcDiagrams}}]
The maps~$\underline{\delta}$ and~$\overline{\delta}$ are bijections from permutations of~$\fS_n$ to noncrossing arc diagrams of~$\c{A}_n$.
\end{theorem}

%%%%%%%

\subsection{Lattice quotients of the weak order and arc ideals}
\label{subsec:arcIdeals}

A \defn{lattice congruence} of~$L$ is an equivalence relation on~$L$ such that $x \equiv x'$ and~$y \equiv y'$ implies ${x \meet y \, \equiv \, x' \meet y'}$ and~${x \join y \, \equiv \, x' \join y'}$.
A lattice congruence~$\equiv$ defines a \defn{lattice quotient}~$L/{\equiv}$ obtained by contracting the equivalence classes of~$\equiv$.
We say that an element~$x$ is \defn{contracted} by~$\equiv$ if it is not minimal in its equivalence class of~$\equiv$.
As each class of~$\equiv$ is an interval of~$L$, it contains a unique uncontracted element, and the quotient~$L/{\equiv}$ is isomorphic to the subposet of~$L$ induced by its uncontracted elements.
Moreover, the canonical join representations in the quotient~$L/{\equiv}$ are precisely the canonical join representations of~$L$ that do not involve any contracted join-irreducible.
This yields the~following.

\begin{theorem}[{\cite[Thm.\,4.1]{Reading-arcDiagrams}}]
\label{thm:arcDiagrams}
Consider a lattice congruence~$\equiv$ of the weak order on~$\fS_n$, and let~$\c{I}_\equiv$ denote the arcs corresponding to the join-irreducible permutations not contracted by~$\equiv$.
\begin{compactenum}
\item A permutation~$\sigma$ is minimal in its $\equiv$-congruence class if and only if~${\underline{\delta}(\sigma) \subseteq \c{I}_\equiv}$.
\item Sending a $\equiv$-congruence class with minimal permutation~$\sigma$ to the arc diagram~$\underline{\delta}(\sigma)$ defines a bijection between the congruence classes of~$\equiv$ and the noncrossing arc diagrams~in~$\c{I}_\equiv$.
\item The congruence~$\equiv$ is the transitive closure of the rewriting rule~$\sigma \to \sigma \cdot (i \; i+1)$ where~$i$ is a descent of~$\sigma$ such that~${\underline{\alpha}(i, i+1, \sigma)} \notin \c{I}_\equiv$.
\end{compactenum}
\end{theorem}

It remains to characterize the sets of arcs~$\c{I}_\equiv$ corresponding to the uncontracted join-irreducible permutations of a lattice congruence~$\equiv$ of the weak order.
This is again transparent on the arc representation.
An arc~$\alpha \eqdef (a, d, n, S)$ is \defn{forced} by an arc~$\beta \eqdef (b, c, n, T)$, denoted~$\alpha \prec \beta$, if~${a \le b < c \le d}$ and~${T = S \cap {]b,c[}}$. 
Graphically, it means that~$\beta$ is obtained by restricting the arc~$\alpha$ to the interval~$[b,c]$.
See \cref{fig:arcDiagramsForcingOrder}\,(right).
An \defn{arc ideal} is any upper ideal~$\c{I}$ of the forcing order: $(a, d, n, S) \in \c{I}$ implies~${(b, c, n, S \cap {]b,c[}) \in \c{I}}$ for all~${a \le b < c \le d}$ and~$S \subseteq {]a,d[}$.
We denote by~$\f{I}_n$ the set of arc ideals of~$\c{A}_n$.

\begin{figure}
\centering
\resizebox{0.8\textwidth}{!}{
		\begin{overpic}[scale=.68]{nonCrossingArcDiagrams}
		    \put(-25,6){$\underline{\delta}(\sigma) =$}
		    \put(-15,40){$\sigma =$}
		    \put(-25,76){$\overline{\delta}(\sigma) =$}
		    \put(105,6){$= \underline{\delta}(\tau)$}
		    \put(105,40){$= \tau$}
		    \put(105,76){$= \overline{\delta}(\tau)$}
		\end{overpic}
		%\includegraphics[scale=.72]{nonCrossingArcDiagrams}
		\qquad\qquad\quad\includegraphics[scale=.68]{forcingOrder}
		}
	\caption{The noncrossing arc diagrams associated to the permutations~$\sigma = 2513746$, and $\tau = 2513476$ (left), and the forcing order on arcs of~$\c{A}_4$ (right).}
	\label{fig:arcDiagramsForcingOrder}
\end{figure}

\begin{theorem}[{\cite[Coro.\,4.5]{Reading-arcDiagrams}}]
\label{thm:arcIdeals}
A set of arcs~$\c{I} \subseteq \c{A}_n$ is the set~$\c{I}_\equiv$ for some lattice congruence~$\equiv$ of the weak order on~$\fS_n$ if and only if it is an arc ideal of~$\f{I}_n$.
\end{theorem}

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

\section{Geometric realizations}
\label{sec:quotientopes}

%%%%%%%

\subsection{Quotient fan}

Consider the \defn{braid arrangement}~$\HA_n \eqdef \set{\Hyp{ab}}{1 \le a < b \le n}$ formed by the hyperpla\-nes $\Hyp{ab} \eqdef \set{\b{x} \in \R^n}{x_a = x_b}$.
The closures of the connected components of~${\R^n \ssm \bigcup \HA_n}$ form a fan, which is complete and simplicial, but not essential.
The \defn{braid fan}~$\Fan_n$ is its intersection with the hyperplane~${\hyp \eqdef \bigset{\b{x} \in \R^n}{\sum_{i \in [n]} x_i = 0}}$.
See \cref{fig:shards4}\,(left).
The cones of the braid fan~$\Fan_n$ are labeled by ordered partitions of~$[n]$: an ordered partition $\pi = \pi_1 | \pi_2 | \dots | \pi_k$ of~$[n]$ into $k$ parts corresponds to the $(k-1)$-dimensional cone
\(
C(\pi) \eqdef \bigset{\b{x} \in \hyp}{x_u \le x_v \text{ for all $i \le j$, $u \in \pi_i$ and~$v \in \pi_j$}}.
\)
In particular, $\Fan_n$ has a maximal cone~$C(\sigma)$ for each permutation~${\sigma \in \fS_n}$, and a ray~$C(R)$ for each subset~$\varnothing \ne R \subsetneq [n]$.

The arcs of \cref{sec:arcDiagrams} have geometric counterparts called shards, due to N.~Reading~\cite{Reading-posetRegions} (see also his survey chapters~\cite{Reading-surveyChapters}).
For an arc~$\alpha \eqdef (a,b,n,S) \in \c{A}_n$, the \defn{shard}~$\shard(\alpha)$ is the cone~$\shard(\alpha) \eqdef \set{\b{x} \in \R^n}{x_a = x_b, \; x_a \ge x_k \text{ for all } k \in S, \; x_a \le x_k \text{ for all } k \in {]a,b[} \ssm S}$.
The hyperplane~$\Hyp{ab}$ is decomposed into the~$2^{b-a-1}$~shards~$\shard(a,b,n,S)$ for all~${S \subseteq {]a,b[}}$. The shards are thus pieces of the hyperplanes of the braid arrangement. See \cref{fig:shards4}\,(middle).

Reading proved in~\cite{Reading-HopfAlgebras} that any lattice congruence of the weak order defines a fan coarsening the braid fan in the following two equivalent ways.
See \cref{fig:shards4}\,(right).

\begin{theorem}[\cite{Reading-HopfAlgebras}]
\label{thm:fanQuotient}
For any lattice congruence~$\equiv$ of the weak order on~$\fS_n$, the cones obtained by
\begin{compactitem}
\item gluing together the cones of the braid fan that belong to the same congruence class of~$\equiv$,
\item keeping the connected components of~$\hyp \ssm \bigcup_{\alpha \in \c{I}_\equiv} \shard(\alpha)$,
\end{compactitem}
coincide and define a fan~$\Fan_\equiv$ whose dual graph is the Hasse diagram of the quotient~$\fS_n/{\equiv}$.
\end{theorem}

\begin{figure}[h]
	\centerline{\includegraphics[scale=.47]{braidArrangement4} \; \includegraphics[scale=.47]{shards4} \; \includegraphics[scale=.47]{LodayFan4}}
	\caption{A stereographic projection of the braid fan~$\Fan_4$ (left), the corresponding shards (middle), and the quotient fan given by the Sylvester congruence~$\equiv^\textrm{sylv}$~(right).}
	\label{fig:shards4}
\end{figure}

%%%%%%%

\subsection{Quotientopes}
\label{subsec:quotientopes}

Closing an open question of~\cite{Reading-HopfAlgebras}, we now use arcs to construct a polytopal realization of the quotient fan~$\Fan_\equiv$.
A function~$f : \c{A}_n \to \R_{>0}$ is \defn{forcing dominant} if
\(
f(\alpha) > \sum_{\beta \prec \alpha} f(\beta)
\)
for any arc~${\alpha \in \c{A}_n}$.
Note that such functions clearly exist since~$\prec$ is a poset, take for example~$f(a,b,n,S) = n^{-(b-a)^2}$. 
For an arc $\alpha = (a,b,n,S) \in \c{A}_n$ and a subset~$R \subseteq [n]$, we define the \defn{contribution}~$\gamma(\alpha, R)$ of~$\alpha$ to~$R$ to be~$1$ if~${|R \cap \{a,b\}| = 1}$ and~$S = R \cap {]a,b[}$, and $0$ otherwise.
For a subset~$R \subseteq [n]$, we pick a representative vector~$\ray(R) = \one_{k \in R} - \one_{k+1 \in R}$ of the ray~$C(R)$, and we define the \defn{height}~$h^f_\equiv(R) \in \R_{>0}$ to be
\(
h^f_\equiv(R) \; \eqdef \sum_{\alpha \in \c{I}_\equiv} f(\alpha) \, \gamma(\alpha, R).
\)
This height function has been chosen to fulfill the following property, proved in~\cite{PilaudSantos-quotientopes}.

\begin{lemma}
\label{lem:linearDependence}
Let~$\sigma, \sigma'$ be two adjacent permutations. Let~$\varnothing \ne R \subsetneq [n]$ (resp.~$\varnothing \ne R' \subsetneq [n]$) be such that~$\ray(R)$ (resp.~$\ray(R')$) is the ray of~$C(\sigma)$ not in~$C(\sigma')$ (resp.~of~$C(\sigma')$ not in~$C(\sigma)$). Then 
\begin{compactitem}
\item the (unique up to rescaling) linear dependence among the rays of the cones~$C(\sigma)$ and~$C(\sigma')$ is
\(
\ray(R) \, + \, \ray(R') \; = \; \ray(R \cap R') \, + \, \ray(R \cup R'),
\)
\item the height function satisfies
\(
h^f_\equiv(R) \, + \, h^f_\equiv(R') \; \ge \; h^f_\equiv(R \cap R') \, + \, h^f_\equiv(R \cup R')
\)
with equality if and only if the chambers~$C(\sigma)$ and~$C(\sigma')$ belongs to the same cone of~$\Fan_\equiv$.
\end{compactitem}
\end{lemma}

This property is a standard characterization of polytopality of fans, see~\cite[Prop.\,3]{PilaudSantos-quotientopes}.
The resulting realizations of~$\Fan_\equiv$, called \defn{quotientopes}, are illustrated in \cref{fig:quotientopeLattice}.

\begin{theorem}[{\cite[Thm.\,2 \& Coro.\,10]{PilaudSantos-quotientopes}}]
\label{thm:quotientopes}
For any lattice congruence~$\equiv$ of the weak order on~$\fS_n$, and any forcing dominant function~$f : \c{A}_n \to \R_{>0}$, the quotient fan~$\Fan_\equiv$ is the normal fan of the polytope
\(
P_\equiv^f \eqdef \bigset{\b{x} \in \R^n}{\dotprod{\ray(R)}{\b{x}} \le h^f_\equiv(R) \text{ for all } \varnothing \ne R \subsetneq [n]}.
\)
\end{theorem}

\begin{figure}
	\centerline{\includegraphics[scale=.31]{quotientopeLattice_square_colored}}
    \caption{The quotientope lattice for~$n = 4$: all quotientopes ordered by inclusion (which corresponds to refinement of the lattice congruences). We only consider lattice congruences whose arcs include all basic arcs~$(i,i+1,4,\varnothing)$, since otherwise their fan is not essential. We have highlighted in red the cube (bottom), J.-L.~Loday's associahedron~\cite{Loday}, C.~Hohlweg and C.~Lange's associahedron~\cite{HohlwegLange}, the diagonal rectangulation polytope~\cite{LawReading}, and the permutahedron (top).}
    \label{fig:quotientopeLattice}
\end{figure}

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

\section{Hopf algebra structures}
\label{sec:HopfAlgebras}

\subsection{Malvenuto--Reutenauer Hopf algebra on permutations}
\label{subsec:MalvenutoReutenauer}

A combinatorial Hopf algebra is a combinatorial vector space~$\c{A}$ endowed with an associative product~$\product : \c{A} \otimes \c{A} \to \c{A}$ and a coassociative coproduct~$\coproduct : \c{A} \to \c{A} \otimes \c{A}$, subject to the compatibility relation~$\coproduct(a \product b) = \coproduct(a) \product \coproduct(b)$, where the right hand side product has to be understood componentwise.
We now recall the fundamental example of~\cite{MalvenutoReutenauer}.

The \defn{standardization} of a word~$w \in \N^q$ with distinct entries is the permutation~$\stdf(w)$ of~$[q]$ whose entries are in the same relative order as the entries of~$w$.
For a permutation~$\rho \in \fS_p$ and a subset~$R = \{r_1 < \dots < r_q\} \subseteq [p]$, we define $\stdpos{\rho}{R}$ (resp.~$\stdval{\rho}{R}$) as the standardization of the word obtained by deleting from~$\rho$ the entries whose positions (resp.~values) are not in~$R$.
For two permutations~$\sigma \in \fS_m$ and~$\tau \in \fS_n$, define the \defn{shifted shuffle}~$\sigma \shiftedShuffle \tau$ and the \defn{convolution}~$\sigma \convolution \tau$~by
\begin{align*}
\sigma \shiftedShuffle \tau & \eqdef \set{\rho \in \fS_{m+n}}{\stdval{\rho}{[m]} = \sigma \text{ and } \stdval{\rho}{[m+n] \ssm [m]} = \tau} \\ 
\text{and}\qquad
\sigma \convolution \tau & \eqdef \set{\rho \in \fS_{m+n}}{\stdpos{\rho}{[m]} = \sigma \text{ and } \stdpos{\rho}{[m+n] \ssm [m]} = \tau}.
\end{align*}
E.g.,
\(
\begin{array}[t]{rl}
{\red 12} \shiftedShuffle {\blue 231} & = \{ {\red 12}{\blue 453}, {\red 1}{\blue 4}{\red 2}{\blue 53}, {\red 1}{\blue 45}{\red 2}{\blue 3}, {\red 1}{\blue 453}{\red 2}, {\blue 4}{\red 12}{\blue 53}, {\blue 4}{\red 1}{\blue 5}{\red 2}{\blue 3}, {\blue 4}{\red 1}{\blue 53}{\red 2}, {\blue 45}{\red 12}{\blue 3}, {\blue 45}{\red 1}{\blue 3}{\red 2}, {\blue 453}{\red 12} \}, \\
{\red 12} \convolution {\blue 231} & = \{ {\red 12}{\blue 453}, {\red 13}{\blue 452}, {\red 14}{\blue 352}, {\red 15}{\blue 342}, {\red 23}{\blue 451}, {\red 24}{\blue 351}, {\red 25}{\blue 341}, {\red 34}{\blue 251}, {\red 35}{\blue 241}, {\red 45}{\blue 231} \}.
\end{array}
\)

\medskip
\noindent
Let~$\fS \eqdef \bigsqcup_{n \in \N} \fS_n$ be the set of all permutations (any size) and $\b{k}\fS$ its $\b{k}$-vector span.

\begin{theorem}[Malvenuto--Reutenauer~\cite{MalvenutoReutenauer}]
\label{thm:MalvenutoReutenauer}
The vector space~$\b{k}\fS$ with basis~$(\F_\sigma)_{\sigma \in \fS}$ endowed with the product~$\F_\sigma \product \F_\tau = \sum\limits_{\rho \in \sigma \shiftedShuffle \tau} \F_\rho$ and the coproduct~$\coproduct \F_\rho = \sum\limits_{\rho \in \sigma \convolution \tau} \F_\sigma \otimes \F_\tau$ is a Hopf~algebra.
\end{theorem}

The product in~$\b{k}\fS$ behaves nicely with the weak order on~$\fS_n$.
For two permutations~$\sigma \in \fS_m$ and~$\tau \in \fS_n$, consider the permutations~$\sigma\backslash\tau$ and~$\tau\slash\sigma$ of~$\fS_{m+n}$ defined~by
\[
\textstyle\sigma\backslash\tau(i) = \begin{cases} \mu(i) & \text{ if } i \in [m] \\ m + \tau(i-m) & \text{ otherwise} \end{cases}
\qquad\text{and}\qquad
\tau\slash\sigma(i) = \begin{cases} m + \tau(i) & \text{ if } i \in [n] \\ \sigma(i-n) & \text{ otherwise.} \end{cases} 
\]
The shifted shuffle~$\sigma \shiftedShuffle \tau$ is then precisely given by the weak order interval between~$\sigma\backslash\tau$ and~$\sigma\slash\tau$ in the weak order on~$\fS_{m+n}$.
This extends to a product of weak order intervals.

\begin{proposition}
\label{prop:productIntervalWeakOrder}
A product of weak order intervals in~$\b{k}\fS$ is a weak order interval: for two weak order intervals~$[\mu, \nu] \subseteq \fS_m$ and~$[\lambda, \omega] \subseteq \fS_n$, we have
\(
\sum\limits_{\mu \le \sigma \le \nu} \F_\sigma \product \sum\limits_{\lambda \le \tau \le \omega} \F_\tau = \sum\limits_{\mu\backslash\lambda \le \rho \le \omega\slash\nu} \F_\rho.
\)
\end{proposition}

%%%%%%%

\vspace{-3ex}
\subsection{Decorated permutations}
\label{subsec:decoratedPermutations}

The Cambrian and permutree Hopf algebras~\cite{ChatelPilaud, PilaudPons-permutrees} were constructed as subalgebras of generalizations of the Malvenuto--Reutenauer algebra to signed or decorated permutations~\cite{NovelliThibon-coloredHopfAlgebras}.
Following this prototype, we will obtain Hopf algebras on noncrossing arc diagrams from algebras on permutations decorated with more complicated structures.

\begin{definition}
\label{def:decorationSet}
A \defn{decoration set} is a graded set~$\f{X} \eqdef \bigsqcup_{n \ge 0} \f{X}_n$ endowed with
\begin{compactitem}
\item a \defn{concatenation}~$\concatf : \f{X}_m \times \f{X}_n \longrightarrow \f{X}_{m+n}$ for all~$m, n \in \N$,
\item a \defn{selection}~$\selectf : \f{X}_m \times \binom{[m]}{k} \longrightarrow \f{X}_k$ for all~$m, k \in \N$,
\end{compactitem}
such that
\begin{compactenum}
\item $\concat{\c{X}}{\concat{\c{Y}}{\c{Z}}} = \concat{\concat{\c{X}}{\c{Y}}}{\c{Z}}$ for any~$\c{X}, \c{Y}, \c{Z} \in \f{X}$,
\item $\select{\select{\c{X}}{R}}{S} = \select{\c{X}}{\set{r_s}{s \in S}}$ for any~$\c{X} \in \f{X}_p$, $R \! = \! \{r_1, \dots, r_q\} \subseteq [p]$,~${S \subseteq [q]}$,
\item ${\concat{\select{\c{X}}{R}}{\select{\c{Y}}{S}} = \select{\concat{\c{X}}{\c{Y}}}{R \cup S^{\rightarrow m}}}$ for any~${\c{X} \in \f{X}_m}$,~${\c{Y} \in \f{X}_n}$, and any~${R \subseteq [m]}$,~$S \subseteq [n]$, where~$S^{\rightarrow m} \eqdef \set{s+m}{s \in S}$.
\end{compactenum}
\end{definition}

\begin{example}
\label{exm:decorationSet}
A typical decoration set is the set of words~$\c{A}^*$ on a finite alphabet~$\c{A}$, graded by length, with the concatenation of words $\concat{u_1 \dots u_m}{v_1 \dots v_n} = u_1 \dots u_mv_1 \dots v_n$ and the selection defined by subwords $\select{w_1 \dots w_p}{\{r_1, \dots, r_q\}} = w_{r_1} \dots w_{r_q}$.
\end{example}

For~$n \ge 0$, we denote by~$\eP_n$ the set of \defn{$\f{X}$-decorated permutations} of size~$n$, \ie of pairs~$(\sigma, \c{X})$ with~$\sigma \in \fS_n$ and~$\c{X} \in \f{X}_n$.
We consider the graded set~$\eP \eqdef \bigsqcup_{n \ge 0} \eP_n$ and the graded vector space~$\b{k}\eP \eqdef \bigoplus_{n\ge 0} \b{k}\eP_n$, where~$\b{k}\eP_n$ is a vector space with basis~$(\F_{(\sigma, \c{X})})_{(\sigma, \c{X}) \in \eP_n}$ indexed by \mbox{$\f{X}$-decorated} permutations of size~$n$.
For two decorated permutations~$(\sigma, \c{X})$ and~$(\tau, \c{Y})$, we define the \defn{product}~$\F_{(\sigma, \c{X})} \product \F_{(\tau, \c{Y})}$ by
\[
\F_{(\sigma, \c{X})} \product \F_{(\tau, \c{Y})} \eqdef \sum_{\rho \in \sigma \shiftedShuffle \tau} \F_{( \rho, \concat{\c{X}}{\c{Y}} )}.
\]

\begin{proposition}[{\cite[Prop.\,11]{Pilaud-arcDiagramAlgebra}}]
\label{prop:algebraDecoratedPermutations}
The product~$\product$ defines an associative algebra on~$\b{k}\eP$.
\end{proposition}

Let the \defn{standardization} of a decorated permutation~$(\rho, \c{Z}) \in \eP_p$ at a subset~$R \subseteq [p]$~be
\[
\std{(\rho, \c{Z})}{R} \eqdef \big( \stdpos{\rho}{R}, \select{\c{Z}}{\rho^{-1}(R)} \big),
\]
where~$\stdpos{\rho}{R}$ is the position standardization on~$\fS$ and~$\select{\c{Z}}{\rho^{-1}(R)}$ is the selection on~$\f{X}$.
For a decorated permutation~$(\rho, \c{Z}) \in \eP_p$, we define the \defn{coproduct}~$\coproduct\F_{(\rho, \c{Z})}$ by
\[
\coproduct\F_{(\rho, \c{Z})} \eqdef \sum\nolimits_{k = 0}^p \F_{\std{(\rho, \c{Z})}{[k]}} \otimes \F_{\std{(\rho, \c{Z})}{[p] \ssm [k]}}.
\]

\begin{proposition}[{\cite[Prop.\,12]{Pilaud-arcDiagramAlgebra}}]
\label{prop:coalgebraDecoratedPermutations}
The coproduct~$\coproduct$ defines a coassociative coalgebra on~$\b{k}\eP$.
\end{proposition}

\begin{theorem}[{\cite[Thm.\,13]{Pilaud-arcDiagramAlgebra}}]
\label{thm:HopfAlgebraDecoratedPermutations}
$(\b{k}\eP, \product, \coproduct)$ defines a combinatorial Hopf algebra.
\end{theorem}

\begin{example}
\label{exm:decoratedPermutations}
When~$\f{X}$ is the set of words~$\c{A}^*$ on a finite alphabet~$\c{A}$ as in \cref{exm:decorationSet}, the Hopf algebra of decorated permutations was studied in detail by J.-C.~Novelli and J.-Y.~Thibon in~\cite{NovelliThibon-coloredHopfAlgebras}. In particular, if~$\f{X} = \{\bullet\}^*$, then~$\b{k}\eP$ is just the Malvenuto--Reutenauer algebra.
\end{example}

%%%%%%%

\vspace{-3ex}
\subsection{Decorated noncrossing arc diagrams}
\label{subsec:decoratedArcDiagrams}

We now use our Hopf algebra on decorated permutations to construct Hopf algebras on decorated noncrossing arc diagrams.
As in the previous section, we consider a decoration set~$(\f{X}, \concatf, \selectf)$ and the corresponding Hopf algebra~$(\b{k}\eP, \,\product\,, \coproduct)$ on $\f{X}$-decorated permutations.
Recall from \cref{subsec:arcIdeals} that~$\f{I}_n$ denotes the set of arc ideals of~$\c{A}_n$.

For an arc~$\alpha = (a, b, m, S)$ and~$n \in \N$, define the \defn{augmented arc}~${\alpha^{+n} \eqdef (a, b, m+n, S)}$ and the \defn{shifted arc}~$\alpha^{\rightarrow n} \eqdef (a+n, b+n, m+n, \set{s+n}{s \in S})$.
Graphically, the arc $\alpha^{+n}$ (resp.~$\alpha^{\rightarrow n}$) is obtained from the arc~$\alpha$ by adding $n$ points to its right (resp.~to its left).
For~$\c{I} \subseteq \c{A}_m$ and~$n \in \N$, define~$\c{I}^{+n} \eqdef \set{\alpha^{+n}}{\alpha \in \c{I}}$ and~$\c{I}^{\rightarrow n} \eqdef \set{\alpha^{\rightarrow n}}{\alpha \in \c{I}}$.

\begin{definition}
\label{def:conservative}
A graded function~$\arcs : \f{X} = \bigsqcup_{n \ge 0} \f{X}_n \longrightarrow \f{I} = \bigsqcup_{n \ge 0} \f{I}_n$ is \defn{conservative} if
\begin{compactenum}
\item $\arcs(\c{X})^{+n}$ and~$\arcs(\c{Y})^{\rightarrow m}$ are both subsets of~$\arcs(\concat{\c{X}}{\c{Y}})$ for any~$\c{X} \in \f{X}_m$,~${\c{Y} \in \f{X}_n}$,
\item $(r_a, r_b, p, S) \in \arcs(\c{Z})$ implies $(a, b, q, \set{c \in [q]}{r_c \in S}) \in \arcs(\select{\c{Z}}{R})$ for any~$\c{Z} \in \f{X}_p$, any ${R = \{r_1 < \dots < r_q\} \subseteq [p]}$, any~$1 \le a < b \le q$ and any~$S \subseteq {]r_a, r_b[}$.
\end{compactenum}
\end{definition}

\begin{example}
\label{exm:conservative}
If~$\f{X} = \{\bullet\}^*$ is the decoration set of words on a one element alphabet, then the maps $\bullet^n \mapsto \c{A}_n$ and~$\bullet^n \mapsto \c{A}_n^\varnothing \eqdef \set{(a, b, n, \varnothing)}{1 \le a < b \le n}$ are both conservative.
\end{example}

From now on, we assume that we are given a conservative function~$\arcs : \f{X} \longrightarrow \f{I}$.
For~${n \ge 0}$, we denote by~$\eD_n$ the set of \defn{$\f{X}$-decorated noncrossing arc diagrams} of size~$n$, \ie of pairs~$(\c{D}, \c{X})$ where~${\c{X} \in \f{X}_n}$ and~$\c{D}$ is a noncrossing arc diagram contained in~$\arcs(\c{X})$.

We now define a Hopf algebra on $\f{X}$-decorated noncrossing arc diagrams.
By \cref{thm:arcIdeals}, any lattice congruence~$\equiv$ of the weak order on~$\fS_n$ corresponds to an arc ideal~$\c{I}_\equiv \in \f{I}_n$.
We consider the map~$\underline{\eta}_{\c{I}_\equiv} : \fS_n \to \c{I}_\equiv$ which associates to any permutation~$\tau \in \fS_n$ the noncrossing arc diagram of~$\c{I}_\equiv$ corresponding to the $\equiv$-congruence class of~$\tau$.
By \cref{thm:arcDiagrams}, $\underline{\eta}_{\c{I}_\equiv}(\tau) = \underline{\delta}(\sigma)$ where~$\sigma$ is the minimal permutation in the $\equiv$-congruence class of~$\tau$.
We denote by~$\b{k}\eD \eqdef \bigoplus_{n \ge 0} \b{k}\eD_n$ the graded vector subspace of~$\b{k}\eP$ generated by the elements
\vspace{-0.5ex}
\[
\PPT_{(\c{D}, \c{X})} \eqdef \sum_{\substack{\sigma \in \fS \\ \underline{\eta}{}_{\arcs(\c{X})}(\sigma) = \c{D}}} \F_{(\sigma, \c{X})},
\]

\vspace{-0.5ex}
\noindent for all $\f{X}$-decorated noncrossing arc diagrams~$(\c{D}, \c{X})$.
Our main result is the following.

\begin{theorem}[{\cite[Thm.\,17]{Pilaud-arcDiagramAlgebra}}]
\label{thm:HopfAlgebraDecoratedArcDiagrams}
The subspace~$\b{k}\eD$ is a Hopf subalgebra~of~$\b{k}\eP$.
\end{theorem}

\begin{example}
Let~$\f{X} = \{\bullet\}^*$, so that~$\b{k}\eP$ is the Malvenuto--Reutenauer algebra by \cref{exm:decoratedPermutations} and consider the two conservative functions of \cref{exm:conservative}.
If~$\arcs(\bullet^n) = \c{A}_n$, then~$\b{k}\eD = \b{k}\eP$ is also the Malvenuto--Reutenauer algebra. % (as the quotient is trivial).
If~$\arcs(\bullet^n) = \c{A}_n^\varnothing$, then~$\b{k}\eD$ is the Loday--Ronco algebra~\cite{LodayRonco} (as noncrossing arc diagrams in~$\c{A}_n^\varnothing$ are just noncrossing partitions, in bijection with binary trees).
\end{example}

%\vspace{-1ex}
We now state an analogue of \cref{prop:productIntervalWeakOrder} for decorated noncrossing arc diagrams.

%\vspace{-1ex}
\begin{proposition}[{\cite[Prop.\,18]{Pilaud-arcDiagramAlgebra}}]
\label{prop:descriptionProduct}
Consider two $\f{X}$-decorated noncrossing arc diagrams~$(\c{D}, \c{X})$ and~$(\c{E}, \c{Y})$, and their weak order intervals~$[\mu, \nu] \eqdef \underline{\eta}_{\arcs(\c{X})}^{-1}(\c{D})$ and~$[\lambda, \omega]  \eqdef \underline{\eta}_{\arcs(\c{Y})}^{-1}(\c{E})$.
Then
\[
\PPT_{(\c{D}, \c{X})} \product \PPT_{(\c{E}, \c{Y})} = \sum\nolimits_{\c{F}} \PPT_{(\c{F}, \concat{\c{X}}{\c{Y}} )},
\]
where~$\c{F}$ ranges in the interval from~$\c{D}\backslash\c{E} \eqdef \underline{\eta}_{\arcs(\concat{\c{X}}{\c{Y}})}(\mu\backslash\lambda)$ to~$\c{E}\slash\c{D} \eqdef \underline{\eta}_{\arcs(\concat{\c{X}}{\c{Y}})}(\omega\slash\nu)$ in the lattice of noncrossing arc diagrams in~$\arcs(\concat{\c{X}}{\c{Y}})$ (see 2 in \cref{thm:arcDiagrams}).
\end{proposition}

%%%%%%%

\vspace{-3ex}
\subsection{Two applications}

We conclude with two applications of \cref{subsec:decoratedPermutations,subsec:decoratedArcDiagrams} that produce relevant Hopf algebras on noncrossing arc diagrams.
An additional application appears in~\cite[Sect.\,4.2]{Pilaud-arcDiagramAlgebra}.

\vspace{-2ex}
\paragraph{Insertional, translational, and Hopf families of congruences.}

For all~$n \in \N$, fix a lattice congruence~$\equiv_n$ of the weak order on~$\f{S}_n$, with arc ideal~$\c{I}_n$.
As a first application of \cref{thm:HopfAlgebraDecoratedArcDiagrams}, we obtain sufficient conditions for the family~$(\equiv_n)_{n \in \N}$ to define a Hopf subalgebra~of~$\b{k}\f{S}$, which essentially coincide with the translational and insertional conditions given by N.~Reading in~\cite[Thm.~1.2 \& 1.3]{Reading-HopfAlgebras}.
Note that this situation covers various families of lattice congruences, producing Hopf algebra on permutations~\cite{MalvenutoReutenauer}, on binary trees~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees}, on diagonal quadragulations~\cite{LawReading}, on $k$-twists~\cite{Pilaud-brickAlgebra}, etc.


\begin{corollary}[{\cite[Thm.\,1.2 \& 1.3]{Reading-HopfAlgebras}}]
\label{coro:HopfFamilies}
For all~$n \in \N$, consider a lattice congruence~$\equiv_n$ of the weak order on~$\f{S}_n$, with arc ideal~$\c{I}_n$.
If
\begin{compactitem}
\item both~$\c{I}_m^{+n}$ and~$\c{I}_n^{\rightarrow m}$ are contained in~$\c{I}_{m+n}$ for all~$m, n \in \N$,
\item $(r_a, r_b, p, S) \in \c{I}_p$ implies~$(a, b, q, \set{c \in [q]}{r_c \in S}) \in \c{I}_q$ for any~$1 \le a < b \le q$, any~${R = \{r_1 < \dots < r_q\} \subseteq [p]}$, and any~$S \subseteq {]r_a, r_b[}$,
\end{compactitem}
then the subvector space of~$\b{k}\f{S}$ generated by the sums~$\sum_{\sigma} \F_\sigma$ over the classes of the congruences~$\equiv_n$ is a Hopf subalgebra of the Malvenuto--Reutenauer algebra~$\b{k}\f{S}$.
\end{corollary}

%\paragraph{Bounded crossings.}
%Fix four functions~$\north, \south, \east, \west : [n] \to \N$ and choose~$k \in \N$.
%For each~$a \in [n]$, draw $\north(a)$ upper vertical walls above~$a$, $\south(a)$ lower vertical walls below~$a$, and~$\min(\east(a), \west(a+1))$ horizontal walls from~$a$ and~$a+1$.
%Then the set~$\c{A}_{\north, \south, \east, \west}^{< k}$ of arcs that cross at most~$k-1$ of all these walls is an arc ideal.
%For certain choices of~$\north, \south, \east, \west$ and~$k$, the resulting arc ideals can correspond to:

\vspace{-3ex}
\paragraph{All arc diagrams.}

To conclude, we define a Hopf algebra~$\b{k}\f{D}^\star$ simultaneously involving the classes of all lattice congruences of the weak order, and containing the permutree algebra.
An \defn{extended arc} is a quadruple~$(a, b, n, S)$ with integers~$0 \le a < b \le n+1$, and~${S \subseteq {]a,b[}}$.
We denote by~$\c{A}_n^\star$ the set of all extended arcs.
%An extended arc~$(a, b, n, S)$ is \defn{initial} if~$a = 0$, \defn{terminal} if~$b = n+1$, and \defn{strict} otherwise.
The representation of arcs, the notions of crossing and forcing, as well as the operations~$\alpha^{+n}$ and~$\alpha^{\rightarrow n}$, are defined as for classical~arcs.
We denote by~$\f{I}_n^\star$ the set of extended arc ideals (\ie upper ideals of the forcing order~$\prec$ on~$\c{A}_n^\star$).

The \defn{juxtaposition}~$\juxta{\alpha}{\beta}$ of two extended arcs~$\alpha \eqdef (a, b, p, R)$ and~$\beta \eqdef (c, d, p, S)$ is the set~$\juxta{\alpha}{\beta} \eqdef \{(a, d, p, R \cup S)\}$ if~$b = c + 1$, and $\varnothing$ otherwise.
%In other words, $\alpha\beta$ is obtained by joining $\alpha$ to~$\beta$ when the final endpoint of~$\alpha$ appears just after the initial endpoint of~$\beta$, and is empty otherwise.
For~$\c{I}, \c{J} \subseteq \c{A}_p^\star$, we define the \defn{juxtaposition}~$\juxta{\c{I}}{\c{J}}$~by
\(
\juxta{\c{I}}{\c{J}} \eqdef \c{I} \cup \c{J} \cup \bigcup_{\alpha \in \c{I}, \beta \in \c{J}} \juxta{\alpha}{\beta}.
\)
As illustrated in \cref{fig:arcConcatenationSelection}, we define the \defn{concatenation} of two extended arc ideals~$\c{I} \subseteq \c{A}_m^\star$ and~$\c{J} \subseteq \c{A}_n^\star$ by
\(
\concat{\c{I}}{\c{J}} \eqdef \juxta{\c{I}^{+n}}{\c{J}^{\rightarrow m}}.
\)

Consider an extended arc ideal~$\c{K} \subseteq \c{A}_p^\star$ and a subset~$X \eqdef \{x_1 < \dots < x_q\}$ of~$[p]$. Define by convention~$x_0 \eqdef 0$ and~$x_{q+1} \eqdef p+1$.
As illustrated in \cref{fig:arcConcatenationSelection}, we define the \defn{selection}~$\select{\c{K}}{X}$ as the set of all arcs~$(a, b, q, S)$ such that there exist
\begin{compactitem}
\item positions $y_0 < \dots < y_r \in [p] \text{ with } x_a = y_0$ and $x_b = y_r$ while $y_1, \dots, y_{r-1} \notin X$, and
\item arcs~$(y_0, y_1, p, S_1), \dots, (y_{r-1}, y_r, p, S_r) \in \c{K}$ such that~$S = \set{\ell \in [q]}{x_\ell \in \bigcup S_k}$.
\end{compactitem}

\begin{figure}[h]
	\centerline{\includegraphics[scale=.77]{arcConcatenation}\qquad\includegraphics[scale=.77]{arcSelection}}
	\caption{The concatenation and selection for extended arc ideals.}
	\label{fig:arcConcatenationSelection}
\end{figure}

\vspace{-2ex}
\begin{proposition}[{\cite[Coro.\,28]{Pilaud-arcDiagramAlgebra}}]
The set~$\f{I}^\star \eqdef \bigsqcup_{n \in \N} \f{I}_n^\star$ of all extended arcs ideals, endowed with the concatenation~$\concatf$ and selection~$\selectf$, is a decoration set.
\end{proposition}

We now consider the map~$\arcs: \f{I}^\star \to \f{I}$ which sends an extended arc ideal to the arc ideal of its strict arcs (not starting at~$0$ or ending at~$n+1$).
It is clearly conservative so that we obtain a Hopf algebra~$\b{k}\f{D}^\star$ on pairs~$(\c{D}, \c{I})$, where~$\c{I}$ is any extended arc ideal and $\c{D}$ is a noncrossing arc diagram containing only strict arcs of~$\c{I}$.
The Hopf algebra~$\b{k}\f{D}^\star$ involves the classes of all lattice congruences of the weak order, and the concatenation and selection on extended arc diagrams was chosen to fulfill the following statement.

\begin{proposition}[{\cite[Prop.\,29]{Pilaud-arcDiagramAlgebra}}]
The permutree Hopf algebra~\cite{PilaudPons-permutrees} is a Hopf subalgebra of~$\b{k}\f{D}^\star$.
\end{proposition}

\vspace{-3ex}
%% 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}
