%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{61}
%% 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{xargs}
\usepackage{paralist}
\usepackage[inline,shortlabels]{enumitem}
\usepackage{overpic}
\usepackage{blkarray}
\usepackage{tikz}
\usepackage{accents}
\usepackage{multicol, multirow}
\graphicspath{{figures/}}

% theorems
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\smallset}[2]{\{ #1 \;|\; #2 \}} % small set notation
\newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} % big set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:
\newcommand{\N}{\mathbb{N}} % integers
\newcommand{\fS}{\mathfrak{S}} % symmetric group
\newcommand{\fB}{\mathfrak{B}} % binary trees

% relations
\newcommandx{\rel}[1][1=R]{\mathbin{\mathrm{#1}}} % relation
\newcommandx{\notrel}[1][1=R]{\mathbin{\!\raisebox{.02cm}{$\not$}\hspace{.02cm}\mathrm{#1}\hspace*{.01cm}}} % relation
\newcommand{\less}{\vartriangleleft} % less than in the poset
\newcommand{\more}{\vartriangleright} % more than in the poset
\newcommand{\bless}{\blacktriangleleft} % less than in the black poset
\newcommand{\bmore}{\blacktriangleright} % more than in the black poset
\newcommand{\dashV}{\rotatebox[origin=c]{180}{$\Vdash$}} % dashV as rotation of Vdash

% families of relations
\newcommand{\IRel}{\mathcal{R}} % all relations
\newcommand{\ITrans}{\mathcal{T}} % all transitive relations
\newcommand{\ISemiTrans}{\mathcal{ST}} % all semitransitive relations
\newcommand{\ISym}{\mathcal{S}} % all symmetric relations
\newcommand{\IAntisym}{\mathcal{A}} % all antisymmetric relations
\newcommand{\ICong}{\mathcal{C}} % all congruences
\newcommand{\IPos}{\mathcal{P}} % all posets
\newcommand{\IInc}{\mathcal{I}} % increasing relations
\newcommand{\IDec}{\mathcal{D}} % decreasing relations

% operations on relations
\newcommandx{\Inc}[1]{#1^{\mathsf{Inc}}} % incresing subrelation
\newcommandx{\Dec}[1]{#1^{\mathsf{Dec}}}% decresing subrelation
\newcommand{\tc}[1]{#1^{\mathsf{tc}}} % transitive closure of a relation
\DeclareMathOperator{\inv}{inv} % inversion set
\DeclareMathOperator{\ver}{ver} % version set
\newcommand{\wole}{\preccurlyeq} % weak order on relations
\newcommand{\meet}{\wedge} % meet in lattice
\newcommand{\join}{\vee} % join in lattice
\newcommand{\meetR}{\wedge_\IRel} % meet in reflexive relation lattice
\newcommand{\joinR}{\vee_\IRel} % join in reflexive relation lattice
\newcommand{\meetP}{\wedge_\IPos} % meet in transitive relation lattice
\newcommand{\joinP}{\vee_\IPos} % join in transitive relation lattice
\newcommand{\meetST}{\wedge_\ISemiTrans} % meet in semitransitive relation lattice
\newcommand{\joinST}{\vee_\ISemiTrans} % join in semitransitive relation lattice
\newcommand{\joinWO}{\vee_\fS} % join in weak order
\newcommand{\meetWO}{\wedge_\fS} % meet in weak order
\newcommand{\joinWOIP}{\vee_\WOIP} % join in weak order interval posets
\newcommand{\meetWOIP}{\wedge_\WOIP} % meet in weak order interval posets
\newcommand{\joinTO}{\vee_\fB} % join in Tamari order
\newcommand{\meetTO}{\wedge_\fB} % meet in Tamari order
\newcommand{\joinTOIP}{\vee_\TOIP} % join in Tamari order interval posets
\newcommand{\meetTOIP}{\wedge_\TOIP} % meet in Tamari order interval posets
\newcommand{\joinO}{\vee_\orientation} % join in permutree
\newcommand{\meetO}{\wedge_\orientation} % meet in permutree
\newcommand{\joinPIP}{\vee_{\PIP}} % join in permutree interval posets
\newcommand{\meetPIP}{\wedge_{\PIP}} % meet in permutree interval posets
\newcommand{\joinPEP}{\vee_{\PEP}} % join in permutree element posets
\newcommand{\meetPEP}{\wedge_{\PEP}} % meet in permutree element posets
\newcommand{\joinPFP}{\vee_{\PFP}} % join in permutree face posets
\newcommand{\meetPFP}{\wedge_{\PFP}} % meet in permutree face posets
\newcommand{\tid}[1]{#1^{\mathsf{tid}}} % transitive increasing deletion
\newcommand{\tdd}[1]{#1^{\mathsf{tdd}}} % transitive decreasing deletion
\newcommand{\TOIPd}[1]{#1^{\mathsf{TOIPd}}} % TOIP deletion
\newcommandx{\PIPd}[2][2=\orientation]{#1^{\mathsf{PIP}_{#2}\mathsf{d}}} % PIP deletion

% WO...
\newcommand{\WO}{\mathsf{WO}} % weak order
\newcommand{\WOEP}{\mathsf{WOEP}} % weak order element poset
\newcommand{\WOFP}{\mathsf{WOFP}} % weak order face poset
\newcommand{\WOIP}{\mathsf{WOIP}} % weak order interval poset
\newcommand{\IWOIP}{\mathsf{IWOIP}} % increasing weak order interval poset
\newcommand{\DWOIP}{\mathsf{DWOIP}} % decreasing weak order interval poset
\newcommand{\TO}{\mathsf{TO}} % Tamari order
\newcommand{\TOEP}{\mathsf{TOEP}} % Tamari order element poset
\newcommand{\TOFP}{\mathsf{TOFP}} % Tamari order face poset
\newcommand{\TOIP}{\mathsf{TOIP}} % Tamari order interval poset
\newcommand{\BOEP}{\mathsf{BOEP}} % boolean order element poset
\newcommand{\BOFP}{\mathsf{BOFP}} % boolean order face poset
\newcommand{\BOIP}{\mathsf{BOIP}} % boolean order interval poset
\newcommand{\orientation}{\mathbb{O}} % orientation
\newcommand{\positive}{^{+}} % positive
\newcommand{\negative}{^{-}} % negative
\newcommand{\Permutrees}{\mathfrak{P}} % permutrees
\newcommand{\SchroderPermutrees}{\mathfrak{SP}} % Schroder permutrees
\newcommandx{\surjection}[1][1=\orientation]{\Psi_{#1}} % surjection from permutations to #1-permutrees
\newcommand{\linearExtensions}{\mathcal{L}} % linear extensions of a poset
\newcommand{\none}[1]{\underaccent{\phantom{.}}{\accentset{\phantom{.}}{#1}}}
\newcommand{\up}[1]{\underaccent{\phantom{.}}{\overline{#1}}}
\newcommand{\down}[1]{\accentset{\phantom{.}}{\underline{#1}}}
\newcommand{\updown}[1]{\underline{\overline{#1}}}
\newcommandx{\PIP}[1][1=\orientation]{\mathsf{PIP}_{#1}} % permutree interval posets
\newcommandx{\PEP}[1][1=\orientation]{\mathsf{PEP}_{#1}} % permutree element posets
\newcommandx{\PFP}[1][1=\orientation]{\mathsf{PFP}_{#1}} % permutree face posets

% Polytopes
\DeclareMathOperator{\conv}{conv} % convex hull
\newcommandx{\Asso}[1][1=\signature]{\mathsf{Asso}(#1)} % associahedron
\newcommandx{\Perm}[1][1=n]{\mathsf{Perm}(#1)} % permutahedron
\newcommandx{\Para}[1][1=n]{\mathsf{Para}(#1)} % parallelepiped
\newcommandx{\PT}[1][1=\orientation]{\mathsf{PT}(#1)} % permutreehedron

% trees
\newcommandx{\tree}[1][1=T]{\mathrm{#1}} % tree
\newcommand{\bt}{\mathrm{bt}} % binary tree
\newcommand{\st}{\mathrm{st}} % schroder tree

% Hopf algebras
\newcommand{\product}{\cdot} % product
\newcommand{\coproduct}{\triangle} % coproduct
\newcommand{\underprod}[2]{{#1}\backslash{#2}} % #1 under #2
\newcommand{\overprod}[2]{{#1}\slash{#2}} % #1 over #2
\DeclareSymbolFont{Shuffle}{U}{shuffle}{m}{n}
\DeclareFontFamily{U}{shuffle}{}
\DeclareFontShape{U}{shuffle}{m}{n}{%
  <-8>shuffle7%
  <8->shuffle10%
}{}
\DeclareMathSymbol\shuffle{\mathbin}{Shuffle}{"001}
\DeclareMathSymbol\cshuffle{\mathbin}{Shuffle}{"002}
\newcommand{\shiftedShuffle}{\,\overline{\shuffle}\,} % shifted shuffle
\newcommand{\convolution}{\star} % convolution
\newcommand{\K}{\mathbb{K}} % field
\newcommand{\stdf}{\mathsf{std}} % standardization
\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

% others
\newcommand{\red}{\color{red}} % red command
\newcommand{\blue}{\color{blue}} % blue command
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\emph{\darkblue #1}} % emphasis of a definition
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % Exempli gratia
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures

%% TODO notes
\usepackage{todonotes}
\newcommand{\vincent}[1]{\todo[color=blue!30]{#1}}
\newcommand{\viviane}[1]{\todo[color=red!30]{#1}}

%% define your title in the usual way
\title{Algebraic structures on integer posets}

%% 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}.
	Supported by the French ANR grant
	SC3A~(15\,CE40\,0004\,01).}\addressmark{1} \and Viviane
	Pons\thanks{\href{mailto:viviane.pons@lri.fr}{viviane.pons@lri.fr}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau \\
	\addressmark{2}LRI, Univ. Paris-Sud - CNRS - Centrale Supelec - Univ. Paris-Saclay, Orsay
	}

%% 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 define a lattice structure and a Hopf algebra on integer posets and use them to recover relevant structures on the elements, the intervals and the faces in the permutahedron, the associahedron, the cube and more generally all permutreehedra.
}

%% put your French abstract here, or comment this out if you don't have one
\resume{
Nous d\'efinissons une structure de treillis et une alg\`ebre de Hopf sur
les ordre partiels sur les entiers, et nous les utilisons pour retrouver
des structures importantes sur les \'el\'ements, les intervalles et les
faces du permuta\`edre, de l'associa\`edre, du cube et en g\'en\'eral de
tous les permutarbro\`edres.
}

%% put your keywords here, or comment this out if you don't have them yet
%\keywords{math, maths, mathematics}

%% 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{61-Pilaud-Pons.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

Our original motivation is the fascinating interplay between the permutations, the binary trees, and the binary sequences.
These combinatorial objects are deeply related, in particular through their lattice structures (weak order, Tamari lattice, and boolean lattice), their Hopf algebras (Malvenuto--Reutenauer algebra~\cite{MalvenutoReutenauer}, Loday--Ronco algebra~\cite{LodayRonco}, and descent algebra~\cite{GelfandKrobLascouxLeclercRetakhThibon}), and their polytopes (permutahedron, associahedron, and cube).
These connections have been largely explained in~\cite{PilaudPons-permutrees}, where permutations, binary trees and binary sequences are all seen as special instances of permutrees.
Moreover, permutrees allow to interpolate between these families, leading to combinatorial objects that are structurally ``half'' permutations and ``half'' binary trees.

This abstract reports on further developments in this direction, with the objective to provide a unified understanding not only for the elements, but also for the intervals and the faces of the permutahedron,  the associahedron and the cube.
As explained in Section~\ref{sec:relevantFamilies}, the \defn{integer posets} (\ie posets on~$[n]$) provide a convenient model for all these combinatorial objects.
This abstract presents two algebraic structures on integer~posets:
\begin{compactitem}
\item In Section~\ref{sec:woposets}, we define the \defn{weak order} on integer posets and show that it is a lattice. It contains as subposets (and even sometimes sublattices) the classical weak order, the Tamari lattice, their interval lattices and their facial lattices~\cite{KrobLatapyNovelliPhanSchwer, PalaciosRonco, DermenjianHohlwegPilaud}.
\item In Section~\ref{sec:HopfAlgebra}, we define a Hopf algebra on integer posets. The vertices, intervals and faces of the permutahedra index certain quotients of this algebra, and the vertices, intervals and faces of the associahedra index subalgebras of these quotients.
\end{compactitem}

%Integer posets provide convenient combinatorial models for the elements, the intervals and the faces in 

This abstract relies on three papers connected to this topic: one on permutrees~\cite{PilaudPons-permutrees}, one on the weak order on posets~\cite{ChatelPilaudPons}, and one on Hopf algebras on integer posets~\cite{PilaudPons-integerPosetAlgebra}.
More details and proofs can be found in the long versions.

\section{Weak order on integer posets}
\label{sec:woposets}

\subsection{Integer binary relations}

An \defn{integer binary relation} of size~$n$ is a binary relation on~$[n] \eqdef \{1, \dots, n\}$, that is, a subset~$\rel$ of~$[n]^2$. As usual, we write equivalently~$(a,b) \in \rel$ or~$a \rel b$. 
We only consider reflexive relations and let~$\IRel_n$ be the set of all reflexive binary relations on~$[n]$. % The inclusion order defines a lattice structure on~$\IRel_n$ whose meet and join are given by intersection and union.

%We only consider reflexive relations (\ie $u \rel u$ for all~$u \in [n]$) and often omit to mention the reflexive parts of the relation.
The \defn{increasing} and \defn{decreasing subrelations} of an integer relation~$\rel \in \IRel_n$ are the relations defined by $\Inc{\rel} \eqdef \set{(a,b) \in \rel}{a \le b}$ and~$\Dec{\rel} \eqdef \set{(b,a) \in \rel}{a \le b}$.
In our pictures, we always represent an integer relation~$\rel \in \IRel_n$ as follows: we write the numbers $1, \dots, n$ from left to right and we draw the increasing relations of~$\rel$ above in blue and the decreasing relations of~$\rel$ below in red. Although we only consider reflexive relations, we always omit the relations~$(i,i)$ in the pictures. See \eg Figure~\ref{fig:weakOrderPosets}.

We consider the \defn{weak order} on~$\IRel_n$, defined by~$\rel \wole \rel[S]$ if~${\Inc{\rel} \supseteq \Inc{\rel[S]}}$ and~${\Dec{\rel} \subseteq \Dec{\rel[S]}}$.
It is clearly a graded lattice with meet~${\rel[R]} \meetR {\rel[S]} = ( \Inc{\rel} \cup \Inc{\rel[S]} ) \cup ( \Dec{\rel} \cap \Dec{\rel[S]} )$ and join ${\rel[R]} \joinR {\rel[S]} = ( \Inc{\rel} \cap \Inc{\rel[S]} ) \cup ( \Dec{\rel} \cup \Dec{\rel[S]} )$.
The name chosen for this order is explained in Section~\ref{sec:relevantFamilies}, where we explore its connection to various relevant combinatorial lattices.

\subsection{Integer posets}

An \defn{integer poset} is a reflexive ($a \rel a$), antisymmetric (${a \rel b \; \wedge \; b \rel a \implies a = b}$) and transitive ($a \rel b \; \wedge \; b \rel c \implies a \rel c$) integer relation.
We denote by~$\IPos_n$ the set of integer posets on~$[n]$.
We want to show that the subposet of the weak order induced by integer posets is a lattice.
Note that~$\meetR$ and~$\joinR$ do not preserve transitivity, so that $\IPos_n$ does not induce a sublattice of the weak order on~$\IRel_n$.
%We want to understand the meet and join on~$\IPos_n$.
%
%We first consider a weaker notion of transitivity.
%A relation~$\rel \in \IRel_n$ is \defn{semi-transitive} if both~$\Inc{\rel}$ and~$\Dec{\rel}$ are transitive.
%We denote by~$\ISemiTrans(n)$ the set of semi-transitive relations on~$[n]$.
%The subposet~$(\ISemiTrans(n), \wole)$ of the weak order induced by semi-transitive relations is a lattice with meet~${{\rel[R]} \meetST {\rel[S]} = \tc{( \Inc{\rel} \cup \Inc{\rel[S]} )} \cup ( \Dec{\rel} \cap \Dec{\rel[S]} )}$ and join~${{\rel[R]} \joinST {\rel[S]} = ( \Inc{\rel} \cap \Inc{\rel[S]} ) \cup \tc{( \Dec{\rel} \cup \Dec{\rel[S]} )}}$, where~$\tc{\rel[T]}$ is the \defn{transitive closure} defined by $\tc{\rel[T]} \eqdef \set{(u,w) \in [n]^2}{\exists\; v_1, \dots, v_p \in [n] \text{ such that } u = v_1 \rel[T] v_2 \rel[T] \dots \rel[T] v_{p-1} \rel[T] v_p = w}$.
%This is illustrated in the following example: \\[-.1cm]
%\input{semitrans_meet}
%
%We now consider the set~$\ITrans(n)$ of transitive relations on~$[n]$.
For~$\rel \in \IRel_n$, define the \defn{transitive closure}~$\tc{\rel}$, the \defn{transitive decreasing deletion}~$\tdd{\rel}$ and the \defn{transitive increasing deletion}~$\tid{\rel}$ as \\[.1cm]
\centerline{$\tc{\rel} \eqdef \smallset{(u,w) \in [n]^2}{\exists\; v_1, \dots, v_p \in [n] \text{ such that } u = v_1 \rel v_2 \rel \dots \rel v_{p-1} \rel v_p = w}$} \\[.1cm]
\centerline{$\tdd{\rel} \eqdef {\rel} \ssm \smallset{(b,a) \in \Dec{\rel}}{\exists \; i \le b \text{ and } j \ge a \text{ such that } i \rel b \rel a \rel j \text{ while } i \notrel j},$} \\[.1cm]
\centerline{$\tid{\rel} \eqdef {\rel} \ssm \smallset{(a,b) \in \Inc{\rel}}{\exists \; i \ge a \text{ and } j \le b \text{ such that } i \rel a \rel b \rel j \text{ while } i \notrel j}.$} \\[.1cm]
Note that in these definitions, $i$ and~$j$ may coincide with~$a$ and~$b$ (since we assumed that all our relations are reflexive). 
%Observe that two decreasing relations have been deleted: $(3,1)$ (take~$i=2$ and~$j=1$, or~$i=3$ and~$j=2$) and $(4,1)$ (take $i=4$ and $j=2$).  
The next statement is illustrated below and in Figure~\ref{fig:weakOrderPosets}.

\begin{theorem}
\label{thm:posetLattice}
The subposet of the weak order induced by integer posets is a lattice with meet~and~join
${{\rel[R]} \meetP {\rel[S]} = \! \tdd{\big( \tc{(\Inc{\rel} \cup \Inc{\rel[S]})} \cup (\Dec{\rel} \cap \Dec{\rel[S]}) \big)}}$ and~${{\rel[R]} \joinP {\rel[S]} = \! \tid{\big( (\Inc{\rel} \cap \Inc{\rel[S]}) \cup \tc{(\Dec{\rel} \cup \Dec{\rel[S]})} \big)}}$.
\end{theorem}

\input{figures/trans_meet}

\begin{figure}
%	\input{figures/weakOrderPosets3}
	\centerline{\includegraphics[scale=1]{weakOrderPosets3}}
	\vspace{-.3cm}
	\caption{The weak order on integer posets of size~$3$.}
	\label{fig:weakOrderPosets}
\end{figure}

\section{Relevant families of integer posets}
\label{sec:relevantFamilies}

In this section, we observe that certain relevant combinatorial objects can be interpreted by specific integer posets and that  the subposets of the weak order induced by these integer posets correspond to classical lattice structures on these combinatorial objects.
%In this section, we present our motivation to study Theorem~\ref{thm:posetLattice}. We observe that many relevant combinatorial objects (\eg permutations, binary trees, binary sequences,~...) can be interpreted by specific integer posets. Moreover, the subposets of the weak order induced by these integer posets correspond to classical lattice structures on these combinatorial objects (\eg the classical weak order, the Tamari lattice, the boolean lattice,~...). 

\subsection{Permutations}
\label{subsec:permutations}

For a permutation~$\sigma \in \fS_n$, a pair~$(a,b) \in [n]^2$ is a \defn{version} if~$a \le b$ and~$\sigma^{-1}(a) \le \sigma^{-1}(b)$, and an \defn{inversion} if~$a \ge b$ and~$\sigma^{-1}(a) \le \sigma^{-1}(b)$.
The \defn{weak order} on~$\fS_n$ is the lattice defined by inclusion of inversions: ${\sigma \wole \tau \iff \inv(\sigma) \subseteq \inv(\tau) \iff \ver(\sigma) \supseteq \ver(\tau)}$.
Geometrically, its Hasse diagram can be interpreted as the graph of the \defn{permutahedron} $\Perm \eqdef \conv\set{(\sigma(1), \dots, \sigma(n))}{\sigma \in \fS_n}$ oriented from~$[1,2,\dots,n]$~to~$[n,\dots,2,1]$.

Each permutation~$\sigma \in \fS_n$ corresponds to a \defn{weak order element poset}~$\less_\sigma$ defined by~$u \less_\sigma v$ if~${\sigma^{-1}(u) \le \sigma^{-1}(v)}$. %In other words, $\less_\sigma$ is the chain~$\sigma(1) \less_\sigma \dots \less_\sigma \sigma(n)$.
%In other words, the weak order element posets are just the total orders on~$[n]$.
See Figure~\ref{fig:permutrees} for an example with~$\sigma = [2,7,5,1,3,4,6]$.
Define~${\WOEP_n \eqdef \smallset{{\less_\sigma}}{\sigma \in \fS_n}}$.
The following statement motivates Section~\ref{sec:woposets}.

\begin{proposition}
\label{prop:WOEP}
\begin{compactitem}
\item A poset~${\less}$ is in~$\WOEP_n$ if and only if $a \less b$ or~$a \more b$ for all~$a,b \in [n]$.
\item For any~$\sigma \in \fS_n$, the increasing (resp.~decreasing) relations of~$\less_\sigma$ are the versions (resp.~inversions) of~$\sigma$.
Therefore, for any~${\sigma, \sigma' \in \fS_n}$, we have~${\less_\sigma} \wole {\less_{\sigma'}} \iff \sigma \wole \sigma'$.
\item Moreover, the weak order on~$\WOEP_n$ is a sublattice of the weak order on~$\IPos_n$.
\end{compactitem}
\end{proposition}

We now present a similar approach to intervals of the weak order.
For~${\sigma \wole \sigma' \in \fS_n}$, let~$[\sigma, \sigma'] \eqdef \set{\tau \in \fS_n}{\sigma \wole \tau \wole \sigma'}$.
The permutations of~$[\sigma, \sigma']$ are precisely the linear extensions of the \defn{weak order interval poset}~$\less_{[\sigma,\sigma']} \eqdef \bigcap_{\sigma \wole \tau \wole \sigma'} {\less_\tau} = {\less_{\sigma}} \cap {\less_{\sigma'}} = {\Inc{\less_{\sigma'}}} \cup {\Dec{\less_\sigma}}$.
Define~$\WOIP_n \eqdef \smallset{{\less_{[\sigma,\sigma']}}}{\sigma, \sigma' \in \fS_n, \; \sigma \wole \sigma'}$.
%As proved in~\cite[Thm.~6.8]{BjornerWachs}, a poset~${\less} \in \IPos_n$ is in~$\WOIP_n$ if and only if $a \less c \implies a \less b \text{ or } b \less c$ and $a \more c \implies a \more b \text{ or } b \more c$ for all~$a < b < c$.

\begin{proposition}
\label{prop:WOIP}
\begin{compactitem}
\item A poset~${\less}$ is in~$\WOIP_n$ if and only if it satisfies ${a \less c \Rightarrow (a \less b \text{ or } b \less c)}$ and ${a \more c \Rightarrow (a \more b \text{ or } b \more c)}$ for all~$a < b < c$ \cite[Theorem~6.8]{BjornerWachs}.
\item For any~$\sigma \wole \sigma'$ and~$\tau \wole \tau'$ in~$\fS_n$, we have ${\less_{[\sigma,\sigma']}} \wole {\less_{[\tau,\tau']}} \iff \sigma \wole \tau$ and~$\sigma' \wole \tau'$.
\item The weak order on~$\WOIP_n$ is a lattice with meet~${\less_{[\sigma,\sigma']}} \meetWOIP {\less_{[\tau,\tau']}} = {\less_{[\sigma \meetWO \tau, \, \sigma' \meetWO \tau']}}$ and join~${\less_{[\sigma,\sigma']}} \joinWOIP {\less_{[\tau,\tau']}} = {\less_{[\sigma \joinWO \tau, \, \sigma' \joinWO \tau']}}$.
However, the weak order on~$\WOIP_n$ is not a sublattice of the weak order on~$\IPos_n$.
\end{compactitem}
\end{proposition}

Finally, we consider a face of the permutahedron, that is, an ordered partition~$\pi$ of~$[n]$. 
We see~$\pi$ as a \defn{weak order face poset}~$\less_\pi$ defined by~$u \less_\pi v$ if~$\pi^{-1}(u) < \pi^{-1}(v)$. 
See Figure~\ref{fig:SchroderPermutrees} for an example with~$\pi = 125|37|46$.
Define~$\WOFP_n \eqdef \set{{\less_\pi}}{\pi \text{ ordered partition of } [n]}$.

\begin{proposition}
\label{prop:WOFP}
\begin{compactitem}
\item A poset~${\less}$ is in~$\WOFP_n$ if and only if~${\less} \in \WOIP_n$ and ${(a \less b \Leftrightarrow b \more c)}$ and~${(a \more b \Leftrightarrow b \less c)}$ for all~$ a < b < c$ with $a \not\less c$ and~$a \not\more c$.
\item For any ordered partitions~$\pi, \pi'$ of~$[n]$, we have~${\less_\pi} \wole {\less_{\pi'}} \iff \pi \wole \pi'$ in the facial weak order of~\cite{KrobLatapyNovelliPhanSchwer, PalaciosRonco, DermenjianHohlwegPilaud}.
\item The weak order on~$\WOFP_n$ is a lattice but not a sublattice of the weak order on~$\IPos_n$, nor on~$\WOIP_n$.
\end{compactitem}
\end{proposition}

\subsection{Binary trees}
\label{subsec:binaryTrees}

\begin{figure}[t]
\centerline{
	\begin{tabular}{c@{\qquad}c@{\qquad}c@{\qquad}c}
		  permutation~$\sigma$
		& binary tree~$\tree$
		& binary sequence~$\chi$
		& permutree~$\tree$
		\\
		  $2751346 \qquad\quad$ & & &
		\\[-.5cm]
		  \raisebox{.2cm}{\includegraphics[scale=.8]{permutreePermutation}}
		& \includegraphics[scale=.8]{permutreeBinaryTree}
		& \includegraphics[scale=.8]{permutreeBinarySequence}
		& \includegraphics[scale=.8]{permutreeGeneric}
		\\[-.6cm]
		  \;\scalebox{.8}{\input{figures/relations/posetWOEP.tex}}
		& \;\scalebox{.8}{\input{figures/relations/posetTOEP.tex}}
		& \;\scalebox{.8}{\input{figures/relations/posetBOEP.tex}}
		& \;\scalebox{.8}{\input{figures/relations/posetPEP.tex}}
		\\[-.4cm]
		  ${\less_\sigma} \in \WOEP_n$
		& ${\less_{\tree}} \in \TOEP_n$
		& ${\less_\chi} \in \BOEP_n$
		& ${\less_{\tree}} \in \PEP$
	\end{tabular}
}
	\caption{Posets for permutations, binary trees, binary sequences, and permutrees.}
	\label{fig:permutrees}
\end{figure}

Let~$\fB_n$ be the set of \defn{rooted binary trees} with~$n$ nodes (always labeled in inorder). % (all vertices in the left (resp.~right) child of a vertex~$v$ of~$\tree$ receive a label smaller (resp.~larger) than the label of~$v$).
The \defn{Tamari lattice} on~$\fB_n$ is the lattice~$\wole$ whose cover relations are given by \defn{right rotations} on binary trees.
It was reinterpreted in~\cite{BjornerWachs, Reading-CambrianLattices} as a lattice quotient of the weak order as follows.
Consider the surjection~$\bt$ which maps a permutation~$\sigma \eqdef \sigma_1 \dots \sigma_n \in \fS_n$ to the binary tree~$\bt(\sigma) \in \fB_n$ obtained by successive insertions of~$\sigma_n, \dots, \sigma_1$ in a binary (search) tree. 
The fiber of a tree~$\tree$ is precisely the set of linear extensions of~$\tree$. It is an interval of the weak order whose minimal and maximal elements respectively avoid the patterns~$312$ and~$132$.
The Tamari order is given by~$\tree \wole \tree'$ if and only if there exist~$\sigma, \sigma' \in \fS_n$ such that~$\bt(\sigma) = \tree$, $\bt(\sigma') = \tree'$ and~${\sigma \wole \sigma'}$.
%whose meet~$\meetTO$ and join~$\joinTO$ are given by
%\[
%\tree \meetTO \tree' = \bt(\sigma \meetWO \sigma')
%\quad\text{and}\quad
%\tree \joinTO \tree' = \bt(\sigma \joinWO \sigma')
%\]
%for any representatives~$\sigma, \sigma' \in \fS_n$ such that~$\bt(\sigma) = \tree$ and~$\bt(\sigma') = \tree'$. Note that in particular, $\tree \wole \tree'$ if and only if~$\sigma \wole \sigma'$ where~$\sigma$ and~$\sigma'$ denote the minimal (resp.~maximal) linear extensions of~$\tree$ and~$\tree'$ respectively. For example, the minimal (resp.~maximal) tree is the left (resp.~right) comb whose unique linear extension is~$[1,2,\dots,n]$ (resp.~$[n,\dots,2,1]$).
%This lattice structure is the \defn{Tamari lattice} whose cover relations are given by \defn{right rotations} on binary trees.
%See~\cite{Tamari, BjornerWachs, Reading-CambrianLattices}
% It was introduced by D.~Tamari~\cite{TamariFestschrift} on Dyck paths, our presentation is a more modern perspective~\cite{BjornerWachs, Reading-CambrianLattices}.
Geometrically, the Hasse diagram of the Tamari lattice is the graph of the associahedron~\cite{Loday} oriented from the left comb to the right comb.

We aim at reinterpreting the Tamari lattice, its interval lattice and its facial interval lattice using specific posets.
%
Each tree~$\tree$ corresponds to a \defn{Tamari order element poset}~$\less_{\tree}$, defined by~${i \less_{\tree} j}$ when~$i$ is a descendant of~$j$ in~$\tree$. In other words, the Hasse diagram of~$\less_{\tree}$ is the tree~$\tree$ oriented towards its root. 
See Figure~\ref{fig:permutrees}.
% An illustration is provided in \fref{fig:toep}. 
% Note that the increasing (resp.~decreasing) subposet of~$\less_{\tree}$ is given by~$i \Inc{\less_{\tree}} j$ (resp.~$i \Dec{\less_{\tree}} j$) if and only if $i$ belongs to the left (resp.~right) subtree of~$j$ in~$\tree$.
Define~${\TOEP_n \eqdef \smallset{{\less_{\tree}}}{\tree \in \fB_n}}$.

\begin{proposition}
\label{prop:TOEP}
\begin{compactitem}
\item A poset~${\less}$ is in~$\TOEP_n$ if and only if
\begin{enumerate*}[(i)]
\item $(a \less c \Rightarrow b \less c)$ and $(a \more c \Rightarrow a \more b)$ for all~$a < b < c$ and
\item there exists ${a < b < c}$ such that~$a \less b \more c$ for all~$a < c$ incomparable in~$\less$.
\end{enumerate*}
\item For any binary trees~$\tree, \tree' \in \fB_n$, we have~${\less_{\tree}} \wole {\less_{\tree'}} \iff \tree \wole \tree'$.
\item Moreover, the Tamari lattice on~$\TOEP_n$ is a sublattice of the weak order on~$\IPos_n$.
\end{compactitem}
\end{proposition}

%We now consider intervals in the Tamari lattice.
For~$\tree \wole \tree' \in \fB_n$, consider the Tamari interval~$[\tree, \tree'] \eqdef \set{\tree[S] \in \fB_n}{\tree \wole \tree[S] \wole \tree'}$. We see it as the \defn{Tamari order interval poset}~${{\less_{[\tree, \tree']}} \eqdef \bigcap_{\tree \wole \tree[S] \wole \tree'} {\less_{\tree}} = {\less_{\tree}} \cap {\less_{\tree'}} = {\Inc{\less_{\tree'}}} \cap {\Dec{\less_{\tree}}}}$.
Define~$\TOIP_n \eqdef \smallset{{\less_{[\tree,\tree']}}}{\tree, \tree' \in \fB_n, \tree \wole \tree'}$.

\begin{proposition}
\label{prop:TOIP}
\begin{compactitem}
\item A poset~$\less$ is in~$\TOIP_n$ if and only if $(a \less c \Rightarrow b \less c)$ and~$(a \more c \Rightarrow a \more b)$ for all~$a < b < c$.
\item For any~$\tree[S] \wole \tree[S]'$ and~$\tree \wole \tree'$ in~$\fB_n$, we have~${\less_{[\tree[S], \tree[S]']}} \wole {\less_{[\tree, \tree']}} \! \iff \! \tree[S] \wole \tree$~and~${\tree[S]' \wole \tree'}$.
\item %The weak order on~$(\TOIP_n, \wole)$ is a lattice with meet~${\less_{[\tree[S],\tree[S]']}} \meetTOIP {\less_{[\tree,\tree']}} = {\less_{[\tree[S] \meetTO \tree, \tree[S]' \meetTO \tree']}}$ and join~${\less_{[\tree[S],\tree[S]']}} \joinTOIP {\less_{[\tree,\tree']}} = {\less_{[\tree[S] \joinTO \tree, \tree[S]' \joinTO \tree']}}$.
Moreover, the weak order on~$\TOIP_n$ is a sublattice of the weak order on~$\IPos_n$.
\end{compactitem}
\end{proposition}

\begin{figure}[b]
\centerline{
	\begin{tabular}{c@{\qquad}c@{\qquad}c@{\quad}c}
		  ordered partition~$\pi$
		& Schr\"oder tree~$\tree[S]$
		& ternary sequence~$\xi$
		& Schr\"oder permutree~$\tree[S]$
		\\
		  $125|37|46 \qquad\qquad\;\,$ & & &
		\\[-.3cm]
		  \raisebox{.1cm}{\includegraphics[scale=.8]{SchroderPermutreeOrderedPartition}}
		& \includegraphics[scale=.8]{SchroderPermutreeSchroderTree}
		& \includegraphics[scale=.8]{SchroderPermutreeTernarySequence}
		& \includegraphics[scale=.8]{SchroderPermutreeGeneric}
		\\[-.4cm]
		  \;\scalebox{.8}{\input{figures/relations/posetWOFP.tex}}
		& \;\scalebox{.8}{\input{figures/relations/posetTOFP.tex}}
		& \;\scalebox{.8}{\input{figures/relations/posetBOFP.tex}}
		& \;\scalebox{.8}{\input{figures/relations/posetPFP.tex}}
		\\[-.2cm]
		  ${\less_\pi} \in \WOFP_n$
		& ${\less_{\tree[S]}} \in \TOFP_n$
		& ${\less_\xi} \in \BOFP_n$
		& ${\less_{\tree[S]}} \in \PFP$
	\end{tabular}
}
	\caption{Posets for ordered partitions, Schr\"oder trees, ternary sequences, and Schr\"oder permutrees.}
	\label{fig:SchroderPermutrees}
\end{figure}

Consider now a face of the associahedron, that is, a Schr\"oder tree~$\tree[S]$ (a rooted tree where each internal node has at least two children).
We label the angles between two consecutive children in inorder, meaning that each angle is labeled after the angles in its left child and before the angles in its right child.
We associate to~$\tree[S]$ the poset~$\less_{\tree[S]}$ where~$i \less_{\tree[S]} j$ if and only if the angle labeled~$i$ belongs to the left or to the right child of the angle labeled~$j$.
See Figure~\ref{fig:SchroderPermutrees}.
Note that~${\less}_{\tree[S]} = {\less}_{[\tree^{\min}, \tree^{\max}]}$, where~$\tree^{\min}$ (resp.~$\tree^{\max}$) is obtained by replacing the nodes of~$\tree[S]$ by left (resp.~right) combs.
Define~$\TOFP_n \eqdef \smallset{{\less_{\tree[S]}}}{\tree[S] \text{ Schr\"oder tree on $[n]$}}$.

\begin{proposition}
\label{prop:TOFP}
\begin{compactitem}
\item A poset~${\less}$ is in~$\TOFP_n$ if and only if ${\less} \in \TOIP_n$  and for all~$a < c$ incomparable in~$\less$, either there exists~$a < b < c$ such that~$a \not\more b \not\less c$, or for all~$a < b < c$ we have~$a \more b \less c$.
\item For any Schr\"oder trees~$\tree[S], \tree[S]'$, we have~${\less}_{\tree[S]} \wole {\less}_{\tree[S]'} \iff \tree[S] \wole \tree[S]'$ in the \defn{facial weak order} on the associahedron~$\Asso[n]$ studied in~\cite{PalaciosRonco, DermenjianHohlwegPilaud}.
This order is a quotient of the facial weak order on the permutahedron by the fibers of the Schr\"oder tree insertion~$\st$.
\item The weak order on~$\TOFP_n$ is a lattice but not a sublattice of the weak order on~$\IPos_n$, nor on~$\WOIP_n$, nor on~$\TOIP_n$. 
\end{compactitem}
\end{proposition}

Finally, we want to show that the binary tree insertion and the Schr\"oder tree insertion can as well be directly understood at the level of posets.
For this, define the \defn{$\TOIP$ deletion} by~$
{\TOIPd{\less}} \eqdef {\less} \ssm ( \set{(a,c)}{\exists \; a < b < c, \; b \not\less c} \cup \set{(c,a)}{\exists \; a < b < c, \; a \not\more b} )$.
%This map sends~$\WOEP_n$, $\WOIP_n$ and~$\WOFP_n$ to~$\TOEP_n$, $\TOIP_n$ and~$\TOFP_n$ respectively.
%In fact, it is a simple generalization of both the binary tree insertion and the Schr\"oder tree insertion.
% Then~${\TOIPd{\less}} \in \TOIP_n$ for any poset~${\less} \in \IPos_n$ (see Lemma~\ref{lem:IPIPidDPIPdd1}). We compare this map with the binary search tree and Schr\"oder tree insertions described earlier (see Proposition~\ref{prop:PIPd/bst}, Corollary~\ref{coro:PIPd/bstIntervals} and Proposition~\ref{prop:PIPd/st}).

\begin{proposition}
\label{prop:TOIPd/bst}
For any permutation~$\sigma$, weak order interval~$\sigma \wole \sigma'$, and ordered partition~$\pi$, \\[.1cm]
\centerline{$
{\TOIPd{(\less_\sigma)}} = {\less_{\bt(\sigma)}},
\qquad
{\TOIPd{(\less_{[\sigma,\sigma']})}} = {\less_{[\bt(\sigma), \; \bt(\sigma')]}}
\qquad\text{and}\qquad
{\TOIPd{(\less_\pi)}} = {\less_{\st(\pi)}}.
$}
\end{proposition}

\subsection{Permutrees}

To conclude this section, we want to mention that the statements of Sections~\ref{subsec:permutations} \&~\ref{subsec:binaryTrees} extend to the permutrees, a common generalization of permutations and binary~trees.

A \defn{permutree} is an oriented tree~$\tree$ with nodes labeled by~$[n]$, such that 
\begin{compactitem}
\item any node has either one or two parents and either one or two children,
\item if the node~$j$ has two parents (resp.~children), then all labels in its left ancestor (resp.~descendant) subtree are smaller than~$j$ while all labels in its right ancestor (resp.~descendant) subtree are larger than~$j$.
\end{compactitem}
See \eg Figure~\ref{fig:permutrees}.
The \defn{orientation} of a permutree~$\tree$ is~$\orientation(\tree) = (\orientation\positive, \orientation\negative)$ where~$\orientation\positive$ is the set of labels of the nodes with two parents while~$\orientation\negative$ is the set of labels of the nodes with two children.
We denote by~$\Permutrees(\orientation)$ the set of permutrees with a given orientation~$\orientation$.
As illustrated in Figure~\ref{fig:permutrees}, a permutree with orientation~$(\varnothing, \varnothing)$ (resp.~$(\varnothing, [n])$, resp.~$([n],[n])$) is nothing else but a permutation (resp.~a binary tree, resp.~a binary sequence).

To each permutree~$\tree$ corresponds its \defn{permutree element poset}~$\less_{\tree}$ where $i \less_{\tree} j$ if there is an oriented path from~$i$ to~$j$ in~$\tree$. %See Figure~\ref{fig:permutrees}. 
%To visualize the orientation~$\orientation$ in the poset~$\less_{\tree}$, we overline (resp.~underline) the elements of~$\orientation\positive$ (resp.~of~$\orientation\negative$).
Define~${\PEP \eqdef \set{{\less_{\tree}}}{\tree \in \Permutrees(\orientation)}}$.
%
Many properties of permutations and binary trees extend to permutrees. In particular:
\begin{compactitem}
\item For a permutree~$\tree \in \Permutrees(\orientation)$, the set of linear extensions~$\linearExtensions(\tree)$ of~$\less_{\tree}$ is an interval in the weak order on~$\fS_n$ whose minimal element avoids\footnote{A permutation~$\sigma$ contains the pattern~$31$-$\down{2}$ if~$\sigma = \sigma_1 ca \sigma_2 b \sigma_3$ with~$a < b < c$ and~$b \in \orientation\negative$.} the patterns~$31$-$\down{2}$ and~$\up{2}$-$31$, and whose maximal element avoids the patterns~$13$-$\down{2}$ and~$\up{2}$-$31$.
\item For any orientation~$\orientation$ of~$[n]$, the
set~$\set{\linearExtensions(\tree)}{\tree \in \Permutrees(\orientation)}$
forms a partition of~$\fS_n$. This defines a surjection\footnote{This
surjection can also be described directly as an insertion algorithm,
see~\cite[Section~2.2]{PilaudPons-permutrees}.}~$\surjection : \fS_n \to \Permutrees(\orientation)$, which sends a permutation~${\sigma \in \fS_n}$ to the unique permutree~$\tree \in \Permutrees(\orientation)$ such that~$\sigma \in \linearExtensions(\tree)$. % For example, $\surjection[\protect{(\varnothing,[n])}](\sigma) = \bt(\sigma)$ is the result of inserting~$\sigma$ from left to right in a binary search tree.
\item This partition defines a lattice congruence of the weak order
(see~\cite{Reading-latticeCongruences, Reading-CambrianLattices,
PilaudPons-permutrees} for details). This yields the \defn{permutree
lattice}\footnote{This lattice structure can equivalently be described by
right rotations in permutrees~\cite[Section~2.6]{PilaudPons-permutrees}.}, defined by~$\tree \wole \tree'$ if and only if there exist~$\sigma, \sigma' \in \fS_n$ such that~$\surjection(\sigma) = \tree$, $\surjection(\sigma') = \tree'$ and~$\sigma \wole \sigma'$. Its minimal (resp.~maximal) element is the \defn{left} (resp.~\defn{right}) \defn{$\orientation$-comb}: it is a chain where each vertex in~$\orientation\positive$ has an additional empty left (resp.~right) parent, while each vertex in~$\orientation\negative$ has an additional empty right (resp.~left) child.
\item Geometrically, the Hasse diagram of the permutree lattice is the
graph of the \defn{permutreehedron}~$\PT$~\cite[Section~3]{PilaudPons-permutrees} oriented from the left to the right $\orientation$-comb.
\end{compactitem}

The next statement extends Propositions~\ref{prop:WOEP} \&~\ref{prop:TOEP}. An orientation~${\orientation = (\orientation\positive, \orientation\negative)}$ is said to be \defn{covering} if~$\{2, \dots, n-1\} \subseteq \orientation\positive \cup \orientation\negative$.

\begin{proposition}
\label{prop:PEP}
\begin{compactitem}
\item $\PEP$ is characterized by local conditions\footnote{The detailed
conditions are too intricate for this abstract but can be found
in~\cite[Propositions~60 \& 63]{ChatelPilaudPons}.} as in Propositions~\ref{prop:WOEP} \&~\ref{prop:TOEP}.
\item For any permutrees~$\tree, \tree' \in \Permutrees(\orientation)$, we have~${\less_{\tree}} \wole {\less_{\tree'}} \iff \tree \wole \tree'$.
\item The permutree lattice on~$\PEP$ is always a sublattice of the weak order on~$\WOIP_n$. It is a sublattice of the weak order on~$\IPos_n$ when~$\orientation$ is covering, but not in general.
\end{compactitem}
\end{proposition}

We now consider intervals in the permutree lattice.
For two permutrees~$\tree, \tree' \in \Permutrees(\orientation)$ with~$\tree \wole \tree'$, let~$[\tree, \tree'] \eqdef \set{\tree[S] \in \Permutrees(\orientation)}{\tree \wole \tree[S] \wole \tree'}$. It corresponds to the \defn{permutree interval poset}~${\less_{[\tree, \tree']}} \eqdef {\Inc{\less_{\tree'}}} \cap {\Dec{\less_{\tree}}}$.
Define~${\PIP \eqdef \smallset{{\less_{[\tree,\tree']}}}{\tree, \tree' \in \Permutrees(\orientation), \tree \wole \tree'}}$.
The next statement extends Propositions~\ref{prop:WOIP} \&~\ref{prop:TOIP}.

\begin{proposition}
\label{prop:PIP}
\begin{compactitem}
\item A poset~$\less$ is in~$\PIP$ if and only if~${\less} \in \WOIP_n$ and for any ${a < b < c}$, we have $(a \less c \Rightarrow a \less b)$ and~$(a \more c \Rightarrow b \more c)$ when~$b \in \orientation\positive$, and $(a \less c \Rightarrow b \less c)$ and~$(a \more c \Rightarrow a \more b)$ when~$b \in \orientation\negative$.
\item For any~$\tree[S] \wole \tree[S]'$ and~$\tree \wole \tree'$ in~$\Permutrees(\orientation)$, we have~${\less_{[\tree[S], \tree[S]']}} \wole {\less_{[\tree, \tree']}} \iff \tree[S] \wole \tree$ and~$\tree[S]' \wole \tree'$.
\item The weak order on~$\PIP$ is always a sublattice of the weak order on~$\WOIP_n$. It is a sublattice of the weak order on~$\IPos_n$ when~$\orientation$ is covering, but not in general.
\end{compactitem}
\end{proposition}

To extend Propositions~\ref{prop:WOFP} \&~\ref{prop:TOFP}, we now
consider facial intervals of the permutree lattice.
The faces of the permutreehedron~$\PT$ correspond to the Schr\"oder
permutrees with orientation~$\orientation$, which are obtained from the
permutrees of~$\Permutrees(\orientation)$ by edge contractions\footnote{A
more direct but more technical definition of Schr\"oder permutrees can
also be found in~\cite[Section~5]{PilaudPons-permutrees}.}.
Define the \defn{permutree face poset}~${\less}_{\tree[S]} = {\less}_{[\tree^{\min}, \tree^{\max}]}$, where~$\tree^{\min}$ (resp.~$\tree^{\max}$) is obtained by replacing the nodes of~$\tree[S]$ by left (resp.~right) combs (with the correct orientations).
See Figure~\ref{fig:SchroderPermutrees}.
Define~$\PFP \eqdef \set{{\less_{\tree[S]}}}{\tree[S] \text{ Schr\"oder permutree with orientation~$\orientation$}}$.

\begin{proposition}
\label{prop:PFP}
\begin{compactitem}
\item $\PFP$ is characterized by local conditions\footnotemark[2]{} as in Propositions~\ref{prop:WOFP} \&~\ref{prop:TOFP}.
\item For any Schr\"oder permutrees~$\tree[S], \tree[S]'$, we have~${\less}_{\tree[S]} \wole {\less}_{\tree[S]'} \iff \tree[S] \wole \tree[S]'$ in the \defn{facial weak order} on the permutreehedron~$\PT$ studied in~\cite{PilaudPons-permutrees, DermenjianHohlwegPilaud}.
\item The weak order on~$\PFP$ is a lattice but not a sublattice of the weak order on~$\IPos_n$, nor on~$\WOIP_n$, nor on~$\PIP$. 
\end{compactitem}
\end{proposition}

Finally, for~${\less} \in \IPos_n$, we define its \defn{$\PIP$ deletion}~$\PIPd{\less}$ to be the poset obtained by removing simultaneously from~$\less$ all increasing relations~$(a,c)$ such that:
\begin{compactitem}
\item either $\exists \, a < b_1 < \dots < b_k < c$ with~$a \not\less b_1 \not\less \dots \not\less b_k \not\less c$ (preventing ${\less} \in \WOIP$),
\item or $\exists \, a \le n < p \le c$ with~$n \in \{a\} \cup \orientation\negative$,~$p \in \{c\} \cup \orientation\positive$, and~$n \not\less p$.
\end{compactitem}
and their analogue decreasing relations. We now give an analogue of Proposition~\ref{prop:TOIPd/bst}.

\begin{proposition}
\label{prop:PIPd}
For any permutation~$\sigma$, weak order interval~$\sigma \wole \sigma'$, and ordered partition~$\pi$, \\[.1cm]
\centerline{$
{\PIPd{(\less_\sigma)}} = {\less_{\surjection(\sigma)}},
\quad
{\PIPd{(\less_{[\sigma,\sigma']})}} = {\less_{[\surjection(\sigma), \; \surjection(\sigma')]}}
\quad\text{and}\quad
{\PIPd{(\less_\pi)}} = {\less_{\surjection(\pi)}},
$} \\[.1cm]
where~$\surjection(\sigma)$ (resp.~$\surjection(\pi)$) is the permutree (resp.~Schr\"oder permutree) associated to~$\sigma$ (resp.~$\pi$).% with~$\sigma \in \linearExtensions(\sigma)$ and~$\surjection(\pi)$ is the Schr\"oder permutree with~$\linearExtensions(\pi) \subseteq \linearExtensions(\surjection(\pi))$.
\end{proposition}

%\[
%\begin{array}{l@{}l}
%{\PIPd{\less}} \eqdef {\less} & \ssm \set{(a,c)}{\begin{array}{ll} \multirow{2}{.1cm}{\!\!\text{or}} & \exists \, a < b_1 < \dots < b_k < c \text{ such that } a \not\less b_1 \not\less \dots \not\less b_k \not\less c \\ & \exists \, a \le n < p \le c, \; n \in \{a\} \cup \orientation\negative, p \in \{c\} \cup \orientation\positive \text{ and } n \not\less p \end{array}} \\
%& \ssm \set{(a,c)}{\begin{array}{ll} \multirow{2}{.1cm}{\!\!\text{or}} & \exists \, a < b_1 < \dots < b_k < c \text{ such that } a \not\less b_1 \not\less \dots \not\less b_k \not\less c \\ & \exists \, a \le n < p \le c, \; n \in \{a\} \cup \orientation\negative, p \in \{c\} \cup \orientation\positive \text{ and } n \not\less p \end{array}}
%\end{array}
%\]

%\begin{figure}[t]
%\centerline{
%	\begin{tabular}{c|cccc}
%		  $\orientation$
%		& $(\{2,4,7\}, \{1,4,6\})$
%		& $(\varnothing, \varnothing)$
%		& $(\varnothing, [7])$
%%		& $(\{3,6,7\}, \{1,2,4,5\})$
%		& $([7], [7])$
%		\\[.1cm]
%		\hline
%		\\[-.4cm]
%		  \rotatebox{90}{\hspace{1cm}permutree}
%		& \includegraphics[scale=.8]{permutreeGeneric}
%		& \includegraphics[scale=.8]{permutreePermutation}
%		& \includegraphics[scale=.8]{permutreeBinaryTree}
%%		& \includegraphics[scale=.8]{permutreeCambrianTree}
%		& \includegraphics[scale=.8]{permutreeBinarySequence}
%		\\[-.4cm]
%		  \rotatebox{90}{\hspace{1.3cm}$\PEP$}
%		& \;\scalebox{.8}{\input{figures/relations/posetPEP.tex}}
%		& \;\scalebox{.8}{\input{figures/relations/posetWOEP.tex}}
%		& \;\scalebox{.8}{\input{figures/relations/posetTOEP.tex}}
%%		& \;\scalebox{.8}{\input{figures/relations/posetCOEP.tex}}
%		& \;\scalebox{.8}{\input{figures/relations/posetBOEP.tex}}
%		\\[-.4cm]
%		\hline
%		\\[-.4cm]
%		  \rotatebox{90}{\begin{minipage}{2cm} \begin{center} Schr\"oder \\[-.2cm] permutree \end{center} \end{minipage}}
%		& \includegraphics[scale=.8]{SchroderPermutreeGeneric}
%		& \includegraphics[scale=.8]{SchroderPermutreeOrderedPartition}
%		& \includegraphics[scale=.8]{SchroderPermutreeSchroderTree}
%%		& \includegraphics[scale=.8]{SchroderPermutreeCambrianTree}
%		& \includegraphics[scale=.8]{SchroderPermutreeTernarySequence}
%		\\[-.2cm]
%		  \rotatebox{90}{\hspace{.6cm}$\PFP$}
%		& \;\scalebox{.8}{\input{figures/relations/posetPFP.tex}}
%		& \;\scalebox{.8}{\input{figures/relations/posetWOFP.tex}}
%		& \;\scalebox{.8}{\input{figures/relations/posetTOFP.tex}}
%%		& \;\scalebox{.8}{\input{figures/relations/posetCOFP.tex}}
%		& \;\scalebox{.8}{\input{figures/relations/posetBOFP.tex}}
%		\\[-.4cm]
%	\end{tabular}
%}
%	\caption{Permutrees and Schr\"oder permutrees with their posets. While the first column generic, the last three illustrate specific orientations corresponding to permutations, binary trees, and binary sequences.}
%	\label{fig:SchroderPermutrees}
%\end{figure}

\section{Hopf algebra on integer posets}
\label{sec:HopfAlgebra}

In this section, we construct a Hopf algebra on integer posets.
We then show that the permutations, the weak order intervals, and the ordered partitions index certain quotients of the integer poset algebra, and  that the binary trees, the Tamari intervals, and the Schr\"oder trees index subalgebras of these quotients.
Define~$\IRel_\N \eqdef \bigsqcup_{n \ge 0} \IRel_n$ and similarly for the other families of relations considered in this paper.

\subsection{Hopf algebras on binary relations and integer posets} 

As for the weak order, we first define our Hopf algebra at the level of binary relations.
We consider the vector space~$\K\IRel_\N \eqdef \bigoplus_{n \ge 0} \K\IRel_n$ indexed by all integer binary relations of arbitrary size.
We denote by~$\rel_X \eqdef \set{(i,j) \in [k]^2}{x_i \rel x_k}$ the \defn{restriction} of an integer relation~$\rel \in \IRel_n$ to a subset~$X = \{x_1, \dots, x_k\} \subseteq [n]$.
We define:
\begin{compactitem}
\item the \defn{product} of two integer relations~${\rel[R] \in \IRel_m}$ and~$\rel[S] \in \IRel_n$ by~$\rel[R] \product \rel[S] \eqdef \sum \rel[T]$ where $\rel[T]$ ranges over all integer relations~$\rel[T] \in \IRel_{m+n}$ with~$\rel[T]_{[m]} = \rel[R]$ and ${\rel[T]_{[n+m] \ssm [m]} = \rel[S]}$.
\item the \defn{coproduct} of an integer relation~$\rel[T] \in \IRel(p)$ by~$\coproduct({\rel[T]}) \eqdef \sum \rel[T]_X \otimes \rel[T]_Y$ where the sum ranges over all partitions~$X \sqcup Y \subseteq [p]$ such that $x \rel[T] y$ and $y \notrel[T] x$ for all $(x,y) \in X \times Y$.
\end{compactitem}
%
%For example, we have
\begin{align*}
\Eg \quad \input{figures/productRelations},  \\[-.5cm]
\text{and} \; \input{figures/coproductRelations},
\end{align*}

\noindent
where the terms in the coproduct arise from $X$ ranging in $\{ 1,2,3 \}$, $\{ 1 \}$, $\{ 1,3 \}$, and $\varnothing$.
Note that the product~$\rel[R] \product \rel[S]$ is the sum over the interval between~${\underprod{\rel[R]}{\rel[S]} \eqdef {\rel[R]} \cup {\overline{\rel[S]}} \cup ([m] \times \overline{[n]})}$ and ${\overprod{\rel[R]}{\rel[S]} \eqdef {\rel[R]} \cup {\overline{\rel[S]}} \cup (\overline{[n]} \times [m])}$ in the weak order on~$\IRel_{m+n}$ (where we denote the shifts ${\overline{\rel[S]}} \eqdef \set{(m+i, m+j)}{(i,j) \in \rel[S]}$ and~${\overline{[n]} \eqdef [m+n] \ssm [m]}$).

\begin{proposition}
\label{prop:algebraRelations}
%(\K\IRel_\N, {\product}, {\coproduct})$ is a Hopf algebra.
The product~$\product$ and coproduct~$\coproduct$ endow~$\K\IRel_\N$ with a Hopf algebra structure, \ie~$\coproduct(\rel[R] \product \rel[S]) = \coproduct(\rel[R]) \product \coproduct(\rel[S])$ where the last product is~${(a \otimes b) \product (c \otimes d) = (a \product c) \otimes (b \product d)}$.
\end{proposition}

We now use this Hopf algebra on binary relations to get a Hopf algebra on posets.

\begin{proposition}
\label{prop:algebraPosets}
If~$\rel \in \IRel_\N$ is not a poset, then none of the summands in~$\rel[R] \product \rel[S]$ (resp.~$\coproduct(\rel)$) is a poset (resp.~the tensor product of two posets).
In other words, the vector subspace of~$\K\IRel_\N$ generated by integer relations which are not posets is a Hopf ideal of~$(\K\IRel_\N, \product, \coproduct)$.
The quotient of~$(\K\IRel_\N, \product, \coproduct)$ by this ideal is thus a Hopf algebra~$(\K\IPos_\N, \product, \coproduct)$ on integer posets.
\end{proposition}

\Eg $\input{figures/productPosets}$ in~$\K\IPos_\N$.

\begin{proposition}
For~${\less} \in \IPos_m$ and~${\bless} \in \IPos_n$, the product~${\less} \product {\bless}$ is the interval between $\underprod{\less}{\bless}$ and $\overprod{\less}{\bless}$ in the weak order on~$\IPos_{m+n}$.
\end{proposition}

\subsection{Hopf algebras on permutations, intervals, and ordered partitions}

We now want to construct Hopf algebras on~$\WOEP_\N$, $\WOIP_\N$ and~$\WOFP_\N$ as quotients of the integer poset Hopf algebra~$(\IPos_\N, \product, \coproduct)$.
The important point is that all these families of posets are defined by local conditions on their relations, and that a contradiction to these conditions cannot be destroyed by the product or the coproduct.

We start with weak order element posets~$\WOEP_\N$. For two permutations~${\sigma \in \fS_m}$ and~${\tau \in \fS_n}$, define the \defn{shifted shuffle}~$\sigma \shiftedShuffle \tau$ (resp.~the \defn{convolution}~$\sigma \convolution \tau$) as the permutation of~$\fS_{m+n}$ whose first~$m$ values (resp.~positions) are in the same relative order as~$\sigma$ and whose last~$n$ values (resp.~positions) are in the same relative order as~$\tau$.
%
%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 form~$\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*}
%
For example,
\begin{align*}
{\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} \}, \\
\text{and}\quad
{\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{align*}

\noindent
Recall that the Malvenuto--Reutenauer Hopf algebra~\cite{MalvenutoReutenauer} is the Hopf algebra on permutations with product~$\sigma \product \tau \eqdef \sum_{\rho \in \sigma \shiftedShuffle \tau} \rho$ and coproduct~$\coproduct(\rho) \eqdef \sum_{\rho \in \sigma \convolution \tau} \sigma \otimes \tau$.
This Hopf algebra can be interpreted as a quotient of the integer poset Hopf algebra~$(\K\IPos_\N, \product, \coproduct)$.

\begin{proposition}
\label{prop:algebraWOEP}
%The map~$\sigma \mapsto {\less_\sigma}$ defines a Hopf algebra isomorphism from the Malvenuto--Reutenauer Hopf algebra on permutations to the quotient~$(\K\WOEP_\N, \product, \coproduct)$ of the integer poset Hopf algebra~$(\K\IPos_\N, \product, \coproduct)$ by the Hopf ideal generated by non total integer posets.
\begin{compactitem}
\item %If~$\less \in \IPos_\N$ is not total, then none of the summands in~${\less} \product {\bless}$ (resp.~$\coproduct({\less})$) is total (resp.~the tensor product of two total orders). 
The vector subspace of~$\K\IPos_\N$ generated by non-total integer posets is a Hopf ideal of~$(\K\IPos_\N, \product, \coproduct)$.
The quotient of the poset Hopf algebra~$(\K\IPos_\N, \product, \coproduct)$ by this ideal is thus a Hopf algebra~$(\K\WOEP_\N, \product, \coproduct)$ on total orders.
\item The map~$\sigma \mapsto {\less_\sigma}$ defines a Hopf algebra isomorphism from the Malvenuto--Reutenauer Hopf algebra on permutations~\cite{MalvenutoReutenauer} to~$(\K\WOEP_\N, \product, \coproduct)$.
\item For any permutations~$\sigma \in \fS_m$ and~$\tau \in \fS_n$, the product~${\less_\sigma} \product {\less_\tau}$ is the interval between $\underprod{\less_\sigma}{\less_\tau}$ and $\overprod{\less_\sigma}{\less_\tau}$ in the weak order on~${\WOEP_{m+n}}$.
\end{compactitem}
\end{proposition}

\Eg $\input{figures/productWOEP}$ in~$\K\WOEP_\N$.

We now consider weak order interval posets~$\WOIP_\N$, characterized in Proposition~\ref{prop:WOIP}.

\begin{proposition}
\label{prop:algebraWOIP}
\begin{compactitem}
\item The vector subspace of~$\K\IPos_\N$ generated by~$\IPos_\N \ssm \WOIP_\N$ is a Hopf ideal of~$(\K\IPos_\N, \product, \coproduct)$.
The quotient of the integer poset algebra~$(\K\IPos_\N, \product, \coproduct)$ by this ideal is thus a Hopf algebra~$(\K\WOIP_\N, \product, \coproduct)$ on weak order intervals.
\item For any~$\sigma \wole \sigma' \in \fS_m$ and~$\tau \wole \tau' \in \fS_n$, the product~${\less_{[\sigma,\sigma']}} \product {\less_{[\tau,\tau']}}$ is the interval between $\underprod{\less_{[\sigma,\sigma']}}{\less_{[\tau,\tau']}}$ and $\overprod{\less_{[\sigma,\sigma']}}{\less_{[\tau,\tau']}}$ in the weak order on~$\WOIP_{m+n}$.
\end{compactitem}
\end{proposition}

\Eg $\input{figures/productWOIP}$ in~$\K\WOIP_\N$.

Finally, a similar statement holds for weak order face posets~$\WOFP_\N$, characterized in Proposition~\ref{prop:WOFP}.
It turns out that the resulting algebra was studied in~\cite{Chapoton}.

\begin{proposition}
\label{prop:algebraWOFP}
\begin{compactitem}
\item The vector subspace of~$\K\IPos_\N$ generated by~$\IPos_\N \ssm \WOIP_\N$ is a Hopf ideal of~$(\K\IPos_\N, \product, \coproduct)$.
The quotient of the poset Hopf algebra~$(\K\IPos_\N, \product, \coproduct)$ by this ideal is thus a Hopf algebra~$(\K\WOFP_\N, \product, \coproduct)$ on faces of the permutahedron.
\item The map~$\pi \mapsto {\less_\pi}$ defines a Hopf algebra isomorphism from the Chapoton Hopf algebra on ordered partitions~\cite{Chapoton} to~$(\K\WOFP_\N, \product, \coproduct)$.
\item For any ordered partitions~$\pi$ of~$[m]$ and~$\omega$ of~$[n]$, the product~${\less_\pi} \product {\less_\omega}$ is the interval between $\underprod{\less_\pi}{\less_\omega}$ and $\overprod{\less_\pi}{\less_\omega}$ in the weak order on~${\WOFP_{m+n}}$.
\end{compactitem}
\end{proposition}

\Eg $\input{figures/productWOFP}$ in~$\K\WOFP_\N$.

\subsection{Hopf algebras on binary trees, Tamari intervals, and Schr\"oder trees}

\enlargethispage{.2cm}
To conclude, we use the $\TOIP$ deletion defined in the end of Section~\ref{subsec:binaryTrees} to construct Hopf subalgebras of~$\K\WOEP_\N$, $\K\WOIP_\N$ and~$\K\WOFP_\N$ respectively indexed by~$\TOEP_\N$, $\TOIP_\N$ and~$\TOFP_\N$. This idea mimics the construction of the Loday--Ronco algebra on binary trees~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees}, that can be defined as a Hopf subalgebra of the Malvenuto--Reutenauer algebra on permutations~\cite{MalvenutoReutenauer}.

\begin{proposition}
\begin{compactitem}
\item The vector subspace~$\K\TOEP_\N$ of~$\K\WOEP_\N$ generated by the sums of the fibers $\set{{\less} \in \WOEP_\N}{{\TOIPd{\less}} = {\bless}}$ for all~${\bless} \in \TOEP_\N$ is stable by $\product$ and~$\coproduct$.
\item For any binary trees~$\tree[S] \in \fB_m$ and~$\tree[T] \in \fB_n$, the product~${\less_{\tree[S]}} \product {\less_{\tree[T]}}$ is the interval between $\underprod{\less_{\tree[S]}}{\less_{\tree[T]}}$ and $\overprod{\less_{\tree[S]}}{\less_{\tree[T]}}$ in the weak order on~${\TOEP_{m+n}}$.
\item The map~$\tree \mapsto {\less_{\tree}}$ is a Hopf algebra isomorphism from the Loday--Ronco algebra on binary trees~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees} to~$(\K\TOEP_\N, \product, \coproduct)$.
\end{compactitem}
\end{proposition}

We now proceed to the same construction for Tamari intervals.
To the best of our knowledge, our approach provides the first Hopf algebra on Tamari intervals.

\begin{proposition}
\begin{compactitem}
\item The vector subspace~$\K\TOIP_\N$ of~$\K\WOIP_\N$ generated by the sums of the fibers $\set{{\less} \in \WOIP_\N}{{\TOIPd{\less}} = {\bless}}$ for all~${\bless} \in \TOIP_\N$ is stable by $\product$ and~$\coproduct$.
\item For any Tamari intervals~$\tree[S] \wole \tree[S]' \in \fB_m$ and~$\tree[T] \wole \tree[T]' \in \fB_n$, the product~${\less_{[\tree[S], \tree[S]']}} \product {\less_{[\tree[T], \tree[T]']}}$ is the interval between $\underprod{\less_{[\tree[S], \tree[S]']}}{\less_{[\tree[T], \tree[T]']}}$ and $\overprod{\less_{[\tree[S], \tree[S]']}}{\less_{[\tree[T], \tree[T]']}}$ in the weak order on~${\WOIP_{m+n}}$.
\end{compactitem}
\end{proposition}

The same construction for faces recovers Chapoton's Schr\"oder trees Hopf Algebra~\cite{Chapoton}.

\begin{proposition}
\begin{compactitem}
\item The vector subspace~$\K\TOFP_\N$ of~$\K\WOFP_\N$ generated by the sums of the fibers $\set{{\less} \in \WOFP_\N}{{\TOIPd{\less}} = {\bless}}$ for all~${\bless} \in \TOFP_\N$ is stable by $\product$ and~$\coproduct$.
\item For any Schr\"oder trees~$\sigma[S]$ on~$[m]$ and~$\tree[T]$ on~$[n]$, the product~${\less_{\tree[S]}} \product {\less_{\tree[T]}}$ is the interval between $\underprod{\less_{\tree[S]}}{\less_{\tree[T]}}$ and $\overprod{\less_{\tree[S]}}{\less_{\tree[T]}}$ in the weak order on~${\WOFP_{m+n}}$.
\item The map~$\tree[S] \mapsto {\less_{\tree[S]}}$ is a Hopf algebra isomorphism from the Chapoton algebra on Schr\"oder trees~\cite{Chapoton} to~$(\K\TOFP_\N, \product, \coproduct)$.
\end{compactitem}
\end{proposition}

Finally, let us mention that similar ideas can be used to uniformly construct Hopf algebra structures on permutrees, permutree intervals, and Schr\"oder permutrees.
Following~\cite{ChatelPilaud, PilaudPons-permutrees}, one first defines some decorated versions of the Hopf algebras~$\K\WOEP_\N$, $\K\WOIP_\N$ and~$\K\WOFP_\N$, where each poset on~$[n]$ appears~$4^n$ times with all possible different orientations.
One then constructs Hopf algebras on~$\K\PEP[]$, $\K\PIP[]$ and~$\K\PFP[]$ using the fibers of the surjective map~$({\less}, \orientation) \mapsto {\PIPd{\less}}$.
See~\cite{PilaudPons-permutrees, PilaudPons-integerPosetAlgebra} for details.


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