%% The class cedram-ALCO is just a wrapper around amsart.cls (version 2) %% implementing the layout of the journal, and some additionnal %% administrative commands. Two options are available: %% * "francais" for a paper written in French (probably never used), %% in this case you should use alttitle, altkeywords and altabstract %% in order to pass English metadata. %% * "Unicode" if the file is UTF-8 encoded. \documentclass[ALCO]{cedram} %\OneNumberAllTheorems %\overfullrule5pt %% Here you might want to add some standard packages if those %% functionnalities are required. \usepackage[shortlabels]{enumitem} \usepackage{float} \usepackage{amsthm, wasysym, hypcap, stmaryrd, shuffle, xargs, multicol, overpic, pdflscape, multirow, hvfloat, minibox, accents, etoolbox, dsfont} % \hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue, urlcolor=darkblue} \usepackage{tikz}\usetikzlibrary{trees,snakes,shapes,arrows,matrix,calc} \graphicspath{{figures/}{figures/nodes/}} \makeatletter \def\input@path{{figures/}} \makeatother %% The production will anyway use amsmath, hyperref, graphicx %% User definitions if necessary... Such definitions are forbidden %% inside titles, abstracts or the bibliography. %\newcommand{\la}{\longrightarrow} % ... %% Theorems should be defined using amsthm syntax % theorems % \newtheorem{corollary}[theorem]{Corollary} % \newtheorem{proposition}[theorem]{Proposition} % \newtheorem{lemma}[theorem]{Lemma} % \newtheorem{definition}[theorem]{Definition} %\equalenv{conjecture}{conj} % newcommands % math special letters \newcommand{\R}{\mathbb{R}} % reals \newcommand{\N}{\mathbb{N}} % naturals \newcommand{\Z}{\mathbb{Z}} % integers \newcommand{\C}{\mathbb{C}} % complex \newcommand{\I}{\mathbb{I}} % set of integers \newcommand{\HH}{\mathbb{H}} % hyperplane \newcommand{\fA}{\mathfrak{A}} % alternating group \newcommand{\fS}{\mathfrak{S}} % symmetric group \newcommand{\fP}{\mathfrak{P}} % partitions \newcommand{\cC}{\mathcal{C}} % circle \newcommand{\fX}{\mathfrak{X}} % generating function \renewcommand{\b}[1]{\mathbf{#1}} % bold 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:}} }} % =: \newcommand{\polar}{^\diamond} % polar \newcommand{\blackPolar}{^\blacklozenge} % black polar \newcommand{\simplex}{\triangle} % simplex \newcommand{\binomspec}[3]{\begin{pmatrix} #1 \\ #2 \end{pmatrix}_{\!\!#3}} % special binomial coefficient (ou {\begin{Bmatrix} #1 \\ #2 \end{Bmatrix}_{#3}) \renewcommand{\implies}{\Rightarrow} % imply sign \newcommand{\sep}{|} % separation for ordered partitions \newcommand{\freeSep}{\freeGap\hspace{-.92mm}|} % free separation for ordered partitions \newcommand{\bsep}{\,|\,} % big separation for ordered partitions \newcommand{\Id}{\mathrm{Id}} % identity \newcommand{\sign}{\mathrm{sign}} % sign % trees \newcommandx{\graphG}[1][1=G]{\mathrm{#1}} % graph \newcommandx{\tree}[1][1=T]{\mathrm{#1}} % tree \newcommand{\ground}{\mathrm{V}} % vertex set \newcommand{\decoration}{\delta} % decoration of a Cambrian tree \newcommand{\Decorations}{\{\noneCirc{}, \downCirc{}, \upCirc{}, \upDownCirc{}\}} % all decorations \newcommand{\less}{\preccurlyeq} % refinement order on decorations \newcommand{\pdecoration}{\decoration_p} % p-decoration of a decorated permutation \newcommand{\vdecoration}{\decoration_v} % v-decoration of a decorated permutation \newcommand{\generatingTree}{\mathcal{T}} % generating tree of permutations avoiding the two Cambrian patterns \newcommand{\generatingTreeSchroder}{\mathcal{S}} % generating tree of permutations avoiding the two Cambrian patterns \newcommand{\level}{m} % level in generating tree \newcommand{\up}[1]{\overline{#1}} \newcommand{\upr}[1]{{\red \up{#1}}} \newcommand{\upb}[1]{{\blue \up{#1}}} \newcommand{\down}[1]{\underline{#1}} \newcommand{\downr}[1]{{\red \down{#1}}} \newcommand{\downb}[1]{{\blue \down{#1}}} \newcommand{\updown}[1]{\up{\down{#1}}} \newcommand{\updownr}[1]{{\red \updown{#1}}} \newcommand{\updownb}[1]{{\blue \updown{#1}}} \newcommand{\linearExtensions}{\mathcal{L}} % linear extensions \newcommand{\circDecoration}{{\text{\tiny$\bigcirc$}}} % small blue circle \newcommand{\squareDecoration}{{\text{\raisebox{-.05cm}{$\square$}}}} % small red square \newcommand{\edgecut}[2]{\left( #1 \;\middle\|\; #2 \right)} % edge cut \newcommand{\cuts}{\mathsf{EC}} % edge cuts \newcommand{\decreasingCuts}{\mathsf{DEC}} % decreasing edge cuts \newcommand{\dash}{\text{-}} \newcommand{\Permutrees}{\mathcal{PT}} % permutrees \newcommand{\SchrPermutrees}{\mathrm{SchrPT}} % Schroder-permutrees \newcommand{\factCatalan}[1]{\text{\bf C}(#1)} % factorial-Catalan number \newcommand{\factSchroder}[1]{\text{\bf S}(#1)} % factorial Schroder number % arc diagrams \newcommand{\arcDiagrams}{\mathcal{A}} % arc diagrams \newcommand{\asc}{\mathsf{asc}} % ascent bijection from permutations to arc diagrams \newcommand{\desc}{\mathsf{desc}} % descent bijection from permutations to arc diagrams % Polytopes \newcommandx{\Perm}[1][1=n]{\mathds{P}\mathrm{erm}(#1)} % permutahedron \newcommandx{\Asso}[1][1=n]{\mathds{A}\mathrm{sso}(#1)} % associahedron \newcommandx{\Para}[1][1=n]{\mathds{P}\mathrm{ara}(#1)} % parallelepiped \newcommandx{\Zono}[1][1=\decoration]{\mathds{Z}\mathrm{ono}(#1)} % zonotope \newcommandx{\Permutreehedron}[1][1=\decoration]{\mathds{PT}(#1)} % permutreehedron \newcommand{\Cone}{\mathrm{C}} % cone \newcommand{\fan}{\mathcal{F}} % fan \newcommandx{\Fan}[1][1=\decoration]{\fan(#1)} % permutree fan \newcommand{\Hyp}{\b{H}^=} % hyperplane \newcommand{\HS}{\b{H}^\ge} % half-space \newcommand{\face}{\mathsf{F}} % face % operators \DeclareMathOperator{\conv}{conv} % convex hull \DeclareMathOperator{\cone}{cone} % cone hull \DeclareMathOperator{\coinv}{coinv} % coinversion set \newcommand{\meet}{\wedge} % meet in lattice \newcommand{\join}{\vee} % join in lattice \newcommand{\projDown}{\pi_{\!\downarrow\!}} % down projection lattice congruence \newcommand{\projUp}{\pi^{\!\uparrow\!}} % up projection lattice congruence \newcommand{\verticalSymmetry}[1]{#1^{\;\mathbin{\tikz [thin, baseline=-0.2em] \draw [<->] (0em,-.3em) -- (0em,.3em);}}\,} % vertical symmetry of permutrees \newcommand{\horizontalSymmetry}[1]{#1^{\mathbin{\tikz [baseline=-0.2em] \draw [<->] (-.3em,0em) -- (.3em,0em);}}} % horizontal symmetry of permutrees \newcommand{\horizontalVerticalSymmetry}[1]{#1^{\mathbin{\tikz [baseline=-0.2em] {\draw [<->] (0em,-.3em) -- (0em,.3em); \draw [<->] (-.4em,0em) -- (.4em,0em);}}}} % horizontal and vertical symmetry of permutrees % Hopf algebras \newcommand{\FQSym}{\mathsf{FQSym}} % quasi-symmetric functions \newcommand{\PBT}{\mathsf{PBT}} % PBT (Loday-Ronco) \newcommand{\PermutreeAlgebra}{\mathsf{PT}} % Permutree Algebra \newcommand{\SchrPermutreeAlgebra}{\mathsf{SchrPT}} % Schroder-Permutree Algebra \newcommand{\OrdPart}{\mathsf{OrdPart}} % ordered partition Hopf algebra \newcommand{\sfx}{\mathsf{x}} % element of Alg \newcommand{\sfy}{\mathsf{y}} % element of Alg \newcommand{\sfz}{\mathsf{z}} % element of Alg \newcommand{\integerPointTransform}{\mathbb{Z}} % integer point transform % operations \newcommand{\product}{\cdot} % product \newcommand{\coproduct}{\triangle} % coproduct \newcommand{\shiftedShuffle}{\,\bar\shuffle\,} % shifted shuffle \newcommand{\convolution}{\star} % shifted shuffle \newcommand{\underprod}[2]{{#1}\backslash{#2}} % #1 under #2 \newcommand{\overprod}[2]{{#1}\slash{#2}} % #1 over #2 % 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 % correspondences \newcommand{\permutreeCorresp}{\Theta} % bijection from the permutations to the leveled permutrees \newcommand{\SchroderPermutreeCorresp}{\Theta^\star} % bijection from the permutations to the leveled Schroder permutrees \newcommandx{\surjection}[2][1=\decoration, 2=\decoration']{\Psi_{#1}^{#2}} % surjection from #1-permutrees to #2-permutrees \newcommandx{\surjectionSchroder}[2][1=\decoration, 2=\decoration']{{\Psi^\star}_{#1}^{#2}} % surjection from #1-permutrees to #2-permutrees \newcommand{\PSymbol}{\mathbf{P}} % P-symbol \newcommand{\QSymbol}{\mathbf{Q}} % Q-symbol \newcommand{\SchroderPSymbol}{\mathbf{P}^\star} % Schroder P-symbol % others \newcommand{\fref}[1]{Figure~\ref{#1}} % reference figures \renewcommand{\ie}{\textit{i.e.}~} % id est \renewcommand{\eg}{\textit{e.g.}~} % 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]{\emph{\darkblue #1}} % emphasis of a definition \usepackage{todonotes} \newcommand{\vincent}[1]{\todo[color=blue!30]{#1}} \newcommand{\viviane}[1]{\todo[color=red!30]{#1}} \newcommand{\para}[1]{\medskip\noindent\framebox{\textsc{#1}}} % paragraph \DeclareRobustCommand{\verylongrightarrow}{\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\rightarrow} \newcommand{\includeSymbol}[1]{\ensuremath{% \mathchoice {\raisebox{-.7mm}{\includegraphics[height=2.2ex]{#1}}} {\raisebox{-.7mm}{\includegraphics[height=2.2ex]{#1}}} {\raisebox{-.6mm}{\includegraphics[height=1.6ex]{#1}}} {\raisebox{-.5mm}{\includegraphics[height=1ex]{#1}}} }} \robustify{\includeSymbol} \newcommand{\noneCirc}{\includeSymbol{none}} \newcommand{\upCirc}{\includeSymbol{up}} \newcommand{\downCirc}{\includeSymbol{down}} \newcommand{\upDownCirc}{\includeSymbol{updown}} \newcommand{\noneSquare}{\includeSymbol{noneSquare}} \newcommand{\upSquare}{\includeSymbol{upSquare}} \newcommand{\downSquare}{\includeSymbol{downSquare}} \newcommand{\upDownSquare}{\includeSymbol{updownSquare}} % Tikz macros \usepackage{tikz} \usetikzlibrary{positioning,arrows,matrix,chains,shadows,shapes} \tikzstyle{Point} = [fill, radius=0.08] \newcommand{\bannedGap}{}%{\textcolor{red}{{\scalebox{.5}{$\bf\times$}}}} \newcommand{\freeGap}{\textcolor{blue}{{\scalebox{.5}{$\bullet$}}}} % formating the table of contents \makeatletter \def\l@section{\@tocline{1}{3pt}{0pc}{}{}} \makeatother \let\oldtocpart=\tocpart \renewcommand{\tocpart}[2]{\hspace{0em}\bf\large\oldtocpart{#1}{#2}} \let\oldtocsection=\tocsection \renewcommand{\tocsection}[2]{\hspace{0em}\bf\oldtocsection{#1}{#2}} %% The title of the paper: amsart's syntax. \title{Permutrees} %% Authors according to amsart's syntax + distinction between Given %% and Proper names: \author{\firstname{Vincent} \lastname{Pilaud}} %% Do not include any other information inside \author's argument! %% Other author data have special commands for them: \address%[VPi] {CNRS \& LIX, \'Ecole Polytechnique, Palaiseau} \email{vincent.pilaud@lix.polytechnique.fr} \urladdr{http://www.lix.polytechnique.fr/~pilaud/} \author{\firstname{Viviane} \lastname{Pons}} \address%[VPo] {LRI, Univ. Paris-Sud - CNRS - Centrale Supelec - Univ. Paris-Saclay} \email{viviane.pons@lri.fr} \urladdr{https://www.lri.fr/~pons/} \thanks{VPi~was supported by the French ANR grant SC3A~(15\,CE40\,0004\,01). } % Key words and phrases: %\keywords{} %% Mathematical classification (2000) %% This will not be printed but can be useful for database search \subjclass{52B12, 16T05, 16T30} \begin{document} \theoremstyle{definition} % \newtheorem{example}[theorem]{Example} % \newtheorem{remark}[theorem]{Remark} %\makeatletter %\newtheorem{question}[cdrthm]{Question} %\makeatother %% Abstracts must be placed before \maketitle \begin{abstract} We introduce permutrees, a unified model for permutations, binary trees, Cambrian trees and binary sequences. On the combinatorial side, we study the rotation lattices on permutrees and their lattice homomorphisms, unifying the weak order, Tamari, Cambrian and boolean lattices and the classical maps between them. On the geometric side, we provide both the vertex and facet descriptions of a polytope realizing the rotation lattice, specializing to the permutahedron, the associahedra, and certain graphical zonotopes. On the algebraic side, we construct a Hopf algebra on permutrees containing the known Hopf algebraic structures on permutations, binary trees, Cambrian trees, and binary sequences. \end{abstract} \maketitle %\renewcommand{\up}[1]{\overline{#1}} \section{Introduction} \label{sec:intro} Binary words, binary trees, and permutations are three combinatorial families that share a common pattern linking their combinatorics to geometry and algebra. For example, the family of binary words of size $n$ is naturally endowed with the boolean lattice structure. Its Hasse diagram corresponds to the skeleton of an $n$-dimensional hypercube. Finally, all binary words index the basis of a Hopf algebra~\cite{GelfandKrobLascouxLeclercRetakhThibon} whose product is encoded in the boolean lattice (the product of two basis elements is given by a sum over an interval in the boolean lattice). We find a similar scheme for the other families which we summarize in \fref{fig:objectstable}. Recently, the family of Cambrian trees was also shown to share a similar pattern: Cambrian trees generalize the notion of binary trees, they are naturally endowed with N.~Reading's (type~$A$) Cambrian lattice structure~\cite{Reading-CambrianLattices}, they correspond to the vertices of C.~Hohlweg and C.~Lange's associahedra~\cite{HohlwegLange}, and they index the basis of G.~Chatel and V.~Pilaud's Cambrian~algebra~\cite{ChatelPilaud}. All these families are related through deep structural properties from all three aspects: combinatorics, geometry, and algebra. As lattices, the boolean lattice on binary sequences is both a sub- and a quotient lattice of the Tamari lattice on binary trees, itself a sub- and quotient lattice of the weak order on permutations~\cite{BjornerWachs, Reading-CambrianLattices}. As polytopes, the cube contains J.-L.~Loday's associahedron~\cite{Loday} which in turn contains the permutahedron~\cite[Lecture~0]{Ziegler}. And as algebras, the descent Hopf algebra on binary sequences of~\cite{GelfandKrobLascouxLeclercRetakhThibon} is a sub- and quotient Hopf algebra of J.-L.~Loday and M.~Ronco's Hopf algebra on binary trees~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees}, itself a sub- and quotient algebra of C.~Malvenuto and C.~Reutenauer's Hopf algebra on permutations~\cite{MalvenutoReutenauer, DuchampHivertThibon}. More generally, these exemples led to the development of necessary and sufficient conditions to obtain combinatorial Hopf algebras from lattice congruences of the weak order~\cite{Reading-HopfAlgebras} and from rewriting rules on monoids~\cite{HivertNovelliThibon-algebraBinarySearchTrees, Priez}. \begin{figure} %Fig. 1 %\input{objectIntroTable} \begin{tabular}{l|c|c|c} & permutations & binary trees & binary sequences \\ \hline & Weak order & Tamari lattice & boolean lattice \\ \rotatebox{90}{\hspace*{.1cm} Combinatorics} & \includegraphics[scale=.3]{figures/weakOrder.pdf} & \includegraphics[scale=.23]{figures/TamariLattice.pdf} & \includegraphics[scale=.35]{figures/booleanLattice.pdf} \\ & \cite{LascouxSchutzenberger} & \cite{TamariFestschrift} & \\ \hline & Permutahedron & Associahedron & Cube \\ \rotatebox{90}{\hspace*{.5cm} Geometry} & \includegraphics[scale=.4]{figures/permutahedron.pdf} & \includegraphics[scale=.3]{figures/associahedronLoday.pdf} & \includegraphics[scale=.35]{figures/parallelepiped.pdf} \\ & \cite[Lecture~0]{Ziegler} & \cite{Loday, HohlwegLange} & \\ \hline \rotatebox{90}{\hspace*{-.8cm} Algebra \;} & Malvenuto-Reutenauer & Loday-Ronco & Descent Hopf algebra \\ & algebra~\cite{MalvenutoReutenauer, DuchampHivertThibon} & algebra~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees} & \cite{GelfandKrobLascouxLeclercRetakhThibon} \\ & & & \\ \hline \end{tabular} \vspace{-.2cm} \caption{Summary of lattice structures, polytopes, and Hopf algebras on 3 families of combinatorial objects} \label{fig:objectstable} \end{figure} All these different aspects have been deeply studied but until now, these families have been considered as \defn{different} kind of objects. In this paper, we unify all these objects under a \defn{unique combinatorial definition} containing structural, geometric, and algebraic information. A given family type (binary words, binary trees, Cambrian trees, permutations) can then be encoded by a special \defn{decoration} on $[n]$. Our definition also allows for \defn{interpolations} between the known families: we obtain combinatorial objects that are structurally ``half'' binary trees and ``half'' permutations. This leads in particular to new lattice structures (see Figures \ref{fig:permutreeLattices} and~\ref{fig:fibersPermutreeCongruences}), to new polytopes (see Figures~\ref{fig:permutreehedron} and~\ref{fig:permutreehedra}) and to new combinatorial Hopf algebras (see Section~\ref{sec:permutreeHopfAlgebra}). We call our new objects \defn{permutrees}. They are labelled and oriented trees where each vertex can have one or two parents and one or two children, and with local rules around each vertex similar to the classical rule for binary trees (see Defintion~\ref{def:permutree}). We will explore in particular the following features of permutrees: \begin{description} \item[Combinatorics] We describe a natural insertion map from (decorated) permutations to permutrees similar to the binary tree insertion. The fibers of this map define a lattice congruence of the weak order. Therefore, there is an homomorphism from the weak order on permutations to the rotation lattice on permutrees. It specializes to the classical weak order on permutations~\cite{LascouxSchutzenberger}, the Tamari order on binary trees~\cite{TamariFestschrift}, the Cambrian lattice on Cambrian trees~\cite{Reading-CambrianLattices, ChatelPilaud}, and the boolean lattice on binary sequences. \item[Geometry] We provide the vertex and facet description of the permutreehedron, a polytope whose graph is the Hasse diagram of the rotation lattice on permutrees. The permutreehedron is obtained by deleting facets from the classical permutahedron. It specializes to the classical permutahedron~\cite[Lecture~0]{Ziegler}, to J.-L.~Loday's and C.~Hohlweg and C.~Lange's associahedra~\cite{Loday, HohlwegLange}, and to the parallelepiped generated by~$\set{\b{e}_{i+1}-\b{e}_i}{i \in [n-1]}$. \item[Algebra] We construct a Hopf algebra on permutrees and describe the product and coproduct in this algebra and its dual in terms of cut and paste operations on permutrees. It contains as subalgebras C.~Malvenuto and C.~Reutenauer's algebra on permutations~\cite{MalvenutoReutenauer, DuchampHivertThibon}, J.-L.~Loday and M.~Ronco's algebra on binary trees~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees}, G.~Chatel and V.~Pilaud's algebra on Cambrian trees~\cite{ChatelPilaud}, and I.~Gelfand, D.~Krob, A.~Lascoux, B.~Leclerc, V.~S. Retakh, and J.-Y.~Thibon's algebra on binary sequences~\cite{GelfandKrobLascouxLeclercRetakhThibon}. \end{description} All our constructions and proofs are generalizations of previous work, in particular~\cite{ChatelPilaud} from which we borrow the general structure of the paper. However, we believe that our main contribution is the very \defn{unified definition} of permutrees which leads to natural constructions, simple proofs, and new objects in algebra and geometry. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Permutrees} \label{sec:permutrees} %%%%%%%%%%%%%%% \subsection{Permutrees and leveled permutrees} \label{subsec:permutrees} This paper focuses on the following family of trees. \begin{definition} \label{def:permutree} A \defn{permutree} is a directed tree~$\tree$ with vertex set~$\ground$ endowed with a bijective vertex labeling $p : \ground \to [n]$ such that for each vertex~$v \in \ground$, \begin{enumerate}[(i)] \item $v$ has one or two parents (outgoing neighbors), and one or two children (incoming neighbors); \item if $v$ has two parents (resp.~children), then all labels in the left ancestor (resp. descendant) subtree of~$v$ are smaller than~$p(v)$ while all labels in the right ancestor (resp.~descendant) subtree of~$v$ are larger than~$p(v)$. \end{enumerate} The \defn{decoration} of a permutree is the $n$-tuple~$\decoration(\tree) \in \Decorations^n$ defined by \[ \decoration(\tree)_{p(v)} = \begin{cases} \noneCirc{} & \text{if $v$ has one parent and one child,} \\ \downCirc{} & \text{if $v$ has one parent and two children,} \\ \upCirc{} & \text{if $v$ has two parents and one child,} \\ \upDownCirc{} & \text{if $v$ has two parents and two children,} \end{cases} \] for all~$v \in \ground$. Equivalently, we record the \defn{up} labels~${\decoration^\vee(\tree) = \set{i \in [n]}{\decoration(\tree)_i \in \{\upCirc{},\upDownCirc{}\}}}$ of vertices with two parents and the \defn{down} labels~$\decoration_\wedge(\tree) = \set{i \in [n]}{\decoration(\tree)_i \in \{\downCirc{},\upDownCirc{}\}}$ of vertices with two children. If~$\decoration(\tree) = \decoration$, we say that $\tree$ is a \defn{$\decoration$-permutree}. We denote by~$\Permutrees(\decoration)$ the set of $\decoration$-permutrees, by~$\Permutrees(n) = \bigsqcup_{\decoration \in \Decorations^n} \Permutrees(\decoration)$ the set of all permutrees on~$n$ vertices, and by~$\Permutrees \eqdef \bigsqcup_{n \in \N} \Permutrees(n)$ the set of all permutrees. \end{definition} \begin{definition} \label{def:increasingTree} An \defn{increasing tree} is a directed tree~$\tree$ with vertex set~$\ground$ endowed with a bijective vertex labeling~$q : \ground \to [n]$ such that~$v \to w$ in~$\tree$ implies~$q(v) < q(w)$. \end{definition} \begin{definition} \label{def:labeledPermutree} A \defn{leveled permutree} is a directed tree~$\tree$ with vertex set~$\ground$ endowed with two bijective vertex labelings~${p,q : V \to [n]}$ which respectively define a permutree and an increasing tree. In other words, a leveled permutree is a permutree endowed with a linear extension of its transitive closure (given by the inverse of the labeling~$q$). \end{definition} \begin{figure}[H]%%Fig 2 \centerline{\includegraphics[scale=.85]{leveledPermutree}} \caption{A permutree (left), an increasing tree (middle), and a leveled permutree (right). The decoration is \downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}\noneCirc{}\downCirc{}\upCirc{}.} \label{fig:leveledPermutree} \end{figure} \fref{fig:leveledPermutree} provides examples of a permutree, an increasing tree, and a leveled permutree. We use the following conventions in all figures of this paper: \begin{enumerate}[(i)] \item All edges are oriented bottom-up --- we can thus omit the edge orientation; \item For a permutree, the vertices appear from left to right in the order given by the labeling~$p$ --- we can thus omit the vertex labeling; \item For an increasing tree, the vertices appear from bottom to top in the order given by the labeling~$q$ --- we can thus omit the vertex labeling; \item In particular, for a leveled permutree with vertex labelings~$p,q : \ground \to [n]$ as in Definition~\ref{def:labeledPermutree}, each vertex~$v$ appears at position~$\big( p(v),q(v) \big)$ --- we can thus omit both labelings; \item In all our trees, we decorate the vertices with \noneCirc{}, \downCirc{}, \upCirc{}, or \upDownCirc{} depending on their number of parents and children, following the natural visual convention of Definition~\ref{def:permutree}; \item In a permutree, we often draw a vertical red wall below \downCirc{} and \upDownCirc{} vertices and above \upCirc{} and \upDownCirc{} vertices to mark the separation between the left and right descendant or ancestor subtrees of these vertices. \end{enumerate} \begin{example} \label{exm:permutreesSpecificDecorations} For specific decorations, permutrees specialize to classical combinatorial families: \begin{enumerate}[(i)] \item Permutrees with decoration~$\noneCirc{}^n$ are in bijection with permutations of~$[n]$. Indeed, such a permutree is just a path of vertices labelled by~$[n]$. \item Permutrees with decoration~$\downCirc{}^n$ are in bijection with rooted planar binary trees on $n$ vertices. Indeed, such a permutree has a structure of rooted planar binary tree, and its labeling~${p : \ground \to [n]}$ is just the inorder labeling which can be recovered from the binary tree (inductively label each vertex after its left subtree and before its right subtree). \item Permutrees with decoration in~$\{\downCirc{}, \upCirc{}\}^n$ are precisely Cambrian trees~\cite{ChatelPilaud}. \item Permutrees with decoration~$\upDownCirc{}^n$ are in bijection with binary sequences with $n-1$ letters. Indeed, such a tree can be transformed to a sequence of letters~$u$ or~$d$ whose $i$th letter records whether the vertex~$i$ is a child of the vertex~$i+1$ or the opposite. \item Permutrees with decoration in~$\{\noneCirc{}, \upDownCirc{}\}^n$ are in bijection with acyclic orientations of the graph with vertices~$[n]$ and an edge between any two positions separated only by~\noneCirc{}'s in the decoration. \end{enumerate} \fref{fig:permutationsBinaryTreesCambrianTreesBinarySequences} illustrates these families represented as permutrees. The goal of this paper is to propose a uniform treatment of all these families and of the lattices, morphisms, polytopes, and Hopf algebras associated to them. % \begin{figure}[H]%%Fig 3 \centerline{\includegraphics[scale=.7]{permutationsBinaryTreesCambrianTreesBinarySequences}} \caption{Leveled permutrees corresponding to a permutation (left), a leveled binary tree (middle left), a leveled Cambrian tree (middle right), and a leveled binary sequence (right).} \label{fig:permutationsBinaryTreesCambrianTreesBinarySequences} \end{figure} % \end{example} \begin{remark} \label{rem:symmetrees} There are two natural operations on permutrees, that we call \defn{symmetrees}, given by horizontal and vertical reflections. Denote by~$\horizontalSymmetry{\tree}$ (resp.~$\verticalSymmetry{\tree}$) the permutree obtained from~$\tree$ by a horizontal (resp.~vertical) reflection. Its decoration is then~$\decoration(\horizontalSymmetry{\tree}) = \horizontalSymmetry{\decoration(\tree)}$ (resp.~${\decoration(\verticalSymmetry{\tree}) = \verticalSymmetry{\decoration(\tree)}}$), where~$\horizontalSymmetry{\decoration}$ (resp.~$\verticalSymmetry{\decoration}$) denotes the decoration obtained from~$\decoration$ by a mirror image (resp.~by interverting~\downCirc{} and~\upCirc{} decorations). \end{remark} \begin{remark} \label{rem:bijectionsPermutrees} Observe that the decorations of the leftmost and rightmost vertices of a permutree are irrelevant. Namely, consider two decorations~$\decoration, \decoration' \in \Decorations^n$ such that~$\decoration'$ is obtained from~$\decoration$ by forcing~$\decoration'_1 = \decoration'_n = \noneCirc{}$. Then there is a bijection from $\decoration$-permutrees to $\decoration'$-permutrees which consists in deleting the left (resp.~right) incoming and outgoing edges~---~if any~---~of the leftmost (resp.~rightmost) vertex of a $\decoration$-permutree. See \fref{fig:bijectionsPermutrees}\,(left). When~$\decoration = \decoration'\upDownCirc{}\,\decoration''$, there is a bijection between~$\Permutrees(\decoration)$ and~$\Permutrees(\decoration'\noneCirc{}) \times \Permutrees(\noneCirc{}\decoration'')$. We send a $\decoration$-permutree~$\tree$ to the pair of permutrees~$(\tree', \tree'')$ where~$\tree'$ (resp.~$\tree''$) is the $(\decoration'\noneCirc{})$-permutree (resp.~the $(\noneCirc{}\,\decoration'')$-permutree) on the left (resp.~right) of the~$(|\decoration'|+1)$th vertex of~$\tree$. Conversely, we send a pair of permutrees~$(\tree', \tree'')$ to the $\decoration$-permutree~$\tree$ obtained by merging the rightmost vertex of~$\tree'$ with the leftmost vertex of~$\tree''$. See \fref{fig:bijectionsPermutrees}\,(right). \begin{figure}[H]%%Fig 4 \centerline{\includegraphics[scale=.7]{bijectionsPermutrees}} \caption{Some bijections between permutrees: the leftmost and rightmost decorations do not matter (left), and a decoration~$\upDownCirc{}$ yields a product (right).} \label{fig:bijectionsPermutrees} \end{figure} \end{remark} \begin{remark} \label{rem:234angulations} Permutrees can as well be seen as dual trees of certain $\{2,3,4\}$-angulations. We keep the presentation informal as we only need the intuition of the construction in this paper. For a given decoration~$\decoration \in \Decorations^n$, we construct a collection~$\b{P}_\decoration$ of points in the plane as follows. We first fix~$\b{p}_0 = (0,0)$ and~$\b{p}_{n+1} = (n+1,0)$ and denote by~$C$ the circle with diameter~$\b{p}_0\b{p}_{n+1}$. Then for each~$i \in [n]$, we a place at abscissa~$i$ a point~$\b{p}_i^0$ on~$\b{p}_0\b{p}_{n+1}$ if~$\decoration_i = \noneCirc{}$, a point~$\b{p}_i^-$ on the circle~$C$ and below~$\b{p}_0\b{p}_{n+1}$ if~$\decoration_i \in \{\downCirc{}, \upDownCirc{}\}$, and a point~$\b{p}_i^+$ on the circle~$C$ and above~$\b{p}_0\b{p}_{n+1}$ if~$\decoration_i \in \{\upCirc{}, \upDownCirc{}\}$. Note that when~$\decoration_i = \upDownCirc{}$, we have both~$\b{p}_i^-$ and~$\b{p}_i^+$ at abscissa~$i$. \fref{fig:234angulation} shows the point set~$\b{P}_\decoration$ for~$\decoration = \downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}\noneCirc{}\downCirc{}\upCirc{}$. An \defn{arc} in~$\b{P}_\decoration$ is an abscissa monotone curve connecting two external points of~$\b{P}_\decoration$, not passing through any other point of~$\b{P}_\decoration$, and not crossing the vertical line at abscissa~$i$ if~$\decoration_i = \upDownCirc{}$. Arcs are considered up to isotopy in~$\R^2 \ssm \b{P}_\decoration$. In particular, we can assume that the arcs joining two consecutive points on the boundary of the convex hull of~$\b{P}_\decoration$ are straight. We call \mbox{\defn{$\{2,3,4\}$-angulation}} of~$\b{P}_\decoration$ a maximal set of non-crossing arcs in~$\b{P}_\decoration$. An example is given in \fref{fig:234angulation}. As observed in this picture, one can check that a $\{2,3,4\}$-angulation decomposes the convex hull of~$\b{P}_\decoration$ into diangles, triangles and quadrangles. In fact, for each~$j \in [n]$, there is one diangle around~$\b{p}_j^0$ if~$\decoration_j = \noneCirc{}$, one triangle~$\{\b{p}_i^\pm, \b{p}_j^\pm, \b{p}_k^\pm\}$ with~$i < j < k$ if~$\decoration_j \in \{\downCirc{}, \upCirc{}\}$, and one quadrangle~$\{\b{p}_i^\pm, \b{p}_j^-, \b{p}_j^+, \b{p}_k^\pm\}$ with~$i < j < k$ if~$\decoration_j = \upDownCirc{}$. We associate to a $\{2,3,4\}$-angulation of~$\b{P}_\decoration$ its dual permutree with \begin{itemize} \item a vertex in each $\{2,3,4\}$-angle: the $j$th vertex is a vertex~\noneCirc{} in the diangle enclosing~$\b{p}_j^0$ if~$\decoration_j = \noneCirc{}$, a vertex~\upCirc{} (resp.~\upCirc{}) in the triangle~$\{\b{p}_i^\pm, \b{p}_j^\pm, \b{p}_k^\pm\}$ with $i < j < k$ if~$\decoration_j = \downCirc{}$ (resp.~$\upCirc{}$), and a vertex~\upDownCirc{} in the quadrangle~$\{\b{p}_i^\pm, \b{p}_j^-, \b{p}_j^+, \b{p}_k^\pm\}$ with~${i < j < k}$ if~$\decoration_j = \upDownCirc{}$, \item an edge for each arc: for each arc~$\alpha$, there is an edge from the $\{2,3,4\}$-angle adjacent to~$\alpha$ and below~$\alpha$ to the $\{2,3,4\}$-angle adjacent to~$\alpha$ and above~$\alpha$. \end{itemize} \begin{figure} %Fig 5 \centerline{\includegraphics[scale=.7]{234angulation}} \caption{Permutrees (left) and $\{2,3,4\}$-angulations (right) are dual to each other.} \label{fig:234angulation} \end{figure} \end{remark} %%%%%%%%%%%%%%% \subsection{Permutree correspondence} \label{subsec:correspondence} In this section, we present a correspondence between the permutations of~$\fS_n$ and the leveled $\decoration$-permutrees for any given decoration~$\decoration \in \Decorations$. This correspondence defines a surjection from the permutations of~$\fS_n$ to the $\decoration$-permutrees by forgetting the increasing labeling. This surjection will be a special case of the surjections described in Section~\ref{subsec:decorationRefinements}. We follow here the presentation of the Cambrian correspondence in~\cite{ChatelPilaud}. We represent graphically a permutation~$\tau \in \fS_n$ by the $(n \times n)$-table, with rows labelled by positions from bottom to top and columns labelled by values from left to right, and with a dot at row~$i$ and column~$\tau(i)$ for all~$i \in [n]$. (This unusual choice of orientation is necessary to fit later with the existing constructions of~\cite{LodayRonco, HivertNovelliThibon-algebraBinarySearchTrees, ChatelPilaud}.) A \defn{decorated permutation} is a permutation table where each dot is decorated by~\noneCirc{}, \downCirc{}, \upCirc{},~or~\upDownCirc{}. See the top left corner of \fref{fig:insertionAlgorithm}. We could equivalently think of a permutation where the positions or the values receive a decoration, but it will be useful later to switch the decoration from positions to values. The \defn{p-decoration} (resp.~\defn{v-decoration}) of a decorated permutation~$\tau$ is the sequence~$\pdecoration(\tau)$ (resp.~$\vdecoration(\tau)$) of decorations of~$\tau$ ordered by positions from bottom to top (resp.~by values from left to right). For a permutation~$\tau \in \fS_n$ and a decoration~$\decoration \in \Decorations^n$, we denote by~$\tau_\decoration$ (resp.~by~$\tau^\decoration$) the permutation~$\tau$ with p-decoration~$\pdecoration(\tau_\decoration) = \decoration$ (resp.~with \mbox{v-decoration}~$\vdecoration(\tau^\decoration) = \decoration$). We let~$\fS_\decoration \eqdef \set{\tau_\decoration}{\tau \in \fS_n}$ and~$\fS^\decoration \eqdef \set{\tau^\decoration}{\tau \in \fS_n}$. Finally, we let \[ \fS_{\Decorations} \eqdef \bigsqcup_{\substack{n \in \N \\ \decoration \in \Decorations^n}} \fS_\decoration = \bigsqcup_{\substack{n \in \N \\ \decoration \in \Decorations^n}} \fS^\decoration \] denote the set of all decorated permutations. In concrete examples, we underline the down positions/values (those decorated by~\downCirc{} or~\upDownCirc{}) while we overline the up positions/values (those decorated by~\upCirc{} or~\upDownCirc{}): for example, $\up{2}\up{7}5\down{1}3\updown{4}\down{6}$ is the decorated permutation represented on the top left corner of \fref{fig:insertionAlgorithm}, where~${\tau = [2,7,5,1,3,4,6]}$, ${\pdecoration = \upCirc{}\upCirc{}\noneCirc{}\downCirc{}\noneCirc{}\upDownCirc{}\downCirc{}}$ and~${\vdecoration = \downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}\noneCirc{}\downCirc{}\upCirc{}}$. The insertion algorithm transforms a decorated permutation~$\tau$ to a leveled permutree~$\permutreeCorresp(\tau)$. As a preprocessing, we represent the table of~$\tau$ (with decorated dots in positions~$(\tau(i),i)$ for~$i \in [n]$) and draw a vertical red wall below the down vertices and above the up vertices. These walls separate the table into regions. Note that the number of children (resp. parents) expected at each vertex is the number of regions visible below (resp. above) this vertex. We then sweep the table from bottom to top (thus reading the permutation~$\tau$ from left to right) as follows. The procedure starts with an incoming strand in between any two consecutive down values. At each step, we sweep the next vertex and proceed to the following operations depending on its decoration: \begin{enumerate}[(i)] \item a vertex decorated by \noneCirc{} or \upCirc{} catches the only incoming strands it sees, while a vertex decorated by \downCirc{} or \upDownCirc{} connects the two incoming strands just to its left and to its~right, \item a vertex decorated by \noneCirc{} or \downCirc{} creates a unique outgoing strand, while a vertex decorated by \upCirc{} or \upDownCirc{} creates two outgoing strands just to its left and to its right. \end{enumerate} The procedure finishes with an outgoing strand in between any two consecutive up values. See \fref{fig:insertionAlgorithm}. \begin{figure}[H]%%Fig 6 \centerline{\includegraphics[scale=.65]{insertionAlgorithm}} \caption{The insertion algorithm on the decorated permutation~$\up{2}\up{7}5\down{1}3\updown{4}\down{6}$.} \label{fig:insertionAlgorithm} \end{figure} \begin{proposition} \label{prop:permutreeCorrespondence} The map~$\permutreeCorresp$ is a bijection from $\decoration$-decorated permutations to leveled $\decoration$-permutrees. \end{proposition} \begin{proof} First, we need to prove that the map~$\permutreeCorresp$ is well-defined. This relies on the following invariant of the sweeping algorithm: along the sweeping line, there is precisely one strand in each of the intervals separated by the walls. Indeed, this invariant holds when we start the procedure and is preserved when we sweep any kind of vertex. Therefore, the sweeping algorithm creates a graph whose vertices are the decorated dots of the permutation table together with the initial and final positions of the strands and where no edge crosses a red wall. It follows that this graph is a tree (a cycle would force an edge to cross a red wall), and it is a leveled permutree (the walls separate left and right ancestor or descendant subtrees). To prove that~$\permutreeCorresp$ is bijective, we already observed that a leveled permutree~$\tree$ is a permutree endowed with a linear extension~$\tau$. We can consider that~$\tau$ is decorated by the decorations of the vertices of~$\tree$. Finally, one checks easily that when inserting the decorated permutation~$\tau$, the resulting leveled permutree is~$\permutreeCorresp(\tau) = \tree$. \end{proof} For a decorated permutation~$\tau$, we denote by~$\PSymbol(\tau)$ the permutree obtained by forgetting the increasing labeling in~$\permutreeCorresp(\tau)$ and by~$\QSymbol(\tau)$ the increasing tree obtained by forgetting the permutree labeling in~$\permutreeCorresp(\tau)$. These trees should be thought of as the insertion and recording trees of the permutree correspondence, in analogy to the insertion and recording tableaux in the Robinson-Schensted correspondence~\cite{Schensted}. The same analogy was already done for the sylvester correspondence~\cite{HivertNovelliThibon-algebraBinarySearchTrees} and the Cambrian correspondence~\cite{ChatelPilaud}. The following statement was already observed along the previous proof. \begin{proposition} \label{prop:fibersPSymbol} The decorated permutations~$\tau \in \fS^\decoration$ such that~$\PSymbol(\tau) = \tree$ are precisely the linear extensions of (the transitive closure of) the permutree~$\tree$. \end{proposition} \begin{example} \label{exm:insertionSpecificDecorations} Following Example~\ref{exm:permutreesSpecificDecorations}, the $\decoration$-permutree~$\PSymbol(\tau)$ is: \begin{enumerate}[(i)] \item a path with vertices labelled by~$\tau$ for~$\decoration = \noneCirc{}^n$, \item the binary tree obtained by successive insertions (in a binary search tree) of the values of~$\tau$ read from right to left for~$\decoration = \downCirc{}^n$, \item the Cambrian tree obtained by the insertion algorithm of~\cite{ChatelPilaud} for~${\decoration \in \{\downCirc{}, \upCirc{}\}^n}$, \item a permutree recording the recoils of~$\tau$ for~$\decoration = \upDownCirc{}^n$. Namely, the vertex~$i$ is below the vertex~$i+1$ in~$\PSymbol(\tau)$ if $\tau^{-1}(i) < \tau^{-1}(i+1)$, and above otherwise. \end{enumerate} For example, the leveled permutrees of \fref{fig:permutationsBinaryTreesCambrianTreesBinarySequences} were all obtained by inserting the permutation~$2751346$ with different decorations. \end{example} %%%%%%%%%%%%%%% \subsection{Permutree congruence} \label{subsec:congruence} In this section, we characterize the decorated permutations which give the same $\PSymbol$-symbol in terms of a congruence relation defined by a rewriting rule. We note that this is just a straightforward extension of the definitions of the sylvester congruence by F.~Hivert, J.-C.~Novelli and J.-Y.~Thibon~\cite{HivertNovelliThibon-algebraBinarySearchTrees} and of the Cambrian congruence of N.~Reading~\cite{Reading-CambrianLattices}. \begin{definition} \label{def:permutreeCongruence} For a decoration~$\decoration \in \Decorations^n$, the \defn{$\decoration$-permutree congruence} is the equivalence relation on~$\fS^\decoration$ defined as the transitive closure of the rewriting rules \[ \begin{array}{ll} UacVbW \equiv_\decoration UcaVbW & \text{if } a < b < c \text{ and } \decoration_b = \downCirc{} \text{ or } \upDownCirc{}, \\ UbVacW \equiv_\decoration UbVcaW & \text{if } a < b < c \text{ and } \decoration_b = \upCirc{} \text{ or } \upDownCirc{}, \end{array} \] where~$a,b,c$ are elements of~$[n]$ while~$U,V,W$ are words on~$[n]$. Note that the decorations of~$a$ and~$c$ do not matter, only that of~$b$ which we call the \defn{witness} of the rewriting rule. The \defn{permutree congruence} is the equivalence relation on all decorated permutations~$\fS_{\Decorations}$ obtained as the union of all $\decoration$-permutree congruences: \[ \equiv \; \eqdef \bigsqcup_{\substack{n \in \N \\ \decoration \in \Decorations^n}} \!\! \equiv_\decoration. \] \end{definition} \begin{proposition} \label{prop:permutreeCongruenceClass} Two decorated permutations~$\tau, \tau' \in \fS_{\Decorations}$ are permutree congruent if and only if they have the same $\PSymbol$-symbol: \[ \tau \equiv \tau' \iff \PSymbol(\tau) = \PSymbol(\tau'). \] \end{proposition} \begin{proof} It boils down to observe that two consecutive vertices~$a,c$ in a linear extension~$\tau$ of a \mbox{$\decoration$-permu}\-tree~$\tree$ can be switched while preserving a linear extension~$\tau'$ of~$\tree$ precisely when they belong to distinct ancestor or descendant subtrees of a vertex~$b$ of~$\tree$. It follows that the vertices~$a,c$ lie on either sides of~$b$ so that we have~$a < b < c$. If~$\decoration_b = \downCirc{}$ or~$\upDownCirc{}$ and~$a,c$ appear before~$b$ in~$\tau$, then they belong to distinct descendant subtrees of~$b$ and~$\tau = UacVbW$ can be switched to~$\tau' = UcaVbW$. If~$\decoration_b = \upCirc{}$ or~$\upDownCirc{}$ and~$a,c$ appear after~$b$ in~$\tau$, then they belong to distinct ancestor subtrees of~$b$ and~$\tau = UbVacW$ can be switched to~$\tau' = UbVcaW$. \end{proof} Recall that the (right) \defn{weak order} on~$\fS_n$ is defined as the inclusion order of (right) inversions, where a (right) \defn{inversion} of~$\tau \in \fS_n$ is a pair of values~$i < j$ such that~${\tau^{-1}(i) > \tau^{-1}(j)}$. This order is a lattice with minimal element~$[1, 2, \dots, n-1, n]$ and maximal element~$[n, n-1, \dots, 2, 1]$. A \defn{lattice congruence} of a lattice~$(L, \le, \meet, \join)$ is an equivalence relation~$\equiv$ on~$L$ which respects the meet and join operations: $x \equiv x'$ and~$y \equiv y'$ implies $x \meet y \equiv x' \meet y'$ and~$x \join y \equiv x' \join y'$ for all~$x, x', y, y' \in L$. For finite lattices, it is equivalent to require that equivalence classes of~$\equiv$ are intervals of~$L$ and that the maps~$\projDown$ and~$\projUp$ respectively sending an element to the bottom and top elements of its equivalence class are order preserving. The \defn{quotient} of~$L$ modulo the congruence~$\equiv$ is the lattice~$L/{\equiv}$ whose elements are the equivalence classes of~$L$ under~$\equiv$, and where for any two classes~$X, Y \in L/{\equiv}$, the order is given by~$X \le Y$ if and only if there exist representatives~$x \in X$ and~$y \in Y$ such that~$x \le y$, and the meet (resp.~join) is given by~$X \meet Y = x \meet y$ (resp.~$X \join Y = x \join y$) for any representatives~$x \in X$ and~$y \in Y$. N.~Reading deeply studied the lattice congruences of the weak order, see in particular~\cite{Reading-latticeCongruences, Reading-arcDiagrams}. Using his technology, in particular that of~\cite{Reading-arcDiagrams}, we will prove in the next section that our permutree congruences are as well lattice congruences of the weak order. \begin{proposition} \label{prop:weakOrderCongruence} For any decoration~$\decoration \in \Decorations^n$, the $\decoration$-permutree congruence~$\equiv_\decoration$ is a lattice congruence of the weak order on~$\fS^\decoration$. \end{proposition} \begin{corollary} \label{coro:patternAvoidingPermutations} The $\decoration$-permutree congruence classes are intervals of the weak order on~$\fS_n$. In particular, the following sets are in bijection: \begin{enumerate}[(i)] \item permutrees with decoration~$\decoration$, \item $\decoration$-permutree congruence classes, \item permutations of~$\fS_n$ that avoid the patterns~$ac \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ac$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$ (maximums of $\decoration$-permutree congruence classes), \item permutations of~$\fS_n$ that avoid the patterns~$ca \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ca$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$ (minimums of $\decoration$-permutree congruence classes). \end{enumerate} \end{corollary} \begin{example} \label{exm:congruencesSpecificDecorations} Following Example~\ref{exm:permutreesSpecificDecorations}, the $\decoration$-permutree congruence~$\equiv$ is: \begin{enumerate}[(i)] \item the trivial congruence for~$\decoration = \noneCirc{}^n$, \item the sylvester congruence~\cite{HivertNovelliThibon-algebraBinarySearchTrees} for~$\decoration = \downCirc{}^n$, \item the Cambrian congruence~\cite{Reading-latticeCongruences, Reading-CambrianLattices, ChatelPilaud} for~$\decoration \in \{\downCirc{}, \upCirc{}\}^n$, \item the hypoplactic congruence~\cite{KrobThibon-NCSF4, Novelli-hypoplactic} ($\sigma \equiv \tau$ if and only if $\sigma$ and~$\tau$ have the same descent sets) for~$\decoration = \upDownCirc{}^n$. \end{enumerate} \end{example} \begin{remark} In~\cite{Reading-latticeCongruences}, N.~Reading defines a notion of homogeneous congruences of the weak order. For example, the parabolic congruences cover all homogeneous degree $1$ congruences. It turns out that the permutree congruences cover all homogeneous degree $2$ congruences. In other words, the permutree congruences are precisely the lattice congruences obtained by contracting a subset of side edges of the bottom hexagonal faces of the weak order together with all edges forced by these contractions. For example, as illustrated in \fref{fig:fibersPermutreeCongruences}, for each~$\delta \in \Decorations^4$, the $\delta$-permutree congruence is the finest congruence which contracts the edges \begin{gather*} [1324, 3124] \text{ if } \delta_2 \in \{\downCirc, \upDownCirc\}, \qquad\qquad [2134, 2314] \text{ if } \delta_2 \in \{\upCirc, \upDownCirc\}, \\ [1243, 1423] \text{ if } \delta_3 \in \{\downCirc, \upDownCirc\}, \qquad\qquad [1324, 1342] \text{ if } \delta_3 \in \{\upCirc, \upDownCirc\}. \end{gather*} \end{remark} %%%%%%%%%%%%%%% \subsection{Arc diagrams} \label{subsec:arcDiagrams} We now interpret the permutree congruence in terms of the arc diagrams of N.~Reading~\cite{Reading-arcDiagrams}. We first briefly recall some definitions adapted to suit better our purposes (in contrast to the presentation of~\cite{Reading-arcDiagrams}, our arc diagrams are horizontal to fit our conventions). Consider the $n$ points~$\{\b{q}_1, \dots, \b{q}_n\}$ where~$\b{q}_i = (i,0)$. An \defn{arc diagram} is a set of abscissa monotone curves (called \defn{arcs}) joining two points~$\b{q}_i$ and~$\b{q}_j$, not passing through any other point~$\b{q}_k$, and such that: \begin{itemize} \item no two arcs intersect except possibly at their endpoints, \item no two arcs share the same left endpoint or the same right endpoint (but the right endpoint of an arc may be the left endpoint of another arc). \end{itemize} Two arcs are equivalent if they have the same endpoints~$\b{q}_i, \b{q}_j$ and pass above or below the same points~$\b{q}_k$ for~$i < k < j$, and two arc diagrams are equivalent if their arcs are pairwise equivalent. In other words, arc diagrams are considered up to isotopy. Denote by~$\arcDiagrams_n$ the set of arc diagrams on~$n$ points. There are two similar maps~$\asc$ and~$\desc$ from~$\fS_n$ to~$\arcDiagrams_n$: for a permutation~${\tau \in \fS_n}$, draw the table with a dot at row~$i$ and column~$\tau(i)$ for each~$i \in [n]$, trace the segments joining two consecutive dots corresponding to ascents (resp.~descents) of~$\tau$, let the points and segments fall down to the horizontal line, allowing the segments connecting ascents (resp.~descents) to curve but not to pass through any dot, and call the resulting arc diagram~$\asc(\tau)$ (resp.~$\desc(\tau)$). See \fref{fig:arcDiagrams}\,(left) for an illustration. It is proved in~\cite{Reading-arcDiagrams} that~$\asc$ and~$\desc$ define bijections from~$\fS_n$ to~$\arcDiagrams_n$. Consider now a decoration~$\decoration \in \Decorations^n$. Draw a vertical wall below each point~$\b{q}_i$ with~$\decoration_i \in \{\downCirc{}, \upDownCirc\}$ and above each point~$\b{q}_i$ with~$\decoration_i \in \{\upCirc{}, \upDownCirc\}$. We denote by~$U_\decoration$ the set of arcs which do not cross any of these walls. Note that this is very similar to~\cite[Example~4.9]{Reading-arcDiagrams} where each point~$\b{q}_i$ is incident to precisely one wall. The following lemma is immediate. \begin{lemma} \label{lem:arcDiagrams} For any~$\tau \in \fS_n$, the arc diagram~$\asc(\tau)$ (resp.~$\desc(\tau)$) uses only arcs~in~$U_\decoration$ if and only if~$\tau$ avoids the patterns~$ac \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ac$ with~${\decoration_b \in \{\upCirc{}, \upDownCirc{}\}}$ (resp.~$ca \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ca$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$). \end{lemma} Consider now two arcs~$\alpha$ with endpoints~$\b{q}_i,\b{q}_j$, and~$\beta$ with endpoints~$\b{q}_k,\b{q}_\ell$. Then~$\alpha$ is a \defn{subarc} of~$\beta$ if~$k \le i \le j \le \ell$ and~$\alpha$ and~$\beta$ pass above or below the same points~$\b{q}_m$ for~$i < m < j$. Consider now a subset~$U$ of all possible arcs which is closed by subarcs. Denote by~$\arcDiagrams_n(U)$ the set of arc diagrams consisting only of arcs of~$U$. It is then proved in~\cite{Reading-arcDiagrams} that~$\asc^{-1}(\arcDiagrams_n(U))$ (resp.~$\desc^{-1}(\arcDiagrams_n(U))$) is the set of bottom (resp.~top) elements of the classes of a lattice congruence~$\equiv_U$ of the weak order. We therefore obtain the proof of Proposition~\ref{prop:weakOrderCongruence}. \begin{figure}[t]%%Fig 7 \centerline{\includegraphics[scale=.7]{arcDiagrams}} \caption{The arc diagrams~$\asc(\tau)$ (green, up) and~$\desc(\tau)$ (pink, down) associated to the permutation~$\tau = 2537146$ (left) and the arc diagrams~$\asc(\tree)$ (green, up) and $\desc(\tree)$ (pink, down) associated to a permutree~$\tree$ (right).} \label{fig:arcDiagrams} \end{figure} \begin{proof}[Proof of Proposition~\ref{prop:weakOrderCongruence}] For any decoration~$\decoration \in \Decorations^n$, the set~$U_\decoration$ of arcs not crossing any wall is clearly closed by subarcs. It follows that~$\asc^{-1}(\arcDiagrams_n(U_\decoration))$ (resp.~$\desc^{-1}(\arcDiagrams_n(U_\decoration))$) is the set of bottom (resp.~top) elements of the classes of a lattice congruence~$\equiv_{U_\decoration}$ of the weak order. But Lemma~\ref{lem:arcDiagrams} ensures that~$\asc^{-1}(\arcDiagrams_n(U_\decoration))$ (resp.~$\desc^{-1}(\arcDiagrams_n(U_\decoration))$) are precisely the bottom (resp.~top) elements of the classes of the permutree congruence~$\equiv_\decoration$. The two congruences~$\equiv_{U_\decoration}$ and~$\equiv_\decoration$ thus coincide which proves that~$\equiv_\decoration$ is a lattice congruence of the weak order. \end{proof} We conclude this section with a brief comparison between permutrees and arc diagrams. Consider a permutree~$\tree$, delete all its leaves, and let its vertices fall down to the horizontal axis, allowing the edges to curve but not to pass through any vertex. The resulting set of oriented arcs can be decomposed into the set~$\asc(\tree)$ of increasing arcs oriented from~$i$ to~$j$ with~$i < j$ and the set~$\desc(\tree)$ of decreasing arcs oriented from~$j$ to~$i$ with~$i < j$. The following observation, left to the reader, is illustrated in \fref{fig:arcDiagrams}\,(right). \begin{proposition} The set~$\asc(T)$ is the arc diagram~$\asc(\tau)$ of the maximal linear extension~$\tau$ of~$\tree$ while the set~$\desc(\tree)$ is the arc diagram~$\desc(\sigma)$ of the minimal linear extension~$\sigma$ of~$\tree$. \end{proposition} %%%%%%%%%%%%%%% \subsection{Numerology} \label{subsec:numerology} In this section, we discuss enumerative properties of permutrees. For~$\decoration \in \Decorations^n$, we call \defn{factorial-Catalan number} the number~$\factCatalan{\decoration}$ of $\decoration$-per\-mutrees. The values of~$\factCatalan{\decoration}$ for~$|\decoration| \in \{3,4,5,6\}$ are reported in Table~\ref{table:factorialCatalan}. To evaluate these numbers, we proceed in two steps: we first show that the number of $\decoration$-permutrees only depends on the positions of the \noneCirc{} and \upDownCirc{} in~$\decoration$, and then give summation formulas for factorial-Catalan numbers~$\factCatalan{\decoration}$ for $\decoration \in \{\noneCirc{}, \downCirc{}, \upDownCirc{}\}^n$. {\small \begin{table}[t] \centerline{ $\begin{array}[t]{c|ccc} & {\cdot}{\cdot}{\cdot} & {\cdot}\noneCirc{}{\cdot} \\ \hline {\cdot}{\cdot}{\cdot} & 5 & 6 \\ {\cdot}\upDownCirc{}{\cdot} & 4 & . \end{array}$ \qquad $\begin{array}[t]{c|ccc} & {\cdot}{\cdot}{\cdot}{\cdot} & {\cdot}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}{\cdot} \\ \hline {\cdot}{\cdot}{\cdot}{\cdot} & 14 & 18 & 24 \\ {\cdot}{\cdot}\upDownCirc{}{\cdot} & 10 & 12 & . \\ {\cdot}\upDownCirc{}\upDownCirc{}{\cdot} & 8 & . & . \end{array}$ \qquad $\begin{array}[t]{c|cccccc} & {\cdot}{\cdot}{\cdot}{\cdot}{\cdot} & {\cdot}\noneCirc{}{\cdot}{\cdot}{\cdot} & {\cdot}{\cdot}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}{\cdot}\noneCirc{}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}\noneCirc{}{\cdot} \\ \hline {\cdot}{\cdot}{\cdot}{\cdot}{\cdot} & 42 & 56 & 60 & 76 & 84 & 120 \\ {\cdot}{\cdot}{\cdot}\upDownCirc{}{\cdot} & 28 & 36 & 36 & . & 48 & . \\ {\cdot}{\cdot}\upDownCirc{}{\cdot}{\cdot} & 25 & 30 & 36 & . & . & . \\ {\cdot}{\cdot}\upDownCirc{}\upDownCirc{}{\cdot} & 20 & 24 & . & . & . & . \\ {\cdot}\upDownCirc{}{\cdot}\upDownCirc{}{\cdot} & 20 & 24 & . & . & . & . \\ {\cdot}\upDownCirc{}\upDownCirc{}\upDownCirc{}{\cdot} & 16 & . & . & . & . & . \end{array}$} \vspace{.3cm} \centerline{$\begin{array}{c|cccccccccccccccc} & {\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot} & {\cdot}\noneCirc{}{\cdot}{\cdot}{\cdot}{\cdot} & {\cdot}{\cdot}\noneCirc{}{\cdot}{\cdot}{\cdot} & {\cdot}{\cdot}{\cdot}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}{\cdot}{\cdot}\noneCirc{}{\cdot} & {\cdot}\noneCirc{}{\cdot}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}{\cdot}{\cdot}{\cdot} & {\cdot}{\cdot}\noneCirc{}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}{\cdot}\noneCirc{}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}\noneCirc{}{\cdot}{\cdot} & {\cdot}\noneCirc{}\noneCirc{}\noneCirc{}\noneCirc{}{\cdot} \\ \hline {\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot} & 132 & 180 & 200 & 200 & 248 & 280 & 288 & 324 & 408 & 480 & 720 \\ {\cdot}{\cdot}{\cdot}{\cdot}\upDownCirc{}{\cdot} & 84 & 112 & 120 & 112 & . & 152 & 168 & 168 & . & 240 & . \\ {\cdot}{\cdot}{\cdot}\upDownCirc{}{\cdot}{\cdot} & 70 & 90 & 90 & . & 108 & . & 120 & . & 144 & . & . \\ {\cdot}{\cdot}\upDownCirc{}{\cdot}{\cdot}{\cdot} & 70 & 84 & . & 90 & 108 & 108 & . & . & . & . & . \\ {\cdot}{\cdot}{\cdot}\upDownCirc{}\upDownCirc{}{\cdot} & 56 & 72 & 72 & . & . & . & 96 & . & . & . & . \\ {\cdot}{\cdot}\upDownCirc{}\upDownCirc{}{\cdot}{\cdot} & 56 & 60 & . & . & 72 & . & . & . & . & . & . \\ {\cdot}\upDownCirc{}{\cdot}{\cdot}\upDownCirc{}{\cdot} & 50 & . & 72 & 72 & . & . & . & 96 & . & . & . \\ {\cdot}{\cdot}\upDownCirc{}{\cdot}\upDownCirc{}{\cdot} & 50 & 60 & . & 60 & . & 72 & . & . & . & . & . \\ {\cdot}{\cdot}\upDownCirc{}\upDownCirc{}\upDownCirc{}{\cdot} & 40 & 48 & . & . & . & . & . & . & . & . & . \\ {\cdot}\upDownCirc{}{\cdot}\upDownCirc{}\upDownCirc{}{\cdot} & 40 & . & 48 & . & . & . & . & . & . & . & . \\ {\cdot}\upDownCirc{}\upDownCirc{}\upDownCirc{}\upDownCirc{}{\cdot} & 32 & . & . & . & . & . & . & . & . & . & . \end{array}$} \caption{All factorial-Catalan numbers~$\factCatalan{\decoration}$ for~$|\decoration| \in \{3,4,5,6\}$. Each row (resp.~column) corresponds to all decorations with a fixed subset of positions marked with~\upDownCirc{} (resp.~\noneCirc{}). For example, we read in row~${\cdot}{\cdot}\upDownCirc{}{\cdot}{\cdot}{\cdot}$ and column~${\cdot}\noneCirc{}{\cdot}{\cdot}\noneCirc{}{\cdot}$ of the bottom table that~$\factCatalan{\decoration_1\noneCirc{}\upDownCirc{}\decoration_4\noneCirc{}\decoration_6} = 108$ for any~${\decoration_1, \decoration_4, \decoration_6 \in \{\upCirc{}, \downCirc{}\}}$. Dots inside the table correspond to overlapping sets of positions of~\noneCirc{} and~\upDownCirc{}. These tables give all factorial-Catalan numbers up to the mirror symmetry of Remark~\ref{rem:symmetrees}.} \label{table:factorialCatalan} \end{table} } %%% \subsubsection{Only \noneCirc{} and \upDownCirc{} matter} According to Corollary~\ref{coro:patternAvoidingPermutations}, $\decoration$-permutrees are in bijection with permutations of~$\fS_n$ avoiding the patterns~$ac \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ac$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$. We construct a generating tree~$\generatingTree_{\decoration}$ for these permutations. This tree has~$n$ levels, and the nodes at level~$\level$ are labelled by the permutations of~$[\level]$ whose values are decorated by the restriction of~$\decoration$ to~$[\level]$ and avoiding the two patterns~$ac \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ac$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$. The parent of a permutation in~$\generatingTree_\decoration$ is obtained by deleting its maximal value. See ~\fref{fig:generatingTree} for examples of such generating trees. %\begin{figure}[H]%%Fig 9 % \centerline{\includegraphics[scale=.8,,angle=90]{rotation}} \begin{figure}%%Fig 8 \centerline{\includegraphics[scale=.275,angle=90]{generatingTree}} \caption{The generating trees~$\generatingTree_\decoration$ for the decorations~$\decoration = \downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}$ (top) and ${\decoration = \downCirc{}\noneCirc{}\upDownCirc{}\upCirc{}}$ (bottom). Free gaps are marked with blue dots.} \label{fig:generatingTree} \end{figure} \begin{proposition} \label{prop:generatingTree} For any decorations~$\decoration, \decoration' \in \Decorations^n$ with~$\decoration^{-1}(\noneCirc{}) = \decoration'\,\!^{-1}(\noneCirc{})$ and ${\decoration^{-1}(\upDownCirc{}) = \decoration'\,\!^{-1}(\upDownCirc{})}$, the generating trees~$\generatingTree_\decoration$ and~$\generatingTree_{\decoration'}$ are isomorphic. \end{proposition} For the proof, we consider the possible positions of~$\level+1$ in the children of a permutation~$\tau$ at level~$\level$ in~$\generatingTree_\decoration$. Index by~$\{0, \dots, \level\}$ from left to right the gaps before the first letter, between two consecutive letters, and after the last letter of~$\tau$. We call \defn{free gaps} the gaps in~$\{0, \dots, \level\}$ where placing~$\level+1$ does not create a pattern~$ac \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ac$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$. They are marked with a blue point~$\freeGap$ in \fref{fig:generatingTree}. \begin{lemma} \label{lem:GeneratingTree} Any permutation at level~$\level$ with~$g$ free gaps has $g$ children in~$\generatingTree_\decoration$, whose numbers of free gaps \begin{itemize} \item all equal $g+1$ when~$\decoration_{\level+1} = \noneCirc{}$, \item range from~$2$ to~$g+1$ when~$\decoration_{\level+1} = \downCirc{}$ or \upCirc{}, \item all equal $2$ when~$\decoration_{\level+1} = \upDownCirc{}$. \end{itemize} \end{lemma} \begin{proof} Let~$\tau$ be a permutation at level~$\level$ in~$\generatingTree_\decoration$ with $g$ free gaps. Let~$\sigma$ be the child of~$\tau$ in~$\generatingTree_\decoration$ obtained by inserting~$\level+1$ at a free gap~$j \in \{0, \dots, \level\}$. Then the free gaps of~$\sigma$ are~$0$, $j+1$ together with \begin{itemize} \item all free gaps of~$\tau$ if~$\decoration_{\level+1} = \noneCirc{}$, \item the free gaps of~$\tau$ after~$j$ if~$\decoration_{\level+1} = \downCirc{}$, \item the free gaps of~$\tau$ before~$j+1$ if~$\decoration_{\level+1} = \upCirc{}$, \item no other free gaps if~$\decoration_{\level+1} = \upDownCirc{}$. \qedhere \end{itemize} \end{proof} \begin{proof}[Proof of Proposition~\ref{prop:generatingTree}] Order the children of a node of~$\generatingTree_\decoration$ from left to right by increasing number of free gaps as in \fref{fig:generatingTree}. Lemma~\ref{lem:GeneratingTree} shows that the shape of the resulting tree only depends on the positions of~\noneCirc{} and~\downCirc{} in~$\decoration$. It ensures that the trees~$\generatingTree_\decoration$ and~$\generatingTree_{\decoration'}$ are isomorphic and provides an explicit bijection between the \mbox{$\decoration$-permutrees} and~$\decoration'$-permutrees when~$\decoration^{-1}(\noneCirc{}) = \decoration'\,\!^{-1}(\noneCirc{})$ and ${\decoration^{-1}(\upDownCirc{}) = \decoration'\,\!^{-1}(\upDownCirc{})}$. \end{proof} Proposition~\ref{prop:generatingTree} immediately implies the following equi-enumeration result. \begin{corollary} \label{coro:equienumerated} The factorial-Catalan number~$\factCatalan{\decoration}$ only depends on the positions of the symbols~\noneCirc{} and~\upDownCirc{}~in~$\decoration$. \end{corollary} Using more carefully the description of the generating tree in Lemma~\ref{lem:GeneratingTree}, we obtain the following recursive formulas for the factorial-Catalan numbers. \begin{corollary} \label{coro:inductionFactCatalan} Let~$\decoration \in \Decorations^n$ and~$\decoration'$ be obtained by deleting the last letter~$\decoration_n$ of~$\decoration$. The number~$\factCatalan{\decoration,g}$ of permutations avoiding~$ac \dash b$ with~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash ac$ with~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$ and with $g$ free gaps satisfies the following recurrence relations: \[ \factCatalan{\decoration,g} = \begin{cases} \one_{g > 2} \cdot (g-1) \cdot \factCatalan{\decoration',g-1} & \text{if } \decoration_n = \noneCirc{}, \\[.2cm] \displaystyle \one_{g \ge 2} \cdot \sum_{g' \ge g-1} \factCatalan{\decoration',g'} & \text{if } \decoration_n = \upCirc{} \text{ or } \downCirc{}, \\[.6cm] \displaystyle \one_{g = 2} \cdot \sum_{g' \ge 2} g' \cdot \factCatalan{\decoration',g'} & \text{if } \decoration_n = \upDownCirc{}, \end{cases} \] where~$\one_X$ is $1$ if~$X$ is satisfied and~$0$ otherwise. \end{corollary} This can be used to compute the factorial-Catalan number~${\factCatalan{\decoration} = \sum_{g \ge 2} \factCatalan{\decoration,g}}$ inductively from~$\factCatalan{\decoration,2} = 1$ for any~$\decoration$ of size~$1$. We will see however different formulas in the remainder of this section. %%% \subsubsection{Summation formulas} By Corollary~\ref{coro:equienumerated}, it is enough to understand the factorial-Catalan number~$\factCatalan{\decoration}$ when~$\decoration \in \{\noneCirc{}, \downCirc{}, \upDownCirc{}\}^n$. Following Remark~\ref{rem:bijectionsPermutrees}, we first observe that we can also get rid of the~\upDownCirc{} symbols. \begin{lemma} \label{lem:productFactorialCatalanNumbers} Assume that~$\decoration = \decoration'\upDownCirc{}\,\decoration''$, then $\factCatalan{\decoration} = \factCatalan{\decoration'\noneCirc{}} \cdot \factCatalan{\noneCirc{}\,\decoration''}$. \end{lemma} We can therefore focus on the factorial-Catalan number~$\factCatalan{\decoration}$ when~$\decoration \in \{\noneCirc{}, \downCirc{}\}^n$. Note that when~$\decoration \in \{\noneCirc{}, \downCirc{}\}^n$, all $\decoration$-permutrees have a single outgoing strand, and are therefore rooted. This enables us to derive recursive formulas for factorial-Catalan numbers. \begin{proposition} \label{prop:recursiveFormulaOneNode} For any decoration~$\decoration \in \{\noneCirc{}, \downCirc{}\}^n$, the factorial-Catalan number~$\factCatalan{\decoration}$ satisfies the following recurrence relation \[ \factCatalan{\decoration} = \sum_{i \in \decoration^{-1}(\noneCirc{})} \factCatalan{\decoration_{|[n] \ssm i}} + \sum_{i \in \decoration^{-1}(\downCirc{})} \factCatalan{\decoration_{|[1, \dots, i-1]}} \cdot \factCatalan{\decoration_{|[i+1, \dots, n]}} \] \end{proposition} \begin{proof} We group the $\decoration$-permutrees according to their root. The formula thus follows from the obvious bijection between $\decoration$-permutree~$\tree$ with root~$i$ and \begin{itemize} \item $\decoration_{|[n] \ssm i}$-permutrees if~$\decoration_i = \noneCirc{}$, \item pairs of $\decoration_{|[1, \dots, i-1]}$- and $\decoration_{|[i+1, \dots, n]}$-permutrees if~$\decoration_i = \downCirc{}$. \qedhere \end{itemize} \end{proof} \begin{proposition} \label{prop:recursiveFormulaSeveralNodes} For any decoration~$\decoration \in \{\noneCirc{}, \downCirc{}\}^n$, the factorial-Catalan number~$\factCatalan{\decoration}$ satisfies the following recurrence relation \[ \factCatalan{\decoration} = \sum_{\substack{i \in \decoration^{-1}(\downCirc{}) \\ J \subseteq \decoration^{-1}(\noneCirc{})}} \factCatalan{\decoration_{|[1, \dots, i-1] \ssm J}} \cdot \factCatalan{\decoration_{|[i+1, \dots, n] \ssm J}} \cdot |J|! \] \end{proposition} \begin{proof} Similar as the previous proof except that we group the $\decoration$-permutrees according to their topmost~\downCirc{} vertex. Details are left to the reader. \end{proof} We conclude by the following statement which sums up the results of this numerology section. \begin{corollary} For any decoration~$\decoration$, the factorial-Catalan number~$\factCatalan{\decoration}$ is given by the recurrence formula \[ \factCatalan{\decoration} = \prod_{k \in [m]} \sum_{\substack{i \in [b_{k-1}, b_k] \cap \decoration^{-1}(\downCirc{}) \\ J \subseteq [b_{k-1}, b_k] \cap \decoration^{-1}(\noneCirc{})}} \factCatalan{\decoration_{|[b_{k-1}, \dots, i-1] \ssm J}} \cdot \factCatalan{\decoration_{|[i+1, \dots, b_k] \ssm J}} \cdot |J|! \] where~$\{b_0 < b_1 < \dots < b_m\} = \{0,n\} \cup \decoration^{-1}(\upDownCirc{})$. \end{corollary} \begin{example} \label{exm:numerologySpecificDecorations} Following Example~\ref{exm:permutreesSpecificDecorations}, we obtain classical formulas for \begin{enumerate}[(i)] \item the factorial~$n! = \factCatalan{\noneCirc{}^n}$ \href{https://oeis.org/A000142}{\cite[A000142]{OEIS}}, \item the Catalan number~$\frac{1}{n+1}\binom{2n}{n} = \factCatalan{\downCirc{}^n} = \factCatalan{\decoration}$ for~$\decoration \in \{\downCirc{}, \upCirc{}\}^n$ \href{https://oeis.org/A000108}{\cite[A000108]{OEIS}}, \item the power~$2^{n-1} = \factCatalan{\upDownCirc{}^n}$ \href{https://oeis.org/A000079}{\cite[A000079]{OEIS}}. \end{enumerate} Other relevant subfamilies of decorations will naturally appear in Section~\ref{sec:permutreeHopfAlgebra}. Namely, we are particularly interested in the subfamilies of decorations given by all words in~$D^n$ on a given subset~$D$ of~$\Decorations$. See Table~\ref{table:factorialCatalanFamilies}. {\footnotesize \begin{table} \centerline{ $\begin{array}[t]{c|r@{\quad}r@{\quad}r@{\quad}r@{\quad}r@{\quad}r@{\quad}r@{\quad}r|c} D & \multicolumn{8}{|c|}{\sum_{\decoration \in D^n} \factCatalan{\decoration} \quad \text{for } n \in [10]} & \text{reference} \\[.1cm] \hline \Decorations & 4 & 32 & 320 & 3584 & 43264 & 553472 & 7441920 & 104740864 & - \\ \hline \{\noneCirc{}, \upCirc{}, \downCirc{}\} & 3 & 18 & 144 & 1368 & 14688 & 173664 & 2226528 & 30647808 & - \\ \{\upCirc{}, \downCirc{}, \upDownCirc{}\} & 3 & 18 & 126 & 936 & 7164 & 55800 & 439560 & 3489696 & - \\ \{\noneCirc{}, \upCirc{}, \upDownCirc{}\} \text{ or } \{\noneCirc{}, \downCirc{}, \upDownCirc{}\} & 3 & 18 & 135 & 1134 & 10287 & 99306 & 1014039 & 10933542 & - \\ \hline \{\noneCirc{}, \upCirc{}\} \text{ or } \{\noneCirc{}, \downCirc{}\} & 2 & 8 & 44 & 296 & 2312 & 20384 & 199376 & 2138336 & \text{\href{https://oeis.org/A077607}{\cite[A077607]{OEIS}}} \\ \{\noneCirc{}, \upDownCirc{}\} & 2 & 8 & 40 & 224 & 1360 & 8864 & 61984 & 467072 & - \\ \{\upCirc{}, \upDownCirc{}\} \text{ or } \{\downCirc{}, \upDownCirc{}\} & 2 & 8 & 36 & 168 & 796 & 3800 & 18216 & 87536 & \text{\href{https://oeis.org/A084868}{\cite[A084868]{OEIS}}} \\ \{\upCirc{}, \downCirc{}\} & 2 & 8 & 40 & 224 & 1344 & 8448 & 54912 & 366080 & \text{\href{https://oeis.org/A052701}{\cite[A052701]{OEIS}}} \\ \hline \{\noneCirc{}\} & 1 & 2 & 6 & 24 & 120 & 720 & 5040 & 40320 & \text{\href{https://oeis.org/A000142}{\cite[A000142]{OEIS}}} \\ \{\upCirc{}\} \text{ or } \{\downCirc{}\} & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & \text{\href{https://oeis.org/A000108}{\cite[A000108]{OEIS}}} \\ \{\upDownCirc{}\} & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & \text{\href{https://oeis.org/A000079}{\cite[A000079]{OEIS}}} \\ \end{array}$} \caption{Sums of the factorial-Catalan numbers over subfamilies of decorations given by all words on a given subset of~$\Decorations$.} \label{table:factorialCatalanFamilies} \end{table} } \end{example} \begin{remark} The factorial-Catalan number is always bounded by~${2^{n-1} \le \factCatalan{\decoration} \le n!}$. Moreover, we even have~$\factCatalan{\decoration} \le \frac{1}{n+1}\binom{2n}{n}$ if~$\decoration$ contains no~$\noneCirc{}$, while $\factCatalan{\decoration} \ge \frac{1}{n+1}\binom{2n}{n}$ if~$\decoration$ contains no~$\upDownCirc{}$. This follows from Corollary~\ref{coro:inductionFactCatalan} but will even be easier to see from decoration refinements in the next section. \end{remark} We refer to Table~\ref{table:factorialCatalan} for the values of all factorial-Catalan numbers~$\factCatalan{\decoration}$ for all decorations~$\decoration$ such that~$|\decoration| \in \{3,4,5,6\}$. %%%%%%%%%%%%%%% \subsection{Rotations and permutree lattices} \label{subsec:rotations} We now extend the rotation from binary trees to all permutrees. This local operation only exchanges the orientation of an edge and rearranges the endpoints of two other edges. \begin{definition} \label{def:rotation} Let~$i \to j$ be an edge in a $\decoration$-permutree~$\tree$, with~$i < j$. Let~$D$ be the only (resp. the right) descendant subtree of vertex~$i$ if~${\decoration_i \in \{\noneCirc{}, \upCirc{}\}}$ (resp.~${\decoration_i \in \{\downCirc{}, \upDownCirc{}\}}$) and let~$U$ denote the only (resp.~the left) ancestor subtree of vertex~$j$ if~$\decoration_j \in \{\noneCirc{}, \downCirc{}\}$ (resp.~$\decoration_j \in \{\upCirc{}, \upDownCirc{}\}$). Let~$\tree'$ be the oriented tree obtained from~$\tree$ just reversing the orientation of~$i \to j$ and attaching the subtree~$U$ to~$i$ and the subtree~$D$ to~$j$. The transformation from~$\tree$ to~$\tree'$ is called \defn{rotation} of the edge~$i \to j$. See \fref{fig:rotation}. \medskip \begin{figure}[H]%%Fig 9 \centerline{\includegraphics[scale=.8]{rotation}} \caption{Rotations in permutrees: in each box, the tree~$\tree$ (left) is transformed into the tree~$\tree'$ (right) by rotation of the edge~$i \to j$. The $16$ boxes correspond to the possible decorations of~$i$~and~$j$.} \label{fig:rotation} \end{figure} \end{definition} The following statement shows that the rotation of the edge~$i \to j$ is the only operation which exchanges the orientation of this edge while preserving all other edge cuts. An \defn{edge cut} in a permutree~$\tree$ is the ordered partition~$\edgecut{I}{J}$ of the vertices of~$\tree$ into the set~$I$ of vertices in the source set and the set~$J = [n] \ssm I$ of vertices in the target set of an oriented edge of~$\tree$. \begin{proposition} \label{prop:rotation} The result~$\tree'$ of the rotation of an edge~$i \to j$ in a $\decoration$-permutree~$\tree$ is a \mbox{$\decoration$-permutree}. Moreover, $\tree'$ is the unique $\decoration$-permutree with the same edge cuts as~$\tree$, except the cut defined by the edge~$i \to j$. \end{proposition} \begin{proof} We first observe that~$\tree'$ is still a tree, with an orientation of its edges and a bijective labeling of its vertices by~$[n]$. To check that~$\tree'$ is still a $\decoration$-permutree, we need to check the local conditions of Definition~\ref{def:permutree} around each vertex of~$\tree'$. Since we did not perturb the labels nor the edges incident to the vertices of~$\tree$ distinct from~$i$ and~$j$, it suffices to check the local conditions around~$i$ and~$j$. By symmetry, we only give the arguments around~$i$. We distinguish two cases: \begin{itemize} \item If $i$ is an down vertex in~$\tree$ (decorated by~\downCirc{} or~\upDownCirc{}), then~$D$ is the right descendant of~$i$ in~$\tree$, so that all labels in~$D$ are larger than~$i$. Moreover, all labels in the right ancestor and descendant of~$j$ (if any) are larger than~$j$, which is in turn larger than~$i$. It follows that all labels in the right descendant of~$i$ in~$\tree'$ are larger than~$i$. Finally, the left descendant of~$i$ in~$\tree'$ is the left descendant of~$i$ in~$\tree$, so all its labels are still smaller than~$i$. \item If~$i$ is an up vertex in~$\tree$ (decorated by~\upCirc{} or~\upDownCirc{}), then~$U$ belongs to the right ancestor of~$i$ in~$\tree$, so that all labels in~$U$ are larger than~$i$. It follows that all labels in the right ancestor of~$i$ in~$\tree'$ are larger than~$i$. Finally, the left ancestor of~$i$ in~$\tree'$ is the left ancestor of~$i$ in~$\tree$, so all its labels are still smaller~than~$i$. \end{itemize} This closes the proof that~$\tree'$ is a $\decoration$-permutree. % By construction, the $\decoration$-permutree~$\tree'$ clearly has the same edge cuts as~$\tree$, except the cut corresponding to the edge~$i \to j$. Any $\decoration$-permutree with this property is obtained from~$\tree$ by reversing the edge~$i \to j$ to an edge~$i \leftarrow j$ and rearranging the neighbors of~$i$ and~$j$. But it is clear that the rearrangement given in Definition~\ref{def:rotation} is the only one which preserves the local conditions of Definition~\ref{def:permutree} around the vertices~$i$ and~$j$. \end{proof} \begin{remark} Following Remark~\ref{rem:234angulations}, a rotation on permutrees is dual to a flip on $\{2,3,4\}$-angulations of~$\b{P}_\decoration$. Namely, after deletion of an internal arc from a \mbox{$\{2,3,4\}$-an}\-gulation, there is a unique distinct internal arc that can be inserted to complete to a new~$\{2,3,4\}$-angulation. See \fref{fig:flip}. \begin{figure}[H]%%Fig 10 \centerline{\includegraphics[scale=.7]{flip}} \caption{A sequence of two rotations on permutrees, and the corresponding flips on $\{2,3,4\}$-angulations.} \label{fig:flip} \end{figure} \end{remark} Define the \defn{increasing rotation graph} on~$\Permutrees(\decoration)$ to be the graph whose vertices are the $\decoration$-permutrees and whose arcs are increasing rotations~$\tree \to \tree'$, \ie where the edge~$i \to j$ in~$\tree$ is reversed to the edge~$i \leftarrow j$ in~$\tree'$ for~$i < j$. See \fref{fig:permutreeLattices}. The following statement, adapted from N.~Reading's work~\cite{Reading-CambrianLattices}, asserts that this graph is acyclic, that its transitive closure defines a lattice, and that this lattice is closely related to the weak order. See \fref{fig:permutreeLattices}. \begin{proposition} \label{prop:permutreeLattice} The transitive closure of the increasing rotation graph on~$\Permutrees(\decoration)$ is a lattice, called \defn{$\decoration$-permutree lattice}. The map~$\PSymbol : \fS^\decoration \to \Permutrees(\decoration)$ defines a lattice homomorphism from the weak order on~$\fS^\decoration$ to the $\decoration$-permutree lattice on~$\Permutrees(\decoration)$. \end{proposition} \begin{proof} For two $\decoration$-permutree congruence classes~$X,Y$, define~$X \le Y$ if and only if there are representatives~$\sigma \in X$ and~$\tau \in Y$ such that~$\sigma \le \tau$ in weak order. By Proposition~\ref{prop:weakOrderCongruence}, this order defines a lattice on the $\decoration$-permutree congruence classes. Moreover, these classes correspond to the $\decoration$-permutrees by Proposition~\ref{prop:permutreeCongruenceClass}. Therefore, we only have to show that the quotient order on these classes coincides with the order given by increasing flips on the $\decoration$-permutrees. For this, it suffices to check that if two \hvFloat[nonFloat=true, capPos=b, capWidth=w, capAngle=0, objectAngle=90, capVPos=c, objectPos=c]{figure} %Fig 11 {\begin{minipage}{21cm}\vspace*{-1.2cm}\centerline{\includegraphics[scale=.7]{permutreeLattices}}\end{minipage}} {The $\decoration$-permutree lattices, for the decorations $\decoration = \noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}$ (left) and $\decoration = \noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}$~(right).} {fig:permutreeLattices} \noindent permutations~$\sigma$ and~$\tau$ differ by the transposition of two consecutive values~$i 0. \qedhere \] \end{proof} %%% \subsubsection{Matriochka permutreehedra} We have seen in Proposition~\ref{prop:refinementPermutreeFan} that the $\decoration$-permu\-tree fan~$\Fan[\decoration]$ refines the $\decoration'$-permutree fan~$\Fan[\decoration']$ when~$\decoration \less \decoration'$. It implies that all rays of~$\Fan[\decoration']$ are also rays of~$\Fan[\decoration]$, and thus that all the inequalities of the $\decoration'$-permutreehe\-dron~$\Permutreehedron[\decoration']$ are also inequalities of the $\decoration$-permutreehedron~$\Permutreehedron[\decoration]$. \begin{corollary} For any two decorations~$\decoration \less \decoration'$, we have~$\Permutreehedron[\decoration] \subseteq \Permutreehedron[\decoration']$. \end{corollary} Thus, the poset of $(n-1)$-dimensional permutreehedra ordered by inclusion is isomorphic to the refinement poset on the decorations of~${\noneCirc{} \cdot \Decorations^{n-2} \cdot \noneCirc{}}$ (the decorations on the first and last vertices do not matter by Remark~\ref{rem:bijectionsPermutrees}). Chains along this poset provide \defn{Matriochka permutreehedra}. This poset is illustrated on \fref{fig:permutreehedra}. \subsubsection{Parallel facets} It is known that the permutahedron~$\Perm$ has $2^{n-1}-1$ pairs of parallel facets, while all associahedra~$\Asso[\decoration]$ of C.~Hohlweg and C.~Lange~\cite{HohlwegLange, LangePilaud} as well as the parallelepiped~$\Para$ have~$n-1$ pairs of parallel facets. This property extends to all permutreehedra as follows. \begin{proposition} Consider a decoration~$\decoration \in \Decorations^n$, assume without loss of generality that~$\decoration_1 \ne \noneCirc{}$ and~$\decoration_n \ne \noneCirc{}$, let~$1 = u_0, u_1, \dots, u_{v-1}, u_v = n$ be the positions in~$\decoration$ such that~${\decoration_{u_i} \ne \noneCirc{}}$, and let~$n_i = u_i-u_{i-1}-1$ be the sizes of the (possibly empty) blocks of~$\noneCirc{}$ in~$\decoration$. Then the permutreehedron~$\Permutreehedron$ has \[ \sum_{i \in [v]} (2^{n_i+1}-1) \] pairs of parallel facets whose normal vectors are the characteristic vectors of \begin{itemize} \item the sets~$[u_{i-1}] \cup X$ for~$i \in [v]$ and~$X \subseteq (u_{i-1}, u_i)$, and \item the sets~$X$ for~$i \in [v]$ and~$\varnothing \ne X \subsetneq (u_{i-1}, u_i)$. \end{itemize} \end{proposition} \begin{proof} Pairs of parallel facets correspond to pairs of complementary building blocks. As already mentioned, it is easier to think of building blocks as arcs in~$\b{P}_\decoration$: the building block corresponding to an arc~$\alpha$ is the set~$I_\alpha$ of indices of all points~$\b{p}_k$ below~$\alpha$, including the endpoints of~$\alpha$ in the upper convex hull of~$\b{P}_\decoration$ (and excluding~$0$ and~$n+1$). \hvFloat[nonFloat=true, capWidth=.8735, capPos=b, capAngle=0, objectAngle=90, capVPos=c, objectPos=c]{figure}%Fig 16 {\begin{minipage}{21cm}\vspace*{-2.1cm}\centerline{\includegraphics[scale=.275]{permutreehedra}}\end{minipage}} {The $\decoration$-permutreehedra, for all decorations $\decoration \in \noneCirc{} \cdot \Decorations^2 \cdot \noneCirc{}$.} {fig:permutreehedra} %%% Let~$\b{p}_i, \b{p}_j$ with~$i < j$ denote the endpoints of~$\alpha$, and define~$J_\alpha \eqdef (i,j) \cap \decoration^{-1}(\downCirc)$ and~$K_\alpha \eqdef (i,j) \ssm \decoration^{-1}(\upCirc)$. Observe that \begin{itemize} \item if~$\b{p}_0$ and~$\b{p}_{n+1}$ are both above~$\alpha$, then~$J_\alpha \subseteq I_\alpha \subseteq K_\alpha$, \item if~$\b{p}_0$ is below~$\alpha$ while~$\b{p}_{n+1}$ is above~$\alpha$, then~$[1,i] \cup J_\alpha \subseteq I_\alpha \subseteq [1,i] \cup K_\alpha$, \item if~$\b{p}_0$ is above~$\alpha$ while~$\b{p}_{n+1}$ is below~$\alpha$, then~$[j,n] \cup J_\alpha \subseteq I_\alpha \subseteq [j,n] \cup K_\alpha$, \item if~$\b{p}_0$ and~$\b{p}_{n+1}$ are both below~$\alpha$, then~$[1,i] \cup [j,n] \cup J_\alpha \subseteq I_\alpha \subseteq [1,i] \cup [j,n] \cup K_\alpha$. \end{itemize} We conclude that if~$I_\alpha$ and~$I_\beta$ are complementary, then \begin{itemize} \item either there is~$i \in [v]$ such that~$I_\alpha = [1,u_{i-1}] \cup X$ and~$I_\beta = [u_i+1,n] \cup (u_{i-1},u_i) \ssm X$ for some~$X \subseteq (u_{i-1},u_i)$ (or the opposite), \item or there is~$i \in [v]$ such that~$I_\alpha = X$ and~$I_\beta = [n] \ssm X$ for some ${\varnothing \ne X \subsetneq (u_{i-1}, u_i)}$ (or the opposite). \end{itemize} The enumerative formula is then immediate. \end{proof} %%% \subsubsection{Common vertices} It is combinatorially relevant to characterize which vertices are common to two nested permutreehedra. For example, note that~$[1, 2, \dots, n-1, n]$ and~$[n, n-1, \dots, 2, 1]$ are common vertices of all $(n-1)$-dimensional permutreehedra. The other common vertices are characterized in the following statement. \begin{proposition} \label{prop:singletons} Consider two decorations~$\decoration \less \decoration'$, a $\decoration$-permutree~$\tree$ and a $\decoration'$-permu\-tree~$\tree'$. The following assertions are equivalent: \begin{enumerate}[(i)] \item the vertex~$\b{a}(\tree)$ of~$\Permutreehedron[\decoration]$ coincides with the vertex~$\b{a}(\tree')$ of~$\Permutreehedron[\decoration']$, \item the cone~$\Cone(\tree)$ of~$\Permutreehedron[\decoration]$ coincides with the cone~$\Cone(\tree')$ of~$\Permutreehedron[\decoration']$, \item the normal cone~$\Cone\polar(\tree)$ of~$\Permutreehedron[\decoration]$ coincides with the normal cone~$\Cone\polar(\tree')$ of~$\Permutreehedron[\decoration']$, \item the fiber of~$\tree'$ under the surjection~$\surjection$ is the singleton~$(\surjection)^{-1}(\tree') = \{\tree\}$, \item $\tree$ and~$\tree'$ have precisely the same linear extensions, \item $\tree$ and~$\tree'$ coincide up to some empty descendant or ancestors, \item for each~$i \in [n]$ with~$\decoration_i \in \{\noneCirc{}, \upCirc{}\}$ but~$\decoration'_i \in \{\downCirc{}, \upDownCirc{}\}$ (resp.~with~$\decoration_i \in \{\noneCirc{}, \downCirc{}\}$ but~$\decoration'_i \in \{\upCirc{}, \upDownCirc{}\}$), the vertex~$i$ of~$\tree$ is not above (resp.~below) an edge of~$\tree$, and $\tree'$ is obtained from~$\tree$ by adding one empty descendant (resp.~ancestor) subtree at each such vertex~$i$, \item for each~$i \in [n]$ with~$\decoration_i \in \{\noneCirc{}, \upCirc{}\}$ but~$\decoration'_i \in \{\downCirc{}, \upDownCirc{}\}$ (resp.~with~$\decoration_i \in \{\noneCirc{}, \downCirc{}\}$ but~$\decoration'_i \in \{\upCirc{}, \upDownCirc{}\}$), the vertex~$i$ of~$\tree'$ has at least one empty descendant (resp.~ancestor), and~$\tree$ is obtained from~$\tree'$ by deleting one empty descendant (resp.~ancestor) subtree at each such vertex~$i$. \end{enumerate} \end{proposition} \begin{proof} Since~$\Permutreehedron[\decoration']$ is obtained from~$\Permutreehedron[\decoration]$ by deleting facet inequalities, and~$\Permutreehedron[\decoration]$ is simple, a vertex~$\b{a}(\tree)$ is common to~$\Permutreehedron[\decoration]$ and~$\Permutreehedron[\decoration']$ if and only if the facets containing~$\b{a}(\tree)$ are common to~$\Permutreehedron[\decoration]$ and~$\Permutreehedron[\decoration']$. This proves (i)$\iff$(ii). The equivalence (ii)$\iff$(iii) is immediate by polarity. The equivalence (iii)$\iff$(iv) follows by Proposition~\ref{prop:refinementPermutreeFan}. The equivalence (iii)$\iff$(v) holds since~$\Cone\polar(\tree)$ is the union of the cones~$\Cone\polar(\tau)$ over all linear extensions~$\tau$ of~$\tree$. The equivalence (ii)$\iff$(vi) holds since~$\Cone(\tree)$ has a facet for each internal edge of~$\tree$. Finally, the equivalence (vi)$\iff$(vii)$\iff$(viii) directly follow from the description of~$\surjection$ in Section~\ref{subsec:decorationRefinements}. \end{proof} In particular, since~$\noneCirc{}^n \less \decoration$ for any decoration~$\decoration$, Proposition~\ref{prop:singletons} characterizes the common points of the permutahedron~$\Perm$ with any permutreehedron~$\Permutreehedron$. Call \defn{$\decoration$-singleton} a permutation~$\tau$ corresponding to such a common vertex, that is, such that~$\PSymbol^{-1}(\PSymbol(\tau)) = \{\tau\}$. In the next section, we will need the following consequences of Proposition~\ref{prop:singletons}. \begin{lemma} \label{lem:singleton} Let~$\tau \in \fS_n$ be a $\decoration$-singleton and let~$i,j \in [n]$ be such that~$\tau(i) = j$. Then \begin{itemize} \item if~$\decoration_j \in \{\downCirc{}, \upDownCirc{}\}$, then either~$\tau([1,i-1]) \subseteq [1,j-1]$ or~$\tau([1,i-1]) \subseteq [j+1,n]$; \item if~$\decoration_j \in \{\upCirc{}, \upDownCirc{}\}$, then either~$\tau([i+1,n]) \subseteq [1,j-1]$ or~$\tau([i+1,n]) \subseteq [j+1,n]$. \end{itemize} \end{lemma} \begin{proof} Let~$\tree$ be the $\noneCirc{}^n$-permutree obtained by insertion of~$\tau$. By Proposition~\ref{prop:singletons}, if~$\decoration_j \in \{\downCirc{}, \upDownCirc{}\}$, then the vertex~$j$ of~$\tree$ is not above an edge of~$\tree$. Equivalently, all vertices of~$\tree$ below~$j$ are either to the left or to the right of~$j$. In other words, if~$i = \tau^{-1}(j)$, we have either~$\tau([1,i-1]) \subseteq [1,j-1]$ or~$\tau([1,i-1]) \subseteq [j+1,n]$. The second part of the statement is symmetric. \end{proof} \begin{lemma} \label{lem:oppositeSingletons} Consider a decoration~$\decoration \in \noneCirc{} \cdot \Decorations^{n-2} \cdot \noneCirc{}$, and denote by~$I_1, \dots, I_p$ the blocks of consecutive decorations~\noneCirc{} in~$\decoration$. Then a permutation~$\tau$ and its opposite~$\bar\tau = \tau \cdot [n, \dots, 1]$ are both $\decoration$-singletons if and only if~$\tau = \pi_1 \cdot \ldots \cdot \pi_p$ or~$\bar\tau = \pi_1 \cdot \ldots \cdot \pi_p$ for some~$(\pi_1, \dots, \pi_p) \in \fS_{I_1} \times \dots \times \fS_{I_p}$. \end{lemma} \begin{proof} Let~$i,j \in [n]$ be such that~$\tau(i) = j$ and~$\decoration_j \in \{\downCirc{}, \upDownCirc{}\}$. Since~$\tau$ is a $\decoration$-singleton, $\tau([1,i-1])$ is a subset of either~$[1,j-1]$ or~$[j+1,n]$ by Lemma~\ref{lem:singleton}. Since~$\bar\tau$ is a $\decoration$-singleton and~${\bar\tau(n+1-i) = j}$, $\tau([i+1,n]) = \bar\tau([1,n-i]) $ is a subset of either \mbox{$[1,j-1]$} or~$[j+1,n]$ by Lemma~\ref{lem:singleton}. If~$\tau([1,i-1])$ and~$\tau([i+1,n])$ are both subsets of~$[1,j-1]$ (resp.~of~${[j+1,n]}$), then~$j=n$ (resp.~$j=1$) which contradicts our assumption that~$\decoration_n = \noneCirc{}$ (resp.~that~$\decoration_1 = \noneCirc{}$). By symmetry, we conclude that for all~$i,j \in [n]$ with~$\tau(i) = j$ and~$\decoration_j \ne \noneCirc{}$, we have either~$\tau([1,i-1]) \subseteq [1,j-1]$ and~${\tau([i+1,n]) = [j+1,n]}$, or~$\tau([1,i-1]) \subseteq [j+1,n]$ and~$\tau([i+1,n]) = [1,j-1]$. The result immediately follows. \end{proof} %%% \subsubsection{Isometrees} We now consider isometries of the permutreehedron~$\Permutreehedron$ and between distinct permutreehedra~$\Permutreehedron[\decoration]$ and~$\Permutreehedron[\decoration']$. As already observed, $\Permutreehedron$ is independent of the first and last decorations~$\decoration_1$ and~$\decoration_n$. In this section, we assume without loss of generality that~${\decoration_1 = \decoration_n = \noneCirc{}}$. For a permutation~$\tau \in \fS_n$, we denote by~$\rho_\tau: \R^n \to \R^n$ the isometry of~$\R^n$ given by permutation of coordinates~$\rho_\tau(x_1, \dots, x_n) = (x_{\tau(1)}, \dots, x_{\tau(n)})$. We write~${\rho_i = \rho_{(i \; i+1)}}$ for the exchange of the $i$th and~$(i+1)$th coordinates. With these notations, we have the following observation. \begin{proposition} \label{prop:isometrees1} If~$\decoration_i = \decoration_{i+1} = \noneCirc{}$, then~$\rho_i$ is an isometry of the permutreehedron~$\Permutreehedron$. Thus, if~$I_1, \dots, I_p$ are the blocks of consecutive~\noneCirc{} in~$\decoration$, then for any~${\Pi = (\pi_1, \dots, \pi_v) \in \fS_{I_1} \times \dots \times \fS_{I_p}}$, the map~$\rho_\Pi \eqdef \rho_{\pi_1} \circ \dots \circ \rho_{\pi_p}$ is an isometry of the permutreehedron~$\Permutreehedron$. \end{proposition} \begin{proof} Assume that~$\decoration_i = \decoration_{i+1} = \noneCirc{}$. Then there are no local condition around vertices~$i$ and~$i+1$ in the definition of $\decoration$-permutrees. Therefore, exchanging the labels~$i$ and~$i+1$ in any $\decoration$-permutree~$\tree$ results in a new $\decoration$-permutree~$\tree'$. Moreover, the vertices associated to~$\tree$ and~$\tree'$ are related by~$\b{a}(\tree') = \rho_i(\b{a}(\tree))$. We conclude that~$\rho_i$ is indeed an isometry of the permutreehedron~$\Permutreehedron$. \end{proof} Remember now the two symmetrees discussed in Remark~\ref{rem:symmetrees}. Denote by~$\horizontalSymmetry{\tree}$ (resp.~$\verticalSymmetry{\tree}$) the permutree obtained from~$\tree$ by a horizontal (resp.~vertical) symmetry, and denote by~$\horizontalSymmetry{\decoration}$ (resp.~$\verticalSymmetry{\decoration}$) the decoration obtained from~$\decoration$ by a mirror image (resp.~by interverting~\downCirc{} and~\upCirc{} decorations), so that~$\decoration(\horizontalSymmetry{\tree}) = \horizontalSymmetry{\decoration(\tree)}$ (resp.~$\decoration(\verticalSymmetry{\tree}) = \verticalSymmetry{\decoration(\tree)}$). Finally, we write~$\horizontalVerticalSymmetry{\decoration} = \horizontalSymmetry{(\verticalSymmetry{\decoration})} = \verticalSymmetry{(\horizontalSymmetry{\decoration})}$. \begin{proposition} \label{prop:isometrees2} For any permutree~$\tree$, we have \[ \b{a}(\horizontalSymmetry{\tree})_i = \b{a}(\tree)_{n+1-i} \qquad\text{and}\qquad \b{a}(\verticalSymmetry{\tree})_i = n+1-\b{a}(\tree)_i. \] Thus, the permutreehedra~$\Permutreehedron[\decoration]$, $\Permutreehedron[\horizontalSymmetry{\decoration}]$, $\Permutreehedron[\verticalSymmetry{\decoration}]$, and~$\Permutreehedron[\horizontalVerticalSymmetry{\decoration}]$ are all isometric. \end{proposition} \begin{proof} The formulas follow by case analysis from the definition of~$\b{a}(\tree)_i$. \end{proof} We denote by \[ \chi : (x_1, \dots, x_n) \mapsto (x_n, \dots, x_1) \quad\text{and}\quad \theta : (x_1, \dots, x_n) \mapsto (n+1-x_1, \dots, n+1-x_n) \] the two maps of Proposition~\ref{prop:isometrees2}. To follow Remark~\ref{rem:symmetrees}, we call them \defn{isometrees}. The main result of this section claims that the isometries of Propositions~\ref{prop:isometrees1} and~\ref{prop:isometrees2} are essentially the only isometries preserving permutreehedra. \begin{proposition} \label{prop:isometrees3} Let~$\decoration, \decoration' \in \noneCirc{} \cdot \Decorations^{n-2} \cdot \noneCirc{}$ and denote by~$I_1, \dots, I_p$ and~$I'_1, \dots, I'_{q}$ the blocks of consecutive decorations~\noneCirc{} in~$\decoration$ and~$\decoration'$ respectively. If~$\rho$ is an isometry of~$\R^n$ which sends the permutreehedron~$\Permutreehedron[\decoration]$ to the permutreehedron~$\Permutreehedron[\decoration']$, then~$\decoration' \in \{\decoration, \horizontalSymmetry{\decoration}, \verticalSymmetry{\decoration}, \horizontalVerticalSymmetry{\decoration}\}$ and~$\rho_{\Pi'}^{-1} \circ \rho \circ \rho_{\Pi}^{-1} \in \{\Id, \chi, \theta, \chi \circ \theta\}$ for some~$\Pi \in \fS_{I_1} \times \dots \times \fS_{I_p}$ and~${\Pi' \in \fS_{I'_1} \times \dots \times \fS_{I'_{q}}}$. \end{proposition} \begin{proof} By Proposition~\ref{prop:singletons}, the $\decoration$-singletons correspond to the cones of the permutree fan~$\Fan$ that are single braid cones. Since the isometry~$\rho$ sends the permutreehedron~$\Permutreehedron[\decoration]$ to the permutreehedron~$\Permutreehedron[\decoration']$, it sends the permutree fan~$\Fan[\decoration]$ to the permutree fan~$\Fan[\decoration']$, and thus the $\decoration$-singletons to the $\decoration'$-singletons. Therefore, $\rho$ sends any pair~$(\tau, \bar\tau)$ of opposite $\decoration$-singletons to a pair~$(\tau', \bar\tau')$ of opposite $\decoration'$-singletons. Lemma~\ref{lem:oppositeSingletons} ensures that there is~$\Pi \eqdef (\pi_1, \dots, \pi_p) \in \fS_{I_1} \times \dots \times \fS_{I_p}$ such that~${\tau = \pi_1 \cdot \ldots \cdot \pi_p}$ or~$\bar\tau = \pi_1 \cdot \ldots \cdot \pi_p$, and~$\Pi' \eqdef (\pi'_1, \dots, \pi'_{q}) \in \fS_{I'_1} \times \dots \times \fS_{I'_{q}}$ such that~$\tau' = \pi'_1 \cdot \ldots \cdot \pi'_{q}$ or~$\bar\tau' = \pi'_1 \cdot \ldots \cdot \pi'_{q}$. Therefore, the isometry~$\Gamma \eqdef \rho_{\Pi'}^{-1} \circ \rho \circ \rho_{\Pi}^{-1}$ stabilizes the pair of opposite singletons~$\{[1, \dots, n], [n, \dots, 1]\}$, and thus the center~$\b{O} \eqdef \frac{n+1}{2} \one$ of the permutahedron~$\Perm$. For any subset~$\varnothing \ne U \subseteq [n]$ of cardinality~$u \eqdef |U|$, the distance from~$\b{O}$ to the hyperplane~$\Hyp(U)$~is \[ d \big( \b{O}, \Hyp(U) \big) = \frac{n \, u\, (n - u)}{\sqrt{u^2 + (n - u)^2}}. \] Observe that the function \[ x \longmapsto \frac{x \, (1-x)}{\sqrt{x^2 + (1-x)^2}} \] is bijective on~$\big[ 0, \frac{1}{2} \big]$. It follows that the isometry~$\Gamma$ sends the hyperplane~$\Hyp(U)$, for~${\varnothing \ne U \subseteq \ground}$, to an hyperplane~$\Hyp(U')$ for some~$\varnothing \ne U' \subseteq [n]$ with~$|U'| = |U|$ or~$|U'| = n - |U|$. Observe moreover that the facets of~$\Perm$ defined by the hyperplanes~$\Hyp(\{i\})$ for~$i \in [n]$ are pairwise non-adjacent, but that the facet defined by~$\Hyp(\{i\})$ is adjacent to all facets defined by~${\Hyp(\ground \ssm \{j\})}$ for~$j \in [n] \ssm \{i\}$. Therefore, the hyperplanes~$\Hyp(\{i\})$ for~$i \in [n]$ are either all sent to the hyperplanes~$\Hyp(\{j\})$ for~$j \in [n]$, or all sent to the hyperplanes~$\Hyp([n] \ssm \{j\})$ for~$j \in [n]$. Assume first that we are in the former situation. Define a map~$\gamma : [n] \to [n]$ such that the hyperplane~$\Hyp(\{i\})$ is sent by~$\Gamma$ to the hyperplane~$\Gamma \big( \Hyp(\{i\}) \big) = \Hyp(\{\gamma(i)\})$ for any~$i \in [n]$. It follows that~$\Gamma(\b{e}_i) = \b{e}_{\gamma(i)}$. Since~$\Gamma$ is a linear map, it sends the characteristic vector of any subset~$\varnothing \ne U \subseteq [n]$ to the characteristic vector of~$\gamma(U)$. Thus, the map~$\gamma$ defines an isomorphism from the $\decoration$-building blocks to the $\decoration'$-building blocks. However, up to an horizontal reflection, the $\decoration$-building blocks determine the decoration~$\decoration$. Indeed, we immediately derive from the description of building blocks in terms of arcs in the point set~$\b{P}_\decoration$ that \begin{itemize} \item $\decoration_j \in \{\noneCirc{}, \downCirc{}\}$ if and only if~$\{j\}$ is a $\decoration$-building block, \item $\decoration_j \in \{\noneCirc{}, \upCirc{}\}$ if and only if~$[n] \ssm \{j\}$ is a $\decoration$-building block, and \item two labels~$i,j \in [n]$ are only separated by~\noneCirc{} in~$\decoration$ if and only if they belong to complementary $\decoration$-building blocks. \end{itemize} We conclude that~$\Gamma \in \{\Id, \chi\}$ in this first situation. Finally, if we were in the latter situation above, then we just apply a vertical reflection to the decoration~$\decoration$. By Proposition~\ref{prop:isometrees2}, it composes~$\Gamma$ by a symmetry~$\theta$ and thus places us back in the situation treated above. We conclude that~$\Gamma \in \{\theta, \chi \circ \theta\}$ in this second situation. \end{proof} \begin{corollary} Consider a decoration~$\decoration \in \noneCirc{} \cdot \Decorations^{n-2} \cdot \noneCirc{}$, and let~$n_1, \dots, n_p$ denote the sizes of the blocks of consecutive~\noneCirc{} in~$\decoration$. Then the isometry group of the permutreehedron~$\Permutreehedron$ has cardinality \[ n_1! \cdots n_p! \, (1 + \one_{\decoration = \horizontalSymmetry{\decoration}} - \one_{\decoration = \noneCirc{}^n}) \, (1 + \one_{\decoration \in \{\verticalSymmetry{\decoration}, \horizontalVerticalSymmetry{\decoration}\}}). \] \end{corollary} We finally consider the number~$x(n)$ of isometry classes of $n$-dimensional permutreehedra. We have~$x(0) = 1$ (a point), $x(1) = 1$ (a segment), $x(2) = 3$ (an hexagon, a pentagon, a quadrilateral), and \fref{fig:permutreehedra} shows that~$x(3) = 7$. In general, $x(n)$ is given by the following statement. \begin{corollary} The number~$x(n)$ of isometry classes of $n$-dimensional permutreehedra is the number of orbits of decorations~$\decoration \in \noneCirc{} \cdot \Decorations^{n-1} \cdot \noneCirc{}$ under the symmetrees~$\decoration \mapsto \horizontalSymmetry{\decoration}$ and~$\decoration \mapsto \verticalSymmetry{\decoration}$. It is given by the formula \[ x(n) = 2^{n-4} \big( 2^n + (-1)^n + 7 \big) \] for~$n \ge 1$. Its generating function is given by \[ \sum_{n \in \N} x(n)t^n = \frac{1-3t-5t^2+7t^3}{1-4t-4t^2+16t^3}. \] See~\href{https://oeis.org/A225826}{\cite[A225826]{OEIS}}. \end{corollary} \begin{proof} The first sentence is a direct consequence of Proposition~\ref{prop:isometrees3}. For the second part, note that~$x(n) = 2^{n-4} \big( 2^n + (-1)^n + 7 \big)$ satisfies the recursive formulas: \begin{equation} \tag{$\star$} \label{eq:cor-symmetrees-rec} x(2k) = 4 \cdot x(2k-1) - 4^{k-1} \qquad\text{and}\qquad x(2k+1) = 16 \cdot x(2k-1) - 9 \cdot 4^{k-1}, \end{equation} for~$k \ge 1$ with initial values~$x(0) = x(1) = 1$. There is left to prove that the number of orbits satisfies these recurrences as well. Let~$X_n$ be the set of orbits of decorations ${\decoration \in \noneCirc{} \cdot \Decorations^{n-1} \cdot \noneCirc{}}$ (of size $n+1$ such that the corresponding permutreehedron is of dimension~$n$) under the symmetrees~${\decoration \mapsto \horizontalSymmetry{\decoration}}$ and~${\decoration \mapsto \verticalSymmetry{\decoration}}$. We write $X_n = A_n \sqcup B_n \sqcup C_n \sqcup D_n \sqcup E_n$ as a disjoint union of~$5$ subsets according to the symetrees of the orbit: \begin{itemize} \item $A_n$ contains the orbits~$\{\decoration\}$ where~$\delta = \horizontalSymmetry{\decoration} = \verticalSymmetry{\decoration} = \horizontalVerticalSymmetry{\decoration}$ (like $\noneCirc{} \upDownCirc{} \noneCirc{} \upDownCirc{} \noneCirc{}$), \item $B_n$ contains the orbits~$\lbrace \decoration, \horizontalSymmetry{\decoration} \rbrace$ where $\decoration = \verticalSymmetry{\decoration} \ne \horizontalSymmetry{\decoration} = \horizontalVerticalSymmetry{\decoration}$ (like $\noneCirc{} \upDownCirc{} \noneCirc{} \noneCirc{} \noneCirc{}$), \item $C_n$ contains the orbits~$\lbrace \decoration, \verticalSymmetry{\decoration} \rbrace$ where $\decoration = \horizontalSymmetry{\decoration} \ne \verticalSymmetry{\decoration} = \horizontalVerticalSymmetry{\decoration}$ (like $\noneCirc{} \downCirc{} \upCirc{} \downCirc{} \noneCirc{}$), \item $D_n$ contains the orbits~$\lbrace \decoration, \verticalSymmetry{\decoration} = \horizontalSymmetry{\decoration} \rbrace$ where $\decoration= \horizontalVerticalSymmetry{\decoration} \ne \verticalSymmetry{\decoration} = \horizontalSymmetry{\decoration}$ (like $\noneCirc{} \downCirc{} \upDownCirc{} \upCirc{} \noneCirc{}$), \item $E_n$ contains the orbits~$\{\delta, \horizontalSymmetry{\decoration}, \verticalSymmetry{\decoration}, \horizontalVerticalSymmetry{\decoration}\}$, where all symmetrees of~$\decoration$ are distinct (like $\noneCirc{} \downCirc{} \upDownCirc{} \noneCirc{} \noneCirc{}$). \end{itemize} We write the corresponding numbers with lower case letters such that \[ x(n) = a(n) + b(n) + c(n) + d(n) + e(n). \] Now we can obtain recursive formulas for these number by a simple case by case combinatorial generation: orbits of decorations of odd sizes $2k+1$ (even dimension~$2k$) are obtained by adding a letter of $\Decorations$ in the middle of a decoration of size $2k$ and orbits of decorations of even sizes $2k+2$ (odd dimension $2k+1$) are obtained by adding a word of $\Decorations^2$ in the middle of a decoration of size $2k$. Depending on the symmetree subset of the original decoration of size $2k$, this process will have redundancies (adding two different letters can lead to one single orbit) and will lead to the following recursive formulas: \begin{align*} a(2k) &= 2 \cdot a(2k-1) & a(2k+1) &= 2 \cdot a(2k-1)\\ b(2k) &= 2 \cdot b(2k-1)& b(2k+1) &= 4 \cdot b(2k-1) + a(2k-1)\\ c(2k) &= a(2k-1) + 4 \cdot c(2k-1) & c(2k+1) &= 4 \cdot c(2k-1) + a(2k-1)\\ d(2k) &= 2 \cdot d(2k-1)& d(2k+1) &= 4 \cdot d(2k-1) + a(2k-1)\\ e(2k) &= b(2k-1) + d(2k-1) & e(2k+1) &= 2 \cdot a(2k-1) + 6 \cdot b(2k-1) \\ &\hspace{2pt}+4 \cdot e(2k-1) &+6 \cdot c(&2k-1) + 6 \cdot d(2k-1) + 16 \cdot e(2k-1) \end{align*} for~$k \ge 1$ with initial values~$a(1) = 1$ and~$b(1) = c(1) = d(1) = e(1) = 0$. In particular, we obtain \[ a(2k+1) = 2^k \qquad\text{and}\qquad b(2k+1) = c(2k+1) = d(2k+1) = 2 \cdot 4^{k-1} - 2^{k-1}. \] By a basic computation, one checks that the number~$x(n)$ of orbits in~$X_n$ satisfies~\eqref{eq:cor-symmetrees-rec}. For completeness, note that~$x(n)$ can be expressed as \[ x(n) = 4 \cdot x(n-1) + 4 \cdot x(n-2) - 16 \cdot x(n-3) \] for $n \geq 4$ with initial values~$x(0) = 1$, $x(1) = 1$, $x(2) = 3$ and $x(3) = 7$. Therefore, its generating function is given by \[ \sum_{n \in \N} x(n)t^n = \frac{1-3t-5t^2+7t^3}{1-4t-4t^2+16t^3}. \qedhere \] \end{proof} \subsubsection{Permutrees versus signed tree associahedra} To conclude this section on permutreehedra, we want to mention that these polytopes were already constructed very implicitly. Indeed, any permutreehdron is a product of certain faces of the signed tree associahedra studied in~\cite{Pilaud-signedTreeAssociahedra}. More specifically, for any decoration in~$\{\noneCirc{},\downCirc{}\}^n$, the permutreehedron is a graph associahedron as constructed in~\cite{CarrDevadoss, Postnikov, Zelevinsky}. We believe however that the present construction is much more explicit and reflects relevant properties of these polytopes, which are not necessarily apparent in the general construction of~\cite{Pilaud-signedTreeAssociahedra} (in particular the combinatorial and algebraic properties of the permutrees which do not hold in general for arbitrary signed tree associahedra). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The permutree Hopf algebra} \label{sec:permutreeHopfAlgebra} This section is devoted to algebraic aspects of permutrees. More precisely, using the same idea as G.~Chatel and V.~Pilaud in~\cite{ChatelPilaud} we construct a Hopf algebra on permutrees as a subalgebra of a decorated version of C.~Malvenuto and C.~Reutenauer's algebra. In turn, our algebra contains subalgebras isomorphic to C.~Malevenuto and C.~Reutenauer's Hopf algebra on permutations~\cite{MalvenutoReutenauer}, J.-L.~Loday and M.~Ronco's Hopf algebra on binary trees~\cite{LodayRonco}, G.~Chatel and V.~Pilaud Hopf algebra on Cambrian trees~\cite{ChatelPilaud}, and I.~Gelfand, D.~Krob, A.~Lascoux, B.~Leclerc, V.~S. Retakh, and J.-Y.~Thibon's algebra on binary sequences~\cite{GelfandKrobLascouxLeclercRetakhThibon}. In other words, we obtain an algebraic structure in which it is natural to multiply permutations with binary trees, or Cambrian trees with binary sequences. To keep our paper short, we omit the proofs of most statements as they are straightforward and similar to that of~\cite[Section~1.2]{ChatelPilaud}. %%%%%%%%%%%%%%% \subsection{The Hopf algebra on (decorated) permutations} \label{subsec:decoratedMRAlgebra} We briefly recall here the definition and some elementary properties of a decorated version of C.~Malvenuto and C.~Reutenauer's Hopf algebra on permutations~\cite{MalvenutoReutenauer}. For~$n,n' \in \N$, let \[ \fS^{(n,n')} \eqdef \set{\tau \in \fS_{n+n'}}{\tau_1 < \dots < \tau_n \text{ and } \tau_{n+1} < \dots < \tau_{n+n'}} \] denote the set of permutations of~$\fS_{n+n'}$ with at most one descent, at position~$n$. The \defn{shifted concatenation}~$\tau\bar\tau'$, the \defn{shifted shuffle}~$\tau \shiftedShuffle \tau'$, and the \defn{convolution}~$\tau \convolution \tau'$ of two permutations~$\tau \in \fS_n$ and~$\tau' \in \fS_{n'}$ are classically defined by \begin{gather*} \tau\bar\tau' \eqdef [\tau_1, \dots, \tau_n, \tau'_1 + n, \dots, \tau'_{n'} + n] \in \fS_{n+n'}, \\ \tau \shiftedShuffle \tau' \eqdef \bigset{(\tau\bar\tau') \circ \pi^{-1}}{\pi \in \fS^{(n,n')}} \qquad\text{and}\qquad \tau \convolution \tau' \eqdef \bigset{\pi \circ (\tau\bar\tau')}{\pi \in \fS^{(n,n')}}. \end{gather*} 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} \}, \\ {\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*} We also use the notation~$\underprod{\tau}{\tau'} = \tau\bar\tau'$ and~$\overprod{\tau}{\tau'} = \bar\tau'\tau$. As shown by J.-C.~Novelli and J.-Y.~Thibon in~\cite{NovelliThibon-decoratedFQSym}, these definitions extend to decorated permutations as follows. The \defn{decorated shifted shuffle}~$\tau \shiftedShuffle \tau'$ is defined as the shifted shuffle of the permutations where decorations travel with their values, while the \defn{decorated convolution}~$\tau \convolution \tau'$ is defined as the convolution of the permutations where decorations stay at their positions. For example, \begin{align*} \upr{1}\updownr{2} \shiftedShuffle \downb{2}{\blue 3}\upb{1} & = \{ \upr{1}\updownr{2}\downb{4}{\blue 5}\upb{3}, \upr{1}\downb{4}\updownr{2}{\blue 5}\upb{3}, \upr{1}\downb{4}{\blue 5}\updownr{2}\upb{3}, \upr{1}\downb{4}{\blue 5}\upb{3}\updownr{2}, \downb{4}\upr{1}\updownr{2}{\blue 5}\upb{3}, \downb{4}\upr{1}{\blue 5}\updownr{2}\upb{3}, \downb{4}\upr{1}{\blue 5}\upb{3}\updownr{2}, \downb{4}{\blue 5}\upr{1}\updownr{2}\upb{3}, \downb{4}{\blue 5}\upr{1}\upb{3}\updownr{2}, \downb{4}{\blue 5}\upb{3}\upr{1}\updownr{2} \}, \\ \upr{1}\updownr{2} \convolution \downb{2}{\blue 3}\upb{1} & = \{ \upr{1}\updownr{2}\downb{4}{\blue 5}\upb{3}, \upr{1}\updownr{3}\downb{4}{\blue 5}\upb{2}, \upr{1}\updownr{4}\downb{3}{\blue 5}\upb{2}, \upr{1}\updownr{5}\downb{3}{\blue 4}\upb{2}, \upr{2}\updownr{3}\downb{4}{\blue 5}\upb{1}, \upr{2}\updownr{4}\downb{3}{\blue 5}\upb{1}, \upr{2}\updownr{5}\downb{3}{\blue 4}\upb{1}, \upr{3}\updownr{4}\downb{2}{\blue 5}\upb{1}, \upr{3}\updownr{5}\downb{2}{\blue 4}\upb{1}, \upr{4}\updownr{5}\downb{2}{\blue 3}\upb{1} \}. \end{align*} Using these operations, we can define a decorated version of C.~Malvenuto and C.~Reutenauer's Hopf algebra on permutations~\cite{MalvenutoReutenauer}. \begin{definition} Let~$\FQSym_{\Decorations}$ be the Hopf algebra with basis~$(\F_\tau)_{\tau \in \fS_{\Decorations}}$ and whose product and coproduct are defined by \[ \F_\tau \product \F_{\tau'} = \sum_{\sigma \in \tau \shiftedShuffle \tau'} \F_\sigma \qquad\text{and}\qquad \coproduct \F_\sigma = \sum_{\sigma \in \tau \convolution \tau'} \F_\tau \otimes \F_{\tau'}. \] \end{definition} We now recall well-known properties of C.~Malvenuto and C.~Reutenauer's Hopf algebra on permutations which easily translate to similar properties of~$\FQSym_{\Decorations}$. \begin{proposition} \label{prop:productIntervalWeakOrder} A product of weak order intervals in~$\FQSym_{\Decorations}$ is a weak order interval: for any two weak order intervals~$[\mu, \omega] \subseteq \fS^\decoration$ and~$[\mu', \omega'] \subseteq \fS^{\decoration'}$, we have \[ \bigg( \sum_{\mu \le \tau \le \omega} \F_\tau \bigg) \product \bigg( \sum_{\mu' \le \tau' \le \omega'} \F_{\tau'} \bigg) = \sum_{\underprod{\mu}{\mu'} \le \sigma \le \overprod{\omega}{\omega'}} \F_\sigma, \] where~$\le$ denotes the weak order on~$\fS^{\decoration\decoration'}$. \end{proposition} \begin{corollary} \label{coro:multiplicativeBasesFQSym} For~$\tau \in \fS^\decoration$, define \[ \EFQSym^\tau = \sum_{\tau \le \tau'} \F_{\tau'} \qquad\text{and}\qquad \HFQSym^\tau = \sum_{\tau' \le \tau} \F_{\tau'} \] where~$\le$ is the weak order on~$\fS^\decoration$. Then~$(\EFQSym_\tau)_{\tau \in \fS}$ and~$(\HFQSym_\tau)_{\tau \in \fS}$ are multiplicative bases of~$\FQSym$: \[ \EFQSym^\tau \product \EFQSym^{\tau'} = \EFQSym^{\underprod{\tau}{\tau'}} \qquad\text{and}\qquad \HFQSym^\tau \product \HFQSym^{\tau'} = \HFQSym^{\overprod{\tau}{\tau'}}. \] A permutation~$\tau \in \fS^\decoration$ is $\EFQSym$-decomposable (resp.~$\HFQSym$-decomposable) if and only if there exists~${k \in [n-1]}$ such that~$\tau([k]) = [k]$ (resp.~such that~$\tau([k]) = [n] \ssm [k]$). Moreover, $\FQSym_{\Decorations}$ is freely generated by the elements~$\EFQSym^\tau$ (resp.~$\HFQSym^\tau$) for all $\EFQSym$-indecomposable (resp.~$\HFQSym$-indecomposable) decorated permutations~$\tau$. \end{corollary} We will also consider the dual Hopf algebra of~$\FQSym_{\Decorations}$, defined as follows. \begin{definition} Let~$\FQSym_{\Decorations}^*$ be the Hopf algebra with basis~$(\G_\tau)_{\tau \in \fS_{\Decorations}}$ and whose product and coproduct are defined by \[ \G_\tau \product \G_{\tau'} = \sum_{\sigma \in \tau \convolution \tau'} \G_\sigma \qquad\text{and}\qquad \coproduct \G_\sigma = \sum_{\sigma \in \tau \shiftedShuffle \tau'} \G_\tau \otimes \G_{\tau'}. \] \end{definition} %%%%%%%%%%%%%%% \subsection{Subalgebra} \label{subsec:subalgebra} We now construct a subalgebra of~$\FQSym_{\Decorations}$ whose basis is indexed by permutrees. Namely, let~$\PermutreeAlgebra$ be the vector subspace of~$\FQSym_{\Decorations}$ generated by the elements \[ \PPT_{\tree} \eqdef \sum_{\substack{\tau \in \fS_{\Decorations} \\ \PSymbol(\tau) = \tree}} \F_\tau = \sum_{\tau \in \linearExtensions(\tree)} \F_\tau, \] for all permutrees~$\tree$. For example, for the permutree of \fref{fig:leveledPermutree}\,(left), we have \[ \PPT_{\!\!\includegraphics{Tex}} = \F_{\up{2}\down{1}35\updown{4}\up{7}\down{6}} + \F_{\up{2}\down{1}35\up{7}\updown{4}\down{6}} + \F_{\up{2}\down{1}3\up{7}5\updown{4}\down{6}} + \dots + \F_{\up{7}5\up{2}3\down{1}\updown{4}\down{6}} + \F_{\up{7}5\up{2}3\updown{4}\down{1}\down{6}} + \F_{\up{7}5\up{2}3\updown{4}\down{6}\down{1}} \text{ (90 terms)}. \] The following statement is similar to~\cite[Theorem~24]{ChatelPilaud}, which was inspired from similar arguments for Hopf algebras arising from lattice quotients of the weak order~\cite{Reading-HopfAlgebras} and from rewriting rules in monoids~\cite{Priez}. \begin{theorem} \label{thm:permutreeSubalgebra} $\PermutreeAlgebra$ is a Hopf subalgebra of~$\FQSym_{\Decorations}$. \end{theorem} Once we have observed this property, it is interesting to describe the product and coproduct in the Hopf algebra~$\PermutreeAlgebra$ directly in terms of permutrees. We briefly do it in the next two statements. \para{Product} For any permutrees~$\tree, \tree'$, denote by~$\underprod{\tree}{\tree'}$ (resp.~by~$\overprod{\tree}{\tree'}$) the permutree obtained by grafting the rightmost outgoing (resp.~incoming) edge of~$\tree$ to the leftmost incoming (resp.~outgoing) edge of~$\tree'$ while shifting all labels of~$\tree'$. An example is given in \fref{fig:exampleProductCoproduct}\,(left). \begin{proposition} \label{prop:product} For any permutrees~$\tree, \tree'$, the product~$\PPT_{\tree} \product \PPT_{\tree'}$ is given by \[ \PPT_{\tree} \product \PPT_{\tree'} = \sum_{\tree[S]} \PPT_{\tree[S]}, \] where~$\tree[S]$ runs over the interval between~$\underprod{\tree}{\tree'}$ and~$\overprod{\tree}{\tree'}$ in the $\decoration(\tree)\decoration(\tree')$-permutree lattice. \end{proposition} \begin{figure}[H]%%Fig 17 \centerline{\includegraphics[scale=.65]{exampleProductCoproduct}} \caption{Grafting two permutrees (left) and cutting a permutree (right).} \label{fig:exampleProductCoproduct} \end{figure} \para{Coproduct} Define a \defn{cut} of a permutree~$\tree[S]$ to be a set~$\gamma$ of edges such that any geodesic vertical path in~$\tree[S]$ from a down leaf to an up leaf contains precisely one edge of~$\gamma$. Such a cut separates the permutree~$\tree[S]$ into two forests, one above~$\gamma$ and one below~$\gamma$, denoted~$A(\tree[S], \gamma)$ and~$B(\tree[S],\gamma)$, respectively. An example is given in \fref{fig:exampleProductCoproduct}\,(right). \begin{proposition} \label{prop:coproduct} For any permutree~$\tree[S]$, the coproduct~$\coproduct \PPT_{\tree[S]}$ is given by \[ \coproduct \PPT_{\tree[S]} = \sum_{\gamma} \bigg( \prod_{\tree \in B(\tree[S],\gamma)} \PPT_{\tree} \bigg) \otimes \bigg( \prod_{\tree' \in A(\tree[S], \gamma)} \PPT_{\tree'} \bigg), \] where~$\gamma$ runs over all cuts of~$\tree[S]$ and the products are computed from left to right. \end{proposition} \begin{example} Following Example~\ref{exm:permutreesSpecificDecorations}, let us underline relevant subalgebras of the permutree algebra~$\PermutreeAlgebra$. Namely, for any collection~$\Delta$ of decorations in~$\Decorations^*$ stable by shuffle, the linear subspace of~$\PermutreeAlgebra$ generated by the elements~$\PPT_\decoration$ for~$\decoration \in \Delta$ forms a subalgebra~$\PermutreeAlgebra_\Delta$ of~$\PermutreeAlgebra$. In particular, $\PermutreeAlgebra$ contains the subalgebras: \begin{enumerate}[(i)] \item $\PermutreeAlgebra_{\{\noneCirc{}\}^*}$ is C.~Malvenuto and C.~Reutenauer's Hopf algebra on permutations~\cite{MalvenutoReutenauer}, \item $\PermutreeAlgebra_{\{\downCirc{}\}^*}$ is J.-L.~Loday and M.~Ronco's Hopf algebra of on binary trees~\cite{LodayRonco}, \item $\PermutreeAlgebra_{\{\downCirc{}, \upCirc{}\}^*}$ is G.~Chatel and V.~Pilaud's Hopf algebra on Cambrian trees~\cite{ChatelPilaud}, \item $\PermutreeAlgebra_{\{\upDownCirc{}\}^*}$ is I.~Gelfand, D.~Krob, A.~Lascoux, B.~Leclerc, V.~S. Retakh, and \mbox{J.-Y.~Thibon's} algebra on binary sequences~\cite{GelfandKrobLascouxLeclercRetakhThibon}, \end{enumerate} as well as all algebras~$\PermutreeAlgebra_{D^*}$ for any subset~$D$ of the decorations~$\Decorations$. The dimensions of these algebras are given by the number of permutrees with decorations in~$D^*$, gathered in Table~\ref{table:factorialCatalanFamilies}. Interestingly, the rules for the product and the coproduct in the permutree algebra~$\PermutreeAlgebra$ provide uniform product and coproduct rules for all these Hopf algebras. \end{example} %%%%%%%%%%%%%%% \subsection{Quotient algebra} \label{subsec:quotientAlgebra} The next result is automatic by duality from Theorem~\ref{thm:permutreeSubalgebra}. \begin{theorem} The graded dual~$\PermutreeAlgebra^*$ of the permutree algebra~$\PermutreeAlgebra$ is the quotient of~$\FQSym_{\Decorations}^*$ under the permutree congruence~$\equiv$. The dual basis~$\QPT_{\tree}$ of~$\PPT_{\tree}$ is expressed as~$\QPT_{\tree} = \pi(\G_\tau)$, where~$\pi$ is the quotient map and~$\tau$ is any linear extension~of~$\tree$. \end{theorem} Similarly as in the previous section, we can describe combinatorially the product and coproduct of $\QPT$-basis elements of~$\PermutreeAlgebra^*$ in terms of operations on permutrees. \para{Product} Call \defn{gaps} the $n+1$ positions between two consecutive integers of~$[n]$, including the position before~$1$ and the position after~$n$. A gap~$\gamma$ defines a \defn{geodesic vertical path}~$\lambda(\tree,\gamma)$ in a permutree~$\tree$ from the bottom leaf which lies in the same interval of consecutive down labels as~$\gamma$ to the top leaf which lies in the same interval of consecutive up labels as~$\gamma$. See \fref{fig:exampleCoproductDual}. A multiset~$\Gamma$ of gaps therefore defines a \defn{lamination}~$\lambda(\tree,\Gamma)$ of~$\tree$, \ie a multiset of pairwise non-crossing geodesic vertical paths in~$\tree$ from down leaves to up leaves. When cut along the paths of a lamination, the permutree~$\tree$ splits into a forest. Consider two Cambrian trees~$\tree$ and~$\tree'$ on~$[n]$ and~$[n']$ respectively. For any shuffle~$s$ of their decorations~$\decoration$ and~$\decoration'$, consider the multiset~$\Gamma$ of gaps of~$[n]$ given by the positions of the down labels of~$\decoration'$ in~$s$ and the multiset~$\Gamma'$ of gaps of~$[n']$ given by the positions of the up labels of~$\decoration$ in~$s$. We denote by~$\tree \,{}_s\!\backslash \tree'$ the Cambrian tree obtained by connecting the up leaves of the forest defined by the lamination~$\lambda(\tree,\Gamma)$ to the down leaves of the forest defined by the lamination~$\lambda(\tree',\Gamma')$. \begin{example} \begin{figure}[H]%%Fig 18 \centerline{\includegraphics[scale=.65]{exampleProductDual}} \caption[Combinatorial interpretation of the product in the~$\QPT$-basis of~$\PermutreeAlgebra^*$.]{(a) The two initial permutrees~$\tree^\circDecoration$ and~$\tree^\squareDecoration$. (b) Given the shuffle $s = \noneSquare{}\upDownSquare{}\upDownCirc{}\downCirc{}\downSquare{}\upSquare{}\upCirc{}\downSquare{}$, the positions of the~\downSquare{} and~\upDownSquare{} are reported in~$\tree^\circDecoration$ and the positions of the~\upCirc{} and~\upDownCirc{} are reported in~$\tree^\squareDecoration$. (c) The corresponding laminations. (d) The permutrees are split according to the laminations. (e) The resulting permutree~$\tree^\circDecoration {}_s\!\backslash \tree^\squareDecoration$.} \label{fig:exampleProductDual} \end{figure} Consider the permutrees~$\tree^\circDecoration$ and~$\tree^\squareDecoration$ of \fref{fig:exampleProductDual}. To distinguish decorations in~$\tree^\circDecoration$ and~$\tree^\squareDecoration$, we circle the symbols in~$\decoration(\tree^\circDecoration) = \upDownCirc{}\downCirc{}\upCirc{}$ and square the symbols in~$\decoration(\tree^\squareDecoration) = \noneSquare{}\upDownSquare{}\downSquare{}\upSquare{}\downSquare{}$. Consider now an arbitrary shuffle~$s = \noneSquare{}\upDownSquare{}\upDownCirc{}\downCirc{}\downSquare{}\upSquare{}\upCirc{}\downSquare{}$ of these two decorations. The resulting laminations of~$\tree^\circDecoration$ and~$\tree^\squareDecoration$, as well as the permutree~$\tree^\circDecoration {}_s\!\backslash \tree^\squareDecoration$ are represented in \fref{fig:exampleProductDual}. \end{example} \begin{proposition} \label{prop:productDual} For any permutrees~$\tree, \tree'$, the product~$\QPT_{\tree} \product \QPT_{\tree'}$ is given by \[ \QPT_{\tree} \product \QPT_{\tree'} = \sum_s \QPT_{\tree \,{}_s\!\backslash \tree'}, \] where~$s$ runs over all shuffles of the decorations of~$\tree$ and~$\tree'$. \end{proposition} \para{Coproduct} For a gap~$\gamma$, we denote by~$L(\tree[S],\gamma)$ and~$R(\tree[S],\gamma)$ the left and right subpermutrees of~$\tree[S]$ when split along the path~$\lambda(\tree[S], \gamma)$. An example is given in \fref{fig:exampleCoproductDual}. \begin{figure}[H]%%Fig 19 \centerline{\includegraphics[scale=.7]{exampleCoproductDual}} \caption{A gap~$\gamma$ between~$3$ and~$4$ (left) defines a vertical cut (middle) which splits the permutree vertically (right).} \label{fig:exampleCoproductDual} \end{figure} \begin{proposition} \label{prop:coproductDual} For any permutree~$\tree[S]$, the coproduct~$\coproduct\QPT_{\tree[S]}$ is given by \[ \coproduct\QPT_{\tree[S]} = \sum_{\gamma} \QPT_{L(\tree[S],\gamma)} \otimes \QPT_{R(\tree[S],\gamma)}, \] where~$\gamma$ runs over all gaps between vertices of~$\tree[S]$. \end{proposition} %%%%%%%%%%%%%%% \subsection{Further algebraic topics} \label{subsec:furtherAlgebraicTopics} To conclude this section, we explore some more advanced properties of the permutree algebra. %%% \subsubsection{Multiplicative bases and indecomposable elements} For a permutree~$\tree$, define \[ \EPT^{\tree} \eqdef \sum_{\tree \le \tree'} \PPT_{\tree'} \qquad\text{and}\qquad \HPT^{\tree} \eqdef \sum_{\tree' \le \tree} \PPT_{\tree'}. \] The next statement follows from Corollary~\ref{coro:multiplicativeBasesFQSym} and Proposition~\ref{prop:product}. \begin{proposition} $(\EPT^{\tree})_{\tree \in \Permutrees}$ and~$(\HPT^{\tree})_{\tree \in \Permutrees}$ are multiplicative bases of~$\Permutrees$: \[ \EPT^{\tree} \product \EPT^{\tree'} = \EPT^{\underprod{\tree}{\tree'}} \qquad\text{and}\qquad \HPT^{\tree} \product \HPT^{\tree'} = \HPT^{\overprod{\tree}{\tree'}}. \] \end{proposition} We now consider decomposition properties of permutrees. Since the $\EPT$- and $\HPT$-bases have similar properties, we focus on the $\EPT$-basis and invite the reader to translate the following properties to the $\HPT$-basis. %\break \begin{proposition} The following properties are equivalent for a permutree~$\tree[S]$: \begin{enumerate}[(i)] \item $\EPT^{\tree[S]} = \EPT^{\tree} \product \EPT^{\tree'}$ for non-empty permutrees~$\tree, \tree'$; \label{enum:decomposable} \item $\edgecut{[k]}{[n] \ssm [k]}$ is an edge cut of~$\tree[S]$ for some~$k \in [n-1]$; \label{enum:cut} \item at least one linear extension~$\tau$ of~$\tree[S]$ is decomposable, meaning that $\tau([k]) = [k]$ for some \mbox{$k \in [n]$}. \label{enum:perm} \end{enumerate} We say that~$\tree[S]$ is \defn{$\EPT$-decomposable} and that the edge cut~$\edgecut{[k]}{[n] \ssm [k]}$ is \defn{splitting}. \end{proposition} We are interested in $\EPT$-indecomposable elements. We first understand the behavior of decomposability under rotations. \begin{lemma} \label{lem:rotationIndecomposable} Let~$\tree$ be a $\decoration$-permutree, let~$i \to j$ be an edge of~$\tree$ with~$i < j$, and let~$\tree'$ be the $\decoration$-permutree obtained by rotating~$i \to j$ in~$\tree$. Then \begin{enumerate}[(i)] \item if~$\tree$ is $\EPT$-indecomposable, then so is~$\tree'$; \item if~$\tree$ is $\EPT$-decomposable while~$\tree'$ is not, then~$\decoration_i \ne \downCirc{}$ or~$i = 1$, and~$\decoration_j \ne \upCirc{}$ or~$j = n$. \end{enumerate} \end{lemma} \begin{proof} Denote by~$\up{L}$ and~$\down{L}$ (resp.~$\up{R}$ and~$\down{R}$) the index sets of the left (resp.~right) ancestor and descendant subtrees of~$i$ (resp.~of~$j$) in~$\tree$ and~$\tree'$ (using~$\varnothing$ if there is no such subtree), and let~$U$ and~$D$ denote the ancestor and descendant subtrees as in \fref{fig:rotation}. The main observation is that the two permutrees~$\tree$ and~$\tree'$ have the same cuts except the cut corresponding to the edge between~$i$ and~$j$. More precisely, the cut~$C \eqdef \edgecut{\{i\} \cup \down{L} \cup \up{L} \cup D}{\{j\} \cup \down{R} \cup \up{R} \cup U}$ in~$\tree$ is replaced by the cut~$C' \eqdef \edgecut{\{j\} \cup \down{R} \cup \up{R} \cup D}{\{i\} \cup \down{L} \cup \up{L} \cup U}$ in~$\tree'$. Since~$i < j$, the cut~$C'$ cannot be splitting, so that~$\tree'$ is automatically $\EPT$-indecomposable when~$\tree$ is $\EPT$-indecomposable. Assume now that~$\tree$ is $\EPT$-decomposable while~$\tree'$ is not and that~$\decoration_i = \downCirc{}$. Then the cut~$C$ is splitting so that ${\{i\} \cup \down{L} \cup D \ll \{j\} \cup \down{R} \cup \up{R} \cup U}$ (where~$X \ll Y$ means that~$x < y$ for all~$x \in X$ and~$y \in Y$). But~$\down{L} \ll \{i\} \ll D$ since~$\decoration_i = \downCirc{}$. Therefore~$\down{L} \ll \{i,j\} \cup \down{R} \cup \up{R} \cup D \cup U$. Since~$\tree'$ is $\EPT$-indecomposable, this implies that~$\down{L} = \varnothing$ since otherwise the cut~$\edgecut{\down{L}}{\{i,j\} \cup \down{R} \cup \up{R} \cup D \cup U}$ of~$\tree'$ would be splitting. Therefore, $i = 1$. We prove similarly that~$\decoration_j = \upCirc{}$ implies~$j = n$. \end{proof} \begin{corollary} The set of $\EPT$-indecomposable $\decoration$-permutrees is an upper ideal of the $\decoration$-permutree lattice. \end{corollary} \begin{remark} Note that contrarily to the Cambrian algebra, this ideal is not primitive in general. For example, the ideal of $\decoration$-permutrees for the decoration~$\decoration = \downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}\noneCirc{}\downCirc{}\upCirc{}$ illustrated in \fref{fig:leveledPermutree} is generated by the~$4$ permutrees illustrated in \fref{fig:indecomposableGenerators}. \begin{figure}[H]%%Fig 20 \centerline{\includegraphics[scale=.7]{indecomposableGenerators}} \caption{The four generators of the upper ideal of $\EPT$-indecomposable \mbox{$\decoration$-permutrees} for the decoration~$\decoration = \downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}\noneCirc{}\downCirc{}\upCirc{}$.} \label{fig:indecomposableGenerators} \end{figure} \end{remark} %%% \subsubsection{Dendriform structures} Dendriform algebras were introduced by J.-L.~Loday in~\cite[Chap.~5]{Loday-dialgebras}. In a dendriform algebra, the product~$\product$ is decomposed into two partial products~${\product} = {\prec} + {\succ}$ satisfying: \begin{align*} \sfx \prec \big(\sfy \product \sfz \big) & = \big(\sfx \prec \sfy \big) \prec \sfz, \\ \sfx \succ \big(\sfy \prec \sfz \big) & = \big(\sfx \succ \sfy \big) \prec \sfz, \\ \sfx \succ \big(\sfy \succ \sfz \big) & = \big(\sfx \product \sfy \big) \succ \sfz. \end{align*} The shuffle product on permutations can be decomposed into~$\shiftedShuffle = {\prec} + {\succ}$ where for~$\tau = \sigma\tau_n$ and~$\tau' = \sigma'\tau'_{n'}$ we have \[ \tau \prec \tau' \eqdef (\sigma \shiftedShuffle \tau') \tau_n \qquad\text{and}\qquad \tau \succ \tau' \eqdef (\tau \shiftedShuffle \sigma') \bar\tau'_{n'}. \] This endows C.~Malvenuto and C.~Reutenauer's algebra on permutations with a dendriform algebra structure defined on the $\F$-basis by \[ \F_\tau \prec \F_{\tau'} = \sum_{\sigma \in \tau \prec \tau'} \F_\sigma \qquad\text{and}\qquad \F_\tau \succ \F_{\tau'} = \sum_{\sigma \in \tau \succ \tau'} \F_\sigma. \] It turns out that some subalgebras of the permutree algebra are stable under these dendriform operations~$\prec$ and~$\succ$. \begin{proposition} \label{prop:dendriform} For any subset~$\Delta$ of~$\{\noneCirc{}, \downCirc{}\}^*$ stable by shuffle, the subalgebra of the permutree algebra~$\PermutreeAlgebra$ generated by~$\set{\PPT_{\tree}}{\tree \in \Permutrees(\decoration), \; \decoration \in \Delta}$ is stable by the dendriform operations~$\prec$ and~$\succ$. \end{proposition} \begin{proof} Let~$\decoration \in \{\noneCirc{}, \downCirc{}\}^n$ and~$\decoration' \in \{\noneCirc{}, \downCirc{}\}^{n'}$, let~$\tree \in \Permutrees(\decoration)$ and~$\tree' \in \Permutrees(\decoration')$, and let~$\tau = \sigma\tau_n \in \fS_\decoration$ and~$\tau' = \sigma'\tau'_{n'} \in \fS_{\decoration'}$ be such that~$\tree = \PSymbol(\tau)$ and~$\tree' = \PSymbol(\tau')$. Then \[ \PPT_{\tree} \prec \PPT_{\tree'} = \sum_{\PSymbol(\sigma\bar\tau'\tau_n) \le \tree[S] \le \overprod{\tree}{\tree'}} \PPT_{\tree[S]} \qquad\text{and}\qquad \PPT_{\tree} \succ \PPT_{\tree'} = \sum_{\underprod{\tree}{\tree'} \le \tree[S] \le \PSymbol(\bar\sigma'\tau\bar\tau'_{n'})} \PPT_{\tree[S]}. \] Indeed, $\PPT_{\tree} \prec \PPT_{\tree'}$ is the sum of~$\F_\sigma$ for~$\tau\bar\tau' \le \sigma \le \bar\tau'\tau$ such that~$\sigma_{n+n'} = \tau_n$. These permutations are exactly all linear extensions of the trees~$\tree[S]$ such that~${\underprod{\tree}{\tree'} \le \tree[S] \le \overprod{\tree}{\tree'}}$ whose root is~$\tau_n$. Therefore, $\PPT_{\tree} \prec \PPT_{\tree'}$ is the sum of~$\PPT_{\tree[S]}$ for all these trees. Similarly, $\PPT_{\tree} \succ \PPT_{\tree'}$ is the sum of~$\PPT_{\tree[S]}$ for the trees~$\tree[S]$ such that~$\underprod{\tree}{\tree'} \le \tree[S] \le \overprod{\tree}{\tree'}$ whose root is~$\bar\tau'_{n'}$. \end{proof} \begin{remark} Note that the assumption that~$\Delta \subset \{\noneCirc{}, \downCirc{}\}^*$ in Proposition~\ref{prop:dendriform} is necessary. For example, we have \[ \PPT_{\includegraphics{permutreeVee}} \prec \PPT_{\!\!\includegraphics{permutreeWedge}} = (\F_{\up{2}13} + \F_{\up{2}31}) \prec (\F_{13\down{2}} + \F_{31\down{2}}) \] contains~$\F_{\up{2}346\down{5}1}$ but not~$\F_{\up{2}3461\down{5}}$ although~$\PSymbol(\up{2}346\down{5}1) = \PSymbol(\up{2}3461\down{5})$. \end{remark} %%% \subsubsection{Integer point transform} We now show that the product of two permutrees can be interpreted in terms of their integer point transforms. This leads to relevant equalities for permutrees with decorations in~$\{\noneCirc{}, \downCirc{}\}$. \begin{definition} The \defn{integer point transform}~$\integerPointTransform_S$ of a subset~$S$ of~$\R^n$ is the multivariate generating function of the integer points inside~$S$: \[ \integerPointTransform_S(t_1, \dots, t_n) = \sum_{(i_1, \dots, i_n) \in \Z^n \cap S} t_1^{i_1} \cdots t_n^{i_n}. \] \end{definition} For a permutree~$\tree$, we denote by~$\integerPointTransform_{\tree}$ the integer point transform of the cone \[ \Cone\blackPolar(\tree) \eqdef \set{\b{x} \in \R_+^n}{\begin{array}{c} x_i \le x_j \text{ for any edge } i \to j \text{ of } \tree \text{ with } i < j \\ x_i < x_j \text{ for any edge } i \to j \text{ of } \tree \text{ with } i > j \end{array}}. \] Note that this cone differs from the cone~$\Cone\polar(\tree)$ defined in Section~\ref{subsec:permutreeFans} in two ways: first it leaves in~$\R_+^n$ and not in~$\HH$, second it excludes the facets of~$\Cone\polar(\tree)$ corresponding to the decreasing edges of~$\tree$ (\ie the edges~$i \to j$ with~$i > j$). We denote by~$\integerPointTransform_\tau$ the integer point transform of the chain~$\tau_1 \to \cdots \to \tau_n$ for a permutation~$\tau \in \fS_n$. The following statements are classical. \begin{proposition}\label{prop:integerPointTransform} \begin{enumerate}[(i)] \item For any permutation~$\tau \in \fS_n$, the integer point transform~$\integerPointTransform_\tau$ is given by \[ \integerPointTransform_\tau(t_1, \dots, t_n) = \bigg( \prod\limits_{i \in [n]} \big( 1 - t_{\tau_i} \cdots t_{\tau_n} \big)^{-1} \bigg) \bigg( \prod_{\substack{i \in [n-1] \\ \tau_i > \tau_{i+1}}} t_{\tau_i+1} \cdots t_{\tau_n} \bigg). \] \label{item:integerPointTransformPermutation} \item The integer point transform of a permutree~$\tree$ is given by~$\integerPointTransform_{\tree} = \sum_{\tau \in \linearExtensions(\tree)} \integerPointTransform_\tau$, where the sum runs over the set~$\linearExtensions(\tree)$ of linear extensions of~$\tree$. \label{item:integerPointTransformLinearExtensions} \item The product of the integer point transforms~$\integerPointTransform_\tau$ and~$\integerPointTransform_{\tau'}$ of two permutations~${\tau \in \fS_n}$ and~${\tau' \in \fS_{n'}}$ is given by the shifted shuffle \[ \integerPointTransform_\tau(t_1, \dots, t_n) \product \integerPointTransform_{\tau'}(t_{n+1}, \dots, t_{n+n'}) = \sum_{\sigma \in \tau \shiftedShuffle \tau'} \integerPointTransform_\sigma(t_1, \dots, t_{n+n'}). \] In other words, the linear map from~$\FQSym$ to the rational functions defined by $\Psi\colon \F_\tau \mapsto \integerPointTransform_\tau$ is an algebra morphism. \label{item:integerPointTransformProduct} \end{enumerate} \end{proposition} \begin{proof} For Point~\eqref{item:integerPointTransformPermutation}, observe that the cone~$\set{\b{x} \in \R_+^n}{x_{\tau_i} \le x_{\tau_{i+1}} \text{ for all } i \in [n-1]}$ is generated by the vectors~$\b{e}_{\tau_i} + \cdots + \b{e}_{\tau_n}$, for~$i \in [n]$, which form a (unimodular) basis of the lattice~$\Z^n$. A straightforward inductive argument shows that the integer point transform of the cone $\set{\b{x} \in \R_+^n}{x_{\tau_i} \le x_{\tau_{i+1}} \text{ for all } i \in [n-1]}$ is thus given by~$\prod_{i \in [n]} \big( 1- t_{\tau_i} \cdots t_{\tau_n} \big)^{-1}$. The second product of~$\integerPointTransform_\tau$ is then given by the facets which are excluded from the cone~$\Cone\blackPolar(\tau)$. Point~\eqref{item:integerPointTransformLinearExtensions} follows from the fact that the cone~$\Cone\blackPolar(\tree)$ is partitioned by the cones~$\Cone\blackPolar(\tau)$ for the linear extensions~$\tau$ of~$\tree$. Finally, the product~$\integerPointTransform_\tau(t_1, \dots, t_n) \product \integerPointTransform_{\tau'}(t_{n+1}, \dots, t_{n+n'})$ is the integer point transform of the poset formed by the two disjoint chains~$\tau$ and~$\bar\tau'$, whose linear extensions are precisely the permutations which appear in the shifted shuffle of~$\tau$ and~$\tau'$. This shows Point~\eqref{item:integerPointTransformProduct}. \end{proof} It follows from Proposition~\ref{prop:integerPointTransform} that the product of the integer point transforms of two permutrees behaves as the product in the permutree algebra~$\PermutreeAlgebra$. \begin{corollary} For any two permutrees~$\tree \in \Permutrees(n)$ and~$\tree' \in \Permutrees(n')$, we have \[ \integerPointTransform_{\tree}(t_1, \dots, t_n) \product \integerPointTransform_{\tree'}(t_{n+1}, \dots, t_{n+n'}) = \sum_{\underprod{\tree}{\tree'} \, \le \, \tree[S] \, \le \, \overprod{\tree}{\tree'}} \integerPointTransform_{\tree[S]}(t_1, \dots, t_{n+n'}). \] \end{corollary} \begin{proof} Omitting the variables~$(t_1, \dots, t_{n+n'})$ for concision, we have \[ \integerPointTransform_{\tree} \product \integerPointTransform_{\tree'} = \Psi(\PPT_{\tree}) \product \Psi(\PPT_{\tree'}) = \Psi(\PPT_{\tree} \cdot \PPT_{\tree'}) = \Psi \bigg( \sum_{\tree[S]} \PPT_{\tree[S]} \bigg) = \sum_{\tree[S]} \Psi(\PPT_{\tree[S]}) = \sum_{\tree[S]} \integerPointTransform_{\tree[S]}, \] where the sums run over the increasing flip interval~$[\underprod{\tree}{\tree'}, \overprod{\tree}{\tree'}]$. \end{proof} Finally, we specialize this result to permutrees with decorations in~$\{\noneCirc{}, \upCirc{}\}^*$. The main observation is the following. \begin{proposition} The integer point transform of any permutree~$\tree$ with decoration in~$\{\noneCirc{}, \upCirc{}\}^*$ is given by \[ \integerPointTransform_{\tree}(t_1, \dots, t_n) = \bigg( \prod_{\edgecut{I}{J} \in \cuts(\tree)} \big( 1-\prod_{j \in J} t_j \big)^{-1} \bigg) \bigg( \prod_{\edgecut{I}{J} \in \decreasingCuts(\tree)} \; \prod_{j \in J} t_j \bigg), \] where~$\cuts(\tree)$ denotes the set of all edge cuts of~$\tree$ (including~$\edgecut{\varnothing}{[n]}$) and $\decreasingCuts(\tree)$ denotes the decreasing edge cuts of~$\tree$, \ie those of edges~$i \to j$ with~$i > j$. \end{proposition} \begin{proof} Consider the cone~$C$ defined by the inequalities~$0 \le x_i$ for all~$i \in [n]$ and~${x_i \le x_j}$ for all edges~$i \to j$ in~$\tree$. As the decoration of~$\tree$ is in~$\{\noneCirc{}, \upCirc{}\}^*$, the tree~$\tree$ is naturally rooted at its bottommost vertex~$r$. Since there is a path from~$r$ to any other vertex~$v$, the inequalities~$0 \le x_r$ and~$x_i \le x_j$ for all edges~$i \to j$ in~$\tree$ already imply all other inequalities~$0 \le x_i$ for~${i \in [n] \ssm \{r\}}$. We therefore obtain that the cone~$C$ is defined by~$n$ inequalities and thus is simplicial. Moreover, we easily check that the rays of~$C$ are given by the characteristic vectors~$\sum_{j \in J} \b{e}_j$ for all edge cuts~$\edgecut{I}{J} \in \cuts(\tree)$, including the vector~$\one$ for the artificial edge cut~$\edgecut{\varnothing}{[n]}$. We obtain that the integer point transform of~$C$ is~$\prod_{\edgecut{I}{J} \in \cuts(\tree)} \big( 1-\prod_{j \in J} t_j \big)^{-1}$. Finally, the second product of~$\integerPointTransform_{\tree}$ is given by the facets which are excluded from~$C$ to obtain~$\Cone\blackPolar(\tree)$. \end{proof} \begin{corollary} For any permutrees~$\tree \in \Permutrees(n)$ and~$\tree' \in \Permutrees(n')$ with decorations in~$\{\noneCirc{}, \upCirc{}\}^*$, we have \[ \frac{\prod\limits_{\edgecut{I}{J} \in \decreasingCuts(\tree)} \; \prod\limits_{j \in J} t_j}{\prod\limits_{\edgecut{I}{J} \in \cuts(\tree)} \big( 1-\prod\limits_{j \in J} t_j \big)} \cdot \frac{\prod\limits_{\edgecut{I}{J} \in \decreasingCuts(\tree')} \; \prod\limits_{j \in J} t_{n+j}}{\prod\limits_{\edgecut{I}{J} \in \cuts(\tree')} \big( 1-\prod\limits_{j \in J} t_{n+j} \big)} = \sum_{\tree[S]} \frac{\prod\limits_{\edgecut{I}{J} \in \decreasingCuts(\tree[S])} \; \prod\limits_{j \in J} t_j}{\prod\limits_{\edgecut{I}{J} \in \cuts(\tree[S])} \big( 1-\prod\limits_{j \in J} t_j \big)}, \] where~$\tree[S]$ ranges over the permutree lattice interval~$[\underprod{\tree}{\tree'}, \overprod{\tree}{\tree'}]$. \end{corollary} \begin{example} For example, we have the following equality of rational functions: \begin{align*} \integerPointTransform_{\includegraphics{exmPermutreeIPT1}} \cdot \integerPointTransform_{\includegraphics{exmPermutreeIPT2}} = & \; (1-x_1)^{-1}x_1 (1-x_3)^{-1} (1-x_1x_2x_3)^{-1} \cdot (1-x_4)^{-1} \\[-.2cm] = & \quad\; (1-x_1)^{-1}x_1 (1-x_3x_4)^{-1} (1-x_4)^{-1} (1-x_1x_2x_3x_4)^{-1} \\ & + (1-x_1)^{-1}x_1 (1-x_3x_4)^{-1} (1-x_3)^{-1}x_3 (1-x_1x_2x_3x_4)^{-1} \\ & + (1-x_1x_2x_3)^{-1}x_1x_2x_3 (1-x_1)^{-1}x_1 (1-x_3)^{-1} (1-x_1x_2x_3x_4)^{-1} \\[.1cm] = & \; \integerPointTransform_{\includegraphics{exmPermutreeIPT3}} + \integerPointTransform_{\includegraphics{exmPermutreeIPT4}} + \integerPointTransform_{\includegraphics{exmPermutreeIPT5}}. \end{align*} \end{example} \begin{remark} The simple product formula for the integer point transform~$\integerPointTransform_{\tree}$ does not hold for an arbitrary permutree~$\tree$. Indeed, the cone~$\Cone\blackPolar(\tree)$ is not always simplicial. \vspace{-.05cm} For example,~$\Cone\blackPolar(\raisebox{-.2cm}{\includegraphics{permutreeWedge}}\vspace{-.1cm})$ is generated by the vectors~$[0,1,0], [0,1,1], [1,1,0], [1,1,1]$, where the first is not the characteristic vector~$\sum_{j \in J} \b{e}_j$ for an edge cut~$\edgecut{I}{J}$ of~$\raisebox{-.2cm}{\includegraphics{permutreeWedge}}$. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Schr\"oder permutrees} \label{sec:SchroderPermutrees} This section is devoted to Schr\"oder permutrees which correspond to the faces of the permutreehedra. It is largely inspired from the presentation of~\cite[Part 3]{ChatelPilaud}. %%%%%%%%%%%%%%% \subsection{Schr\"oder permutrees} \label{subsec:SchroderPermutrees} We now focus on the following family of trees. \begin{definition} \label{def:SchroderPermutrees} For~$\decoration \in \Decorations^n$ and~$X \subseteq [n]$, let \[ X^\vee \eqdef \set{x \in X}{\decoration_x \in \{\upCirc{}, \upDownCirc{}\}} \qquad\text{and}\qquad X_\wedge \eqdef \set{x \in X}{\decoration_x \in \{\downCirc{}, \upDownCirc{}\}}. \] A \defn{Schr\"oder $\decoration$-permutree} is a directed tree~$\tree[S]$ with vertex set~$\ground$ endowed with a vertex labeling~${p : \ground \to 2^{[n]} \ssm \varnothing}$ such that \begin{enumerate}[(i)] \item the labels of~$\tree[S]$ partition~$[n]$, \ie $v \ne w \implies p(v) \cap p(w) = \varnothing$ and~${\bigcup_{v \in \ground} p(v) = [n]}$; \item each vertex~$v \in \ground$ has one incoming (resp.~outgoing) subtree~$\tree[S]^v_I$ (resp.~$\tree[S]_v^I$) for each interval~$I$ of~${[n] \ssm p(v)_\wedge}$ (resp.~of~$[n] \ssm p(v)^\vee$) and all labels of~$\tree[S]^v_I$ (resp.~of~$\tree[S]_v^I$) are subsets of~$I$. \end{enumerate} For~$\decoration \in \Decorations^n$, we denote by~$\SchrPermutrees(\decoration)$ the set of Schr\"oder $\decoration$-permutrees, and we let~$\SchrPermutrees(n) \eqdef \bigsqcup_{\decoration \in \Decorations^n} \SchrPermutrees(\decoration)$ and $\SchrPermutrees \eqdef \bigsqcup_{n \in \N} \SchrPermutrees(n)$. \end{definition} \begin{definition} A \defn{$k$-leveled Schr\"oder $\decoration$-permutree} is a directed tree with vertex set~$\ground$ endowed with two labelings~$p : \ground \to 2^{[n]} \ssm \varnothing$ and~$q : \ground \to [k]$ which respectively define a Schr\"oder $\decoration$-permutree and an increasing tree (meaning that $q$ is surjective and~$v \to w$ in~$\tree[S]$ implies that~$q(v) < q(w)$). \end{definition} \fref{fig:leveledSchroderPermutree} illustrates a Schr\"oder permutree and a $3$-leveled Schr\"oder permutree. For example, for the node~$v$ labelled by~$p(v) = \{4,6\}$, we have~$p(v)_\wedge = \{4,6\}$ so that~$[7] \ssm p(v)_\wedge = \{1,2,3\} \sqcup \{5\} \sqcup \{7\}$ and~$v$ has $3$ incoming subtrees and~$p(v)_\vee = \{4\}$ so that~$[7] \ssm p(v)_\vee = \{1,2,3\} \sqcup \{5,6,7\}$ and~$v$ has~$2$ outgoing subtrees. Note that each level of a $k$-leveled Schr\"oder permutree may contain more than one node. \begin{figure}[H]%%Fig 21 \centerline{\includegraphics[scale=.7]{leveledSchroderPermutree}} \caption{A Schr\"oder permutree (left), an increasing tree (middle), and a $3$-leveled Schr\"oder permutree (right).} \label{fig:leveledSchroderPermutree} \end{figure} \begin{example} Following Example~\ref{exm:permutreesSpecificDecorations}, observe that Schr\"oder $\decoration$-permutrees specialize to classical families of combinatorial objects: \begin{enumerate}[(i)] \item Schr\"oder $\noneCirc{}^n$-permutrees are in bijection with \defn{ordered partitions} of~$[n]$, \ie with sequences $\lambda \eqdef \lambda_1 \sep \lambda_2 \sep \dots \sep \lambda_{k-1} \sep \lambda_k$ where~$\lambda_i \subseteq [n]$ are such that~$\bigcup_{i \in [k]} \lambda_i = [n]$ and \mbox{$\lambda_i \cap \lambda_j = \varnothing$} for~$i \ne j$. \item Schr\"oder $\downCirc{}^n$-permutrees are precisely \defn{Schr\"oder trees}, \ie planar rooted trees where each node has at least two children. \item Schr\"oder $\decoration$-permutrees for~$\decoration \in \{\upCirc{}, \downCirc{}\}$ are Schr\"oder Cambrian trees~\cite[Section 3.1]{ChatelPilaud}. \item Schr\"oder $\upDownCirc{}^n$-permutrees correspond to ternary sequences of length~${n-1}$. \end{enumerate} \fref{fig:orderedPartitionsSchroderTreesSchroderCambrianTreesTernarySequences} illustrates these families represented as Schr\"oder permutrees. In this section, we provide a uniform treatment of these families. \begin{figure}[H]%%Fig 22 \centerline{\includegraphics[scale=.7]{orderedPartitionsSchroderTreesSchroderCambrianTreesTernarySequences}} \caption{Leveled Schr\"oder permutrees corresponding to an ordered partition (left), a leveled Schr\"oder tree (middle left), a leveled Schr\"oder Cambrian tree (middle right), and a leveled ternary sequence (right).} \label{fig:orderedPartitionsSchroderTreesSchroderCambrianTreesTernarySequences} \end{figure} \end{example} \begin{remark} Similar to Remark~\ref{rem:234angulations}, Schr\"oder $\decoration$-permutrees are dual trees of dissections of~$\b{P}_\decoration$, that is, non-crossing sets of arcs in~$\b{P}_\decoration$ (as defined in Remark~\ref{rem:234angulations}). See \fref{fig:234angulationSchroder} for an illustration. Note that contracting an edge in a Schr\"oder permutree corresponds to deleting an arc in its dual dissection. \begin{figure}[H] %%Fig 23 \centerline{\includegraphics[scale=.7]{234angulationSchroder}} \caption{Schr\"oder permutrees (left) and dissections (right) are dual to each other.} \label{fig:234angulationSchroder} \end{figure} \end{remark} We will need the following statement in the next section. \begin{lemma} Schr\"oder $\decoration$-permutrees are stable by edge contraction. \end{lemma} \begin{proof} Let~$e = v \to w$ be an edge in a Schr\"oder $\decoration$-permutree~$\tree[S]$, and let~$\tree[S]/e$ be the tree obtained by contraction of~$e$, where the contracted vertex $vw$ gets the label~${p(vw) = p(v) \cup p(w)}$. Condition~(i) of Definition~\ref{def:SchroderPermutrees} is clearly satisfied. For Condition~(ii), let~$I_1, \dots, I_p$ be the intervals of~$[n] \ssm p(w)_\wedge$, where~$I_i$ is the interval which contains~$p(v)$, and let~$J_1, \dots, J_q$ be the intervals of~$[n] \ssm p(v)_\wedge$. Observe that for all~$j \in [q]$, all labels of~$\tree[S]^v_{J_j}$ are all included in~$I_i$ (because~$\tree[S]^v_{J_j}$ belongs to~$\tree[S]^w_{I_i}$) and in~$J_j$. Therefore, the descendant subtrees~$\tree[S]^w_{I_1}, \dots, \tree[S]^w_{I_{i-1}}, \tree[S]^v_{J_1}, \dots, \tree[S]^v_{J_q}, \tree[S]^w_{I_{i+1}}, \dots, \tree[S]^w_{I_p}$ of~$vw$ in~$\tree[S]/e$ indeed belong to the intervals~$I_1, \dots, I_{i-1}, I_i \cap J_1, \dots, I_i \cap J_q, I_{i+1}, \dots, I_p$ of~$[n] \ssm p(vw)$. The proof is similar for ancestor subtrees of~$vw$ in~$\tree[S]/e$. The other vertices of~$\tree[S]/e$ have not changed locally. \end{proof} Let~$\tree[S], \tree[S]'$ be two Schr\"oder $\decoration$-permutrees. We say that~$\tree[S]$ \defn{refines}~$\tree[S]'$ if~$\tree[S]'$ can be obtained from~$\tree[S]$ by contraction of some edges. %%%%%%%%%%%%%%% \subsection{Faces} \label{subsec:faces} Consider a Schr\"oder permutree~$\tree[S]$. For~$i,j \in [n]$, we write~$i \to j$ if there are vertices~$v,w$ of~$\tree[S]$ such that~$i \in p(v)$, $j \in p(w)$ and~$v = w$ or~$v \to w$ is an edge in~$\tree[S]$. We say that~$\edgecut{I}{J}$ is an edge cut of~$\tree[S]$ if~$I$ (resp.~$J$) is the union of all labels of the vertices in the source (resp.~sink) set of an edge of~$\tree[S]$. Define the \defn{braid cone}~$\Cone\polar(\tree[S])$ of~$\tree[S]$ as the cone \begin{align*} \Cone\polar(\tree[S]) & \eqdef \set{\b{x} \in \HH}{x_i \le x_j \text{ for any } i \to j \text{ in } \tree[S]} \\ & = \cone \biggset{\sum_{j \in J} \b{e}_j}{\text{for all edge cuts } \edgecut{I}{J} \text{ of } \tree[S]}. \end{align*} \begin{proposition} \label{prop:fan} The map~$\tree[S] \mapsto \Cone\polar(\tree[S])$ is a lattice homomorphism from the refinement lattice on Schr\"oder $\decoration$-permutrees to the inclusion lattice on the cones of the $\decoration$-permutree fan~$\Fan$. In particular, \[ \Fan = \set{\Cone\polar(\tree[S])}{\tree[S] \text{ Schr\"oder $\decoration$-permutree}}. \] \end{proposition} \begin{proof} Contracting an edge~$v \to w$ in~$\tree[S]$ corresponds to forcing the inequalities~$x_i \le x_j$ to become equalities~$x_i = x_j$ for~$i \in p(v)$ and~$j \in p(w)$. Reciprocally, since the cone~$\Cone\polar(\tree[S])$ is simplicial, its faces are obtained by forcing some of its inequalities to become equalities, which corresponds to contracting some edges in~$\tree[S]$. The result immediately follows. \end{proof} \begin{proposition} For any Schr\"oder $\decoration$-permutree~$\tree[S]$, the set \[ \face(\tree[S]) \eqdef \conv\set{\b{a}(\tree)}{\tree \; \decoration\text{-permutree refining } \tree[S]}= \bigcap_{\edgecut{I}{J} \text{ cut of } \tree[S]} \HS(I) \] is a face of the $\decoration$-permutreehedron~$\Permutreehedron$. Moreover, the map~$\tree[S] \mapsto \face(\tree[S])$ is a lattice homomorphism from the refinement lattice on Schr\"oder $\decoration$-permutrees to the face lattice of the $\decoration$-permutreehedron~$\Permutreehedron$. \end{proposition} \begin{proof} Since the normal fan of the $\decoration$-permutreehedron~$\Permutreehedron$ is the $\decoration$-permutree fan~$\Fan$ by Theorem~\ref{theo:permutreehedra}, there is a face~$\face(\tree[S])$ whose normal cone is~$\Cone\polar(\tree[S])$. This face is given by the inequalities of~$\Permutreehedron$ corresponding to the rays of~$\Cone\polar(\tree[S])$, that is, by the inequalities~$\HS(I)$ for the edge cuts~$\edgecut{I}{J}$ of~$\tree[S]$. Moreover, a $\decoration$-permutree satisfies these inequalities if and only if it refines~$\tree[S]$, which proves the second equality. Finally, the lattice homomorphism property is a direct consequence of Proposition~\ref{prop:fan}. \end{proof} %%%%%%%%%%%%%%% \subsection{Schr\"oder permutree correspondence} \label{subsec:SchroderPermutreeCorrespondence} We now define an analogue of the permutree correspondence and $\PSymbol$-symbol, which will map decorated ordered partitions of~$[n]$ to Schr\"oder permutrees. We represent graphically an ordered partition~$\lambda \eqdef \lambda_1 \sep \cdots \sep \lambda_k$ of~$[n]$ into~$k$ parts by the~$(k \times n)$-table with a dot at row~$i$ and column~$j$ for each~$j \in \lambda_i$. See \fref{fig:insertionAlgorithmSchroder}\,(left). We denote by~$\fP_n$ the set of ordered partitions of~$[n]$ and we set~$\fP \eqdef \bigsqcup_{n \in \N} \fP_n$. A \defn{decorated ordered partition} is an ordered partition table where each dot receives a decoration of~$\Decorations$. For a decoration~$\decoration \in \Decorations^n$, let~$\fP_\decoration$ be the set of ordered partitions of~$[n]$ decorated by~$\decoration$, and set~$\fP_{\Decorations} \eqdef \bigsqcup_{n \in \N, \decoration \in \Decorations^n} \fP_\decoration.$ Given such a decorated ordered partition~$\lambda \eqdef \lambda_1 \sep \cdots \sep \lambda_k$, we construct a leveled Schr\"oder-Cambrian tree~$\SchroderPermutreeCorresp(\lambda)$ as follows. As a preprocessing, we represent the table of~$\lambda$ (with a dot at row~$i$ and column~$j$ for each~$j \in \lambda_i$), we draw a vertical red wall below the down dots (decorated by~\downCirc{} or~\upDownCirc{}) and above the up dots (decorated by~\upCirc{} or~\upDownCirc{}), and we connect into nodes the dots at the same level which are not separated by a wall. Note that we might obtain several nodes per level. We then sweep the table from bottom to top as follows. The procedure starts with an incoming strand in between any two consecutive down values. At each level, each node~$v$ (connected set of dots) gathers all strands in the region below and visible from~$v$ (\ie not hidden by a vertical wall) and produces one strand in each region above and visible from~$v$. The procedure finished with an outgoing strand in between any two consecutive up values. See \fref{fig:insertionAlgorithmSchroder}. \begin{figure}[H]%%Fig 24 \centerline{\includegraphics[scale=.65]{insertionAlgorithmSchroder}} \caption{The insertion algorithm on the decorated ordered partition~$\down{1}\up{2}5 \sep 3\up{7} \sep \updown{4}\down{6}$.} \label{fig:insertionAlgorithmSchroder} \end{figure} \begin{example} As illustrations of the Schr\"oder permutree correspondence, the leveled Schr\"oder permutrees of \fref{fig:orderedPartitionsSchroderTreesSchroderCambrianTreesTernarySequences} were all obtained by inserting the ordered partition~$125 \sep 37 \sep 46$ with different decorations. \end{example} \begin{proposition} The map~$\SchroderPermutreeCorresp$ is a bijection from decorated ordered partitions to leveled Schr\"oder-Cambrian trees. \end{proposition} \begin{proof} The proof is similar to that of Proposition~\ref{prop:permutreeCorrespondence}. \end{proof} For a decorated ordered partition~$\lambda$, we denote by~$\SchroderPSymbol(\tau)$ the permutree obtained by forgetting the increasing labeling in~$\SchroderPermutreeCorresp(\tau)$. Note that a decorated ordered partition of~$[n]$ into~$k$ parts is sent to a Schr\"oder permutree with at least~$k$ internal nodes, since some levels can be split into several~nodes. Similar to Proposition~\ref{prop:fibersPSymbol}, the following characterization of the fibers of the map~$\SchroderPSymbol$ is immediate from the description of the Schr\"oder permutree correspondence. For an ordered partition~$\lambda \eqdef \lambda_1 \sep \dots \sep \lambda_k$, we let~$\lambda^{-1}(i)$ be such that~${i \in \lambda_{\lambda^{-1}(i)}}$. For a Schr\"oder permutree~$\tree[S]$, we write~$i \to j$ in~$\tree[S]$ if the node of~$\tree[S]$ containing~$i$ is below the node of~$\tree[S]$ containing~$j$, and~$i \sim j$ in~$\tree[S]$ if~$i$ and~$j$ belong to the same node of~$\tree[S]$. We say that~$i$ and~$j$ are \defn{incomparable} in~$\tree[S]$ when~$i \not\to j$, $j \not\to i$, and~$i \not\sim j$. \begin{proposition} \label{prop:mergeLinearExtensions} For any Schr\"oder $\decoration$-permutree~$\tree[S]$ and any decorated ordered partition~${\lambda \in \fP_\decoration}$, we have~$\SchroderPSymbol(\lambda) = \tree[S]$ if and only if~$i \sim j$ in~$\tree[S]$ implies $\lambda^{-1}(i) = \lambda^{-1}(j)$ and $i \to j$ in~$\tree[S]$ implies $\lambda^{-1}(i) < \lambda^{-1}(j)$. In other words, $\lambda$ is obtained from a linear extension of~$\tree[S]$ by merging parts which label incomparable vertices of~$\tree[S]$. \end{proposition} %%%%%%%%%%%%%%% \subsection{Schr\"oder permutree congruence} \label{subsec:SchroderPermutreeCongruence} Similar to the permutree congruence, we now characterize the fibers of $\SchroderPSymbol$ by a congruence defined as a rewriting rule. Remember that we write~$X \ll Y$ when~$x < y$ for all~$x \in X$ and~$y \in Y$, that is, when~$\max(X) < \min(Y)$. \begin{definition} For a decoration~$\decoration \in \Decorations^n$, the Schr\"oder $\decoration$-permutree congruence is the equivalence relation on~$\fP_\decoration$ defined as the transitive closure of the rewriting rules \[ U \sep \b{a} \sep \b{c} \sep V \equiv^\star_\decoration U \sep \b{a}\b{c} \sep V \equiv^\star_\decoration U \sep \b{c} \sep \b{a} \sep V, \] where $\b{a}, \b{c}$ are parts while~$U, V$ are sequences of parts of~$[n]$, and there exists~$\b{a} \ll b \ll \b{c}$ such that~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$ and~$b \in \bigcup U$, or~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \in \bigcup V$. The Schr\"oder permutree congruence is the equivalence relation~$\equiv^\star$ on~$\fP_{\Decorations}$ obtained as the union of all Schr\"oder $\decoration$-permutree congruences. \end{definition} For example, $\down{1}\up{2} \sep 5 \sep 3\up{7} \sep \updown{4}\down{6} \equiv^\star \down{1}\up{2}5 \sep 3\up{7} \sep \updown{4}\down{6} \equiv^\star \down{1}\up{2}5 \sep \up{7} \sep 3 \sep \updown{4}\down{6} \not\equiv^\star \down{1}\up{2}5 \sep \up{7} \sep \updown{4}\down{6} \sep 3$. \begin{proposition} Two decorated ordered partitions~$\lambda, \lambda' \in \fP_{\Decorations}$ are Schr\"oder permutree congruent if and only if they have the same $\PSymbol^\star$-symbol: \[ \lambda \equiv^\star \lambda' \iff \SchroderPSymbol(\lambda) = \SchroderPSymbol(\lambda'). \] \end{proposition} \begin{proof} It boils down to observe that two consecutive parts~$\b{a}$ and~$\b{c}$ of an ordered partition~$U \sep \b{a} \sep \b{c} \sep V$ in a fiber~$(\SchroderPSymbol)^{-1}(\tree[S])$ can be merged to~$U \sep \b{a}\b{c} \sep V$ and even exchanged to~$U \sep \b{c} \sep \b{a} \sep V$ while staying in~$(\SchroderPSymbol)^{-1}(\tree[S])$ precisely when they belong to distinct subtrees of a node of~$\tree[S]$. They are therefore separated by the vertical wall above (resp.~below) a value~$b$ with~$\b{a} \ll b \ll \b{c}$ and such that~${\decoration_b \in \{\upCirc, \upDownCirc\}}$ and~$b \in \bigcup U$ (resp.~$\decoration_b \in \{\downCirc, \upDownCirc\}$ and~$b \in \bigcup V$). \end{proof} We now see the Schr\"oder permutree congruence as a lattice congruence. We first need to remember the facial weak order on ordered partitions as defined by D.~Krob, M.~Latapy, \mbox{J.-C.~Novelli}, H.~D.~Phan and~S.~Schwer in~\cite{KrobLatapyNovelliPhanSchwer}. This order extends the classical weak order on permutations of~$[n]$. It was also extended to faces of permutahedra of arbitrary finite Coxeter groups by P.~Palacios and M.~Ronco~\cite{PalaciosRonco} and studied in detail by A.~Dermenjian, C.~Hohlweg and V.~Pilaud~\cite{DermenjianHohlwegPilaud}. \begin{definition} The \defn{coinversion map}~${\coinv(\lambda) : \binom{[n]}{2} \to \{-1,0,1\}}$ of an ordered partition~$\lambda \in \fP_n$ is the map defined for~$i < j$ by~$\coinv(\lambda)(i,j) = \sign(\lambda^{-1}(i) - \lambda^{-1}(j))$. The \defn{facial weak order}~$\le$ is the poset on ordered partitions defined by~$\lambda \le \lambda'$ if and only if~$\coinv(\lambda)(i,j) \le \coinv(\lambda')(i,j)$ for all~$i < j$. \end{definition} The following properties of the facial weak order were proved in~\cite{KrobLatapyNovelliPhanSchwer} and extended for arbitrary finite Coxeter groups in~\cite{DermenjianHohlwegPilaud}. \begin{proposition}[\cite{KrobLatapyNovelliPhanSchwer}] The facial weak order on the set of ordered partitions is a lattice. \end{proposition} \begin{proposition}[\cite{KrobLatapyNovelliPhanSchwer}] The cover relations of the weak order~$<$ on~$\fP_n$ are given by \begin{gather*} \lambda_1 \sep \cdots \sep \lambda_i \sep \lambda_{i+1} \sep \cdots \sep \lambda_k \;\; < \;\; \lambda_1 \sep \cdots \sep \lambda_i\lambda_{i+1} \sep \cdots \sep \lambda_k \qquad\text{if } \lambda_i \ll \lambda_{i+1}, \\ \lambda_1 \sep \cdots \sep \lambda_i\lambda_{i+1} \sep \cdots \sep \lambda_k \;\; < \;\; \lambda_1 \sep \cdots \sep \lambda_i \sep \lambda_{i+1} \sep \cdots \sep \lambda_k \qquad\text{if } \lambda_{i+1} \ll \lambda_i. \end{gather*} \end{proposition} We now use the facial weak order to understand better the Schr\"oder permutree congruence. \begin{proposition} \label{prop:facialWeakOrderCongruence} For any decoration~$\decoration \in \Decorations^n$, the Schr\"oder $\decoration$-permutree congruence~$\equiv^\star_\decoration$ is a lattice congruence of the facial weak order on~$\fP^\decoration$. \end{proposition} \begin{proof} We could write a direct proof that the classes of the Schr\"oder $\decoration$-permutree congruence are intervals and that the up and down projection maps are order preserving. This was done for example in~\cite[Proposition~105]{ChatelPilaud}. To avoid this tedious proof, we prefer to refer the reader to~\cite{DermenjianHohlwegPilaud} which states that a lattice congruence of the weak order automatically transposes to a lattice congruence of the facial weak order. \end{proof} \begin{corollary} \label{coro:patternAvoidingPartitions} The Schr\"oder $\decoration$-permutree congruence classes are intervals of the facial weak order on~$\fP_n$. In particular, the following sets are in bijection: \begin{enumerate}[(i)] \item Schr\"oder permutrees with decoration~$\decoration$, \item Schr\"oder $\decoration$-permutree congruence classes, \item partitions of~$\fP_n$ avoiding the patterns~$\b{a} \sep \b{c} \dash b$ and~$\b{ac} \dash b$ for~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash \b{a} \sep \b{c}$ and~$b \dash \b{ac}$ for~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$, where~$\b{a} \ll b \ll \b{c}$ (maximums of classes), \item partitions of~$\fP_n$ avoiding the patterns~$\b{c} \sep \b{a} \dash b$ and~$\b{ac} \dash b$ for~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash \b{c} \sep \b{a}$ and~$b \dash \b{a}\b{c}$ for~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$, where~$\b{a} \ll b \ll \b{c}$ (minimums of classes). \end{enumerate} \end{corollary} It follows that the Schr\"oder permutrees inherit a lattice structure defined by~$\tree[S] < \tree[S]'$ if and only if there exist ordered partitions~$\lambda, \lambda'$ such that~$\SchroderPSymbol(\lambda) = \tree[S]$, $\SchroderPSymbol(\lambda') = \tree[S]'$ and~$\lambda < \lambda'$ in facial weak order. We now provide another interpretation of this lattice. \begin{definition} We say that the contraction of an edge~$e = v \to w$ in a Schr\"oder permutree~$\tree[S]$ is \defn{increasing} if~$p(v) \ll p(w)$ and \defn{decreasing} if~$p(w) \ll p(v)$. The \defn{Schr\"oder $\decoration$-permutree lattice} is the transitive closure of the relations~$\tree[S] < \tree[S]/e$ (resp.~$\tree[S]/e < \tree[S]$) for any Schr\"oder $\decoration$-permutree~$\tree[S]$ and any edge~$e \in \tree[S]$ defining an increasing (resp.~decreasing) contraction. \end{definition} \begin{proposition} The map~$\SchroderPSymbol$ defines a lattice homomorphism from the facial weak order on~$\fP_\decoration$ to the Schr\"oder $\decoration$-permutree lattice. In other words, the Schr\"oder $\decoration$-permutree lattice is isomorphic to the lattice quotient of the facial weak order by the Schr\"oder $\decoration$-permutree congruence. \end{proposition} \begin{proof} Let~$\lambda < \lambda'$ be a cover relation in the weak order on~$\fP_\decoration$. Assume that~$\lambda'$ is obtained by merging the parts~$\lambda_i \ll \lambda_{i+1}$ of~$\lambda$ (the other case being symmetric). Let~$u$ denote the rightmost node of~$\SchroderPSymbol(\lambda)$ at level~$i$, and~$v$ the leftmost node of~$\SchroderPSymbol(\lambda)$ at level~$i+1$. If~$u$ and~$v$ are not comparable, then~$\SchroderPSymbol(\lambda) = \SchroderPSymbol(\lambda')$. Otherwise, there is an edge~$u \to v$ in~$\SchroderPSymbol(\lambda)$ and~$\SchroderPSymbol(\lambda')$ is obtained by the increasing contraction of~$u \to v$ in~$\SchroderPSymbol(\lambda)$. \end{proof} See \fref{fig:SchroderPermutreeLattices} for examples of Schr\"oder $\decoration$-permutree lattices for $\decoration = \noneCirc{}^3$, $\downCirc{}^3$ and~$\upDownCirc{}^3$. \begin{figure}[H]%%Fig 25 \centerline{\includegraphics[scale=.78]{SchroderPermutreeLattices}} \caption{The Schr\"oder $\decoration$-permutree lattices for $\decoration = \noneCirc{}^3$ (left), $\downCirc{}^3$ (middle) and~$\upDownCirc{}^3$~(right).} \label{fig:SchroderPermutreeLattices} \end{figure} %%%%%%%%%%%%%%% \subsection{Numerology} \label{subsec:numerologySchroder} According to Corollary~\ref{coro:patternAvoidingPartitions}, Schr\"oder $\decoration$-permutrees are in bijection with ordered partitions of~$\fP_n$ avoiding the patterns~$\b{a}\sep\b{c} \dash b$ and~$\b{a}\b{c} \dash b$ for~${\decoration_b \in \{\downCirc{}, \upDownCirc{}\}}$ and~$b \dash \b{a}\sep\b{c}$ and~$b \dash \b{a}\b{c}$ for~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$. Similar to Section~\ref{subsec:numerology}, we construct a generating tree~$\generatingTreeSchroder_{\decoration}$ for these ordered partitions. This tree has~$n$ levels, and the nodes at level~$\level$ are labelled by the ordered partitions of~$[\level]$ whose values are decorated by the restriction of~$\decoration$ to~$[\level]$ and avoiding the four forbidden patterns. The parent of an ordered partition in~$\generatingTreeSchroder_\decoration$ is obtained by deleting its maximal value. See~\fref{fig:generatingTreeSchroder} for examples of such trees. As in Section~\ref{subsec:numerology}, we consider the possible positions of~$\level+1$ in the children of an ordered partition~$\lambda$ at level~$\level$ in~$\generatingTreeSchroder_\decoration$. We call \defn{free gaps} the positions where placing~$\level+1$ does not create a forbidden pattern. They are marked with a blue point~$\freeGap$ in \fref{fig:generatingTreeSchroder}. Note that free gaps can appear at the end of a part of~$\lambda$, on a separator~$\sep$ in between two parts of~$\lambda$, or at the beginning or end of~$\lambda$. We therefore include two fake separators at the beginning and at the end of~$\lambda$. Except the first free gap at the beginning of~$\lambda$, all free gaps come by pairs of the form~$\freeGap\freeSep$: if~$\level+1$ can be inserted at the end of a part, it can as well be inserted on the next separator. Therefore, any ordered partition has an odd number of free gaps. Our main tool is the following lemma. Its proof, similar to that of Lemma~\ref{lem:GeneratingTree}, is left to the reader. \begin{figure}[H] %%Fig 26 \centerline{\includegraphics[angle=90,scale=.32]{generatingTreeSchroder}} \caption{The generating trees~$\generatingTreeSchroder_\decoration$ for the decorations~$\decoration = \downCirc{}\upCirc{}\upDownCirc{}$ (top) and ${\decoration = \downCirc{}\noneCirc{}\upCirc{}}$ (bottom). Free gaps are marked with blue dots.} \label{fig:generatingTreeSchroder} \end{figure} \begin{lemma} \label{lem:GeneratingTreeSchroder} Any ordered partition at level~$\level$ with~$2g+1$ free gaps and $s$ internal separators has \begin{itemize} \item $g+1$ children with~$2g+3$ free gaps and~$s+1$ internal separators, and~$g$ children with~$2g+1$ free gaps and~$s$ separators when~$\decoration_{\level+1} = \noneCirc{}$, \item one child with~$2g'+1$ free gaps and $s$ internal separator for each~$g' \in [g]$, and one child with~$2g'+1$ free gaps and~$s+1$ internal separators for each~$g' \in [g+1]$ when~$\decoration_{\level+1} \in \{\downCirc{},\upCirc{}\}$, \item $g+1$ children with~$3$ free gaps and~$s+1$ internal separators, and~$g$ children with~$3$ free gaps and~$s$ separators when~$\decoration_{\level+1} = \upDownCirc{}$. \end{itemize} \end{lemma} Ordering the children of a node of~$\generatingTreeSchroder_\decoration$ in increasing number of free gaps and increasing number of separators, we obtain the following statement similar to Proposition~\ref{prop:generatingTree}. \begin{proposition} \label{prop:generatingTreeSchroder} For any~$\decoration, \decoration' \in \Decorations^n$ such that~${\decoration^{-1}(\noneCirc{}) = \decoration'\,\!^{-1}(\noneCirc{})}$ and ${\decoration^{-1}(\upDownCirc{}) = \decoration'\,\!^{-1}(\upDownCirc{})}$, the generating trees~$\generatingTreeSchroder_\decoration$ and~$\generatingTreeSchroder_{\decoration'}$ are isomorphic. \end{proposition} Finally, similar to Corollary~\ref{coro:inductionFactCatalan}, we obtain the following inductive formulas for the number of Schr\"oder permutrees. \begin{corollary} Let~$\decoration \in \Decorations^n$ and~$\decoration'$ be obtained by deleting the last letter~$\decoration_n$ of~$\decoration$. The number~$\factSchroder{\decoration,g,s}$ of ordered partitions avoiding~$\b{a} \sep \b{c} \dash b$ and~$\b{a}\b{c} \dash b$ for~$\decoration_b \in \{\downCirc{}, \upDownCirc{}\}$ and~$b \dash \b{a} \sep \b{c}$ and~$b \dash \b{a}\b{c}$ for~$\decoration_b \in \{\upCirc{}, \upDownCirc{}\}$ and with $2g+1$ free gaps and $s$ internal separators satisfies the following recurrence relations: \[ \factSchroder{\decoration,g,s} = \left\{\begin{array}{ll} \one_{\substack{g \ge 1 \quad \\ s \ge g-1}} \cdot \bigg( g \cdot \factSchroder{\decoration',g,s} + g \cdot \factSchroder{\decoration',g-1,s-1} \bigg) &\parbox{0.195\textwidth}{\begin{flushright}if $\decoration_n = \noneCirc{}$,\end{flushright}} \\ \displaystyle \one_{\substack{g \ge 1 \quad \\ s \ge g-1}} \cdot \bigg( \displaystyle \sum_{g' \ge g} \factSchroder{\decoration',g',s} + \sum_{g' \ge g-1} \factSchroder{\decoration',g',s-1} \bigg) &\parbox{0.195\textwidth}{\begin{flushright}if $\decoration_n = \upCirc{} \text{ or } \downCirc{}$,\end{flushright}} \\ \displaystyle \one_{g = 1} \cdot \bigg( \sum_{g' \ge 1} g' \cdot \factSchroder{\decoration',g',s} + \sum_{g' \ge 1} (g'+1) \cdot \factSchroder{\decoration',g',s-&1} \bigg) \parbox{0.15\textwidth}{\begin{flushright}if $\decoration_n = \upDownCirc{}$,\end{flushright}} \end{array}\right. \] where~$\one_X$ is $1$ if~$X$ is satisfied and~$0$ otherwise. \end{corollary} Note that for any~$\decoration \in \Decorations^n$, the $f$-vector of the permutreehedron~$\Permutreehedron$ is given by \[ f_k(\Permutreehedron) = \sum_{g \in \N} \factSchroder{\decoration,g,n-1-k}. \] For example the $f$-vector of~$\Permutreehedron[\downCirc{}\upCirc{}\noneCirc{}\upDownCirc{}\noneCirc{}\downCirc{}\upCirc{}]$ is~$[1, 324, 972, 1125, 630, 175, 22, 1]$. \begin{corollary} \label{coro:equienumeratedSchroder} The $f$-vector of the permutreehedron~$\Permutreehedron$ only depends on the positions of the \noneCirc{} and \upDownCirc{} in~$\decoration$. \end{corollary} \begin{example} Following Example~\ref{exm:permutreesSpecificDecorations}, observe that the $f$-vector of the permutreehedron~$\Permutreehedron$ specializes to the following well-known sequences of numbers: \begin{enumerate}[(i)] \item for~$\decoration = \noneCirc{}^n$, \[ f_k(\Permutreehedron[\noneCirc^n]) = \sum_{j = 0}^{n-k} (-1)^j \binom{n-k}{j} (n-k-j)^n \] is the number of ordered partitions of~$[n]$ into~$n-k$ parts~\href{https://oeis.org/A019538}{\cite[A019538]{OEIS}} and \[ \sum_{k=0}^n f_k(\Permutreehedron[\noneCirc^n]) \] is a Fubini number \href{https://oeis.org/A000670}{\cite[A000670]{OEIS}}, \item for~$\decoration \in \{\upCirc{}, \downCirc{}\}^n$, \[ \displaystyle f(\Permutreehedron) = \frac{1}{n-k} \binom{n-1}{n-k-1}\binom{2n-k}{n-k-1} \] is the number of dissections of a convex $(n+2)$-gon with $n-k-1$ non-crossing diagonals \href{https://oeis.org/A033282}{\cite[A033282]{OEIS}} and \[ \sum_{k=0}^n f_k(\Permutreehedron) \] is a Schr\"oder number \href{https://oeis.org/A001003}{\cite[A001003]{OEIS}}, \item for~$\decoration = \upDownCirc{}^n$, \[ f_k(\Permutreehedron[\noneCirc^n]) = 2^{n-1-k}\binom{n-1}{k} \] is the number of words of length~$n-1$ on~$\{-1,0,1\}$ with~$k$ occurrences of~$0$ \href{https://oeis.org/A013609}{\cite[A000244]{OEIS}} and \[ \sum_k f_k(\Permutreehedron[\upDownCirc{}^n]) = 3^{n-1} \] see \href{https://oeis.org/A000244}{\cite[A000670]{OEIS}}. \end{enumerate} \end{example} Note that for any~$\decoration \in \Decorations^n$, the $k$th entry~$h_k(\Permutreehedron)$ of the $h$-vector of the permutreehedron~$\Permutreehedron$ is the number of $\decoration$-permutrees with $k$ increasing edges (\ie edges~$i \to j$ with~$i < j$). Since the $f$-vector only depends on the positions of the \noneCirc{} and \upDownCirc{} in~$\decoration$, so does the $h$-vector. We therefore obtain the following statement. \begin{corollary} The number of $\decoration$-permutrees which have $k$ increasing edges (\ie edges~${i \to j}$ with~$i < j$) only depends on the positions of the \noneCirc{} and \upDownCirc{} in~$\decoration$. \end{corollary} \begin{example} Following Example~\ref{exm:permutreesSpecificDecorations}, observe that the $h$-vector of the permutreehedron~$\Permutreehedron$ specializes to the following well-known sequences of numbers: \begin{enumerate}[(i)] \item the Eulerian numbers \href{https://oeis.org/A008292}{\cite[A008292]{OEIS}} for~$\decoration = \noneCirc{}^n$, \item the Narayana numbers \href{https://oeis.org/A001263}{\cite[A001263]{OEIS}} for~$\decoration \in \{\upCirc{}, \downCirc{}\}^n$, \item the binomial coefficients \href{https://oeis.org/A007318}{\cite[A007318]{OEIS}} for~$\decoration = \upDownCirc^n$. \end{enumerate} \end{example} %%%%%%%%%%%%%%% \subsection{Refinement} \label{subsec:refinementSchroder} As in Section~\ref{subsec:decorationRefinements}, consider two decorations~$\decoration, \decoration' \in \Decorations^n$ such that~$\decoration \less \decoration'$ (\ie, such that~$\decoration_i \less \decoration'_i$ for all~$i \in [n]$ where the order on~$\Decorations$ is given by~$\noneCirc{} \less \{\downCirc{}, \upCirc{}\} \less \upDownCirc{}$). The Schr\"oder $\delta$-permutree congruence then refines the Schr\"oder $\delta'$-permutree congruence. Therefore, we obtain a natural surjection~$\surjectionSchroder : \SchrPermutrees(\decoration) \to \SchrPermutrees(\decoration')$: for any ordered partition~$\lambda$ of~$[n]$, $\surjectionSchroder$ sends the Schr\"oder permutree obtained by insertion of~$\lambda$ decorated by~$\delta$ to the Schr\"oder permutree obtained by insertion of~$\lambda$ decorated by~$\delta'$. This surjection can as well be interpreted directly on our representation of the Schr\"oder permutrees as in \fref{fig:refinement}, where now both the blocks and the edges can be refined. Finally, similar to Proposition~\ref{prop:refinementLatticeHomomorphism}, we obtain the following statement. \begin{proposition} \label{prop:refinementLatticeHomomorphismSchroder} The surjection~$\surjectionSchroder$ defines a lattice homomorphism from the Schr\"oder $\decoration$-permutree lattice to the Schr\"oder $\decoration'$-permutree lattice. \end{proposition} %%%%%%%%%%%%%%% \subsection{Schr\"oder permutree algebra} \label{subsec:permutreeAlgebraSchroder} To conclude this section on Schr\"oder permutrees, we briefly mention their Hopf algebra structure. Following~\cite{ChatelPilaud}, we first reformulate in terms of ordered partitions the Hopf algebra of F.~Chapoton~\cite{Chapoton} indexed by the faces of the permutahedra. We define two restrictions on ordered partitions. Consider an ordered partition~$\mu$ of~$[n]$ into~$p$ parts. For~${I \subseteq [p]}$, we let~$n_I \eqdef |\set{j \in [n]}{\exists \, i \in I, \; j \in \mu_i}|$ and we denote by~$\mu_{|I}$ the ordered partition of~$[n_I]$ into $|I|$ parts obtained from~$\mu$ by deletion of the parts indexed by~$[p] \ssm I$ and standardization. Similarly, for~$J \subseteq [n]$, we let~$p_J \eqdef |\set{i \in [p]}{\exists \, j \in J, \; j \in \mu_i}|$ and we denote by~$\mu^{|J}$ the ordered partition of~$[|J|]$ into~$p_J$ parts obtained from~$\mu$ by deletion of the entries in~$[n] \ssm J$ and standardization. For example, for the ordered partition~$\mu = 16 \sep 27 \sep 4 \sep 35$ we have~$\mu_{|\{2,3\}} = 13 \sep 2$ and~$\mu^{|\{1,3,5\}} = 1 \sep 23$. The \defn{shifted shuffle}~$\lambda \shiftedShuffle \lambda'$ and the \defn{convolution}~$\lambda \convolution \lambda'$ of two ordered partitions~${\lambda \in \fP_n}$ and~$\lambda' \in \fP_{n'}$ are defined by: \begin{align*} \lambda \shiftedShuffle \lambda' & \eqdef \bigset{\mu \in \fP_{n+n'}}{\mu^{|\{1, \dots, n\}} = \lambda \text{ and } \mu^{|\{n+1, \dots, n+n'\}} = \lambda'}, \\ \text{and}\qquad \lambda \convolution \lambda' & \eqdef \bigset{\mu \in \fP_{n+n'}}{\mu_{|\{1, \dots, k\}} = \lambda \text{ and } \mu_{|\{k+1, \dots, k+k'\}} = \lambda'}. \end{align*} For example, \begin{align*} {\red 1} \sep {\red 2} \shiftedShuffle {\blue 2} \sep {\blue 13} = \{ & {\red 1} \sep {\red 2} \sep {\blue 4} \sep {\blue 35}, \; {\red 1} \sep {\red 2}{\blue 4} \sep {\blue 35}, \; {\red 1} \sep {\blue 4} \sep {\red 2} \sep {\blue 35}, \; {\red 1} \sep {\blue 4} \sep {\red 2}{\blue 35}, \; {\red 1} \sep {\blue 4} \sep {\blue 35} \sep {\red 2}, \; {\red 1}{\blue 4} \sep {\red 2} \sep {\blue 35}, \; {\red 1}{\blue 4} \sep {\red 2}{\blue 35}, \\[-.1cm] & {\red 1}{\blue 4} \sep {\blue 35} \sep {\red 2}, \; {\blue 4} \sep {\red 1} \sep {\red 2} \sep {\blue 35}, \; {\blue 4} \sep {\red 1} \sep {\red 2}{\blue 35}, \; {\blue 4} \sep {\red 1} \sep {\blue 35} \sep {\red 2}, \; {\blue 4} \sep {\red 1}{\blue 35} \sep {\red 2}, \; {\blue 4} \sep {\blue 35} \sep {\red 1} \sep {\red 2} \}, \\[.2cm] {\red 1} \sep {\red 2} \convolution {\blue 2} \sep {\blue 13} = \{ & {\red 1} \sep {\red 2} \sep {\blue 4} \sep {\blue 35}, \; {\red 1} \sep {\red 3} \sep {\blue 4} \sep {\blue 25}, \; {\red 1} \sep {\red 4} \sep {\blue 3} \sep {\blue 25}, \; {\red 1} \sep {\red 5} \sep {\blue 3} \sep {\blue 24}, \; {\red 2} \sep {\red 3} \sep {\blue 4} \sep {\blue 15}, \\[-.1cm] & {\red 2} \sep {\red 4} \sep {\blue 3} \sep {\blue 15}, \; {\red 2} \sep {\red 5} \sep {\blue 3} \sep {\blue 14}, \; {\red 3} \sep {\red 4} \sep {\blue 2} \sep {\blue 15}, \; {\red 3} \sep {\red 5} \sep {\blue 2} \sep {\blue 14}, \; {\red 4} \sep {\red 5} \sep {\blue 2} \sep {\blue 13} \}. \end{align*} These definitions extend to decorated ordered partitions: decorations travel with their values in the shifted shuffle product, and stay at their positions in the convolution product. We denote by~$\OrdPart_{\Decorations}$ the Hopf algebra with basis~$(\F_\lambda)_{\lambda \in \fP_{\Decorations}}$ and whose product and coproduct are defined by \[ \F_\lambda \product \F_{\lambda'} = \sum_{\mu \in \lambda \shiftedShuffle \lambda'} \F_\mu \qquad\text{and}\qquad \coproduct \F_\mu = \sum_{\mu \in \lambda \convolution \lambda'} \F_\lambda \otimes \F_{\lambda'}. \] This indeed defines a Hopf algebra, which is just a decorated version of that~\cite{Chapoton}. Finally, we denote by~$\SchrPermutreeAlgebra$ the vector subspace of~$\OrdPart_{\Decorations}$ generated~by \[ \PPT_{\tree[S]} \eqdef \sum_{\substack{\lambda \in \fP_{\Decorations} \\ \SchroderPSymbol(\lambda) = \tree[S]}} \F_\lambda, \] for all Schr\"oder permutree~$\tree[S]$. We skip the proof of the following statement. \begin{theorem} $\SchrPermutreeAlgebra$ is a Hopf subalgebra of~$\OrdPart_{\Decorations}$. \end{theorem} Relevant subalgebras of the Schr\"oder permutree algebra are the Hopf algebras of F.~Chapoton~\cite{Chapoton} on the faces of the permutahedra, associahedra and cubes, as well as the Schr\"oder Cambrian Hopf algebra of G.~Chatel and V.~Pilaud~\cite[Part~3]{ChatelPilaud}. As in Section~\ref{sec:permutreeHopfAlgebra}, we invite the reader to work out direct combinatorial rules for the product and coproduct in the Schr\"oder permutree algebra. Examples can be found in~\cite[Part~3]{ChatelPilaud}. %\section*{Acknowledgments} \longthanks{ We thank two anonymous referees for helpful comments and suggestions on this paper. We thank Nathan Reading for relevant comments on this paper. The computation and tests needed along the research were done using the open-source mathematical software \texttt{Sage}~\cite{Sage} and its combinatorics features developed by the \texttt{Sage-combinat} community~\cite{SageCombinat}.} \bibliographystyle{mersenne-plain} \bibliography{ALCO_Pilaud_17} \end{document}