\documentclass[finalversion]{FPSAC2021}
\articlenumber{10}

%\usepackage{enumerate, paralist, xargs, hypcap, tikz, etoolbox, dsfont}
\usepackage{enumitem, xargs, hypcap, etoolbox, dsfont}
\usepackage{mathtools}
\usepackage{ulem}\normalem % special underline
\graphicspath{{figures/}{figures/nodes/}}
%\hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue}
%\setlist[enumerate,1]{itemsep=2pt,topsep=2pt,parsep=2pt}
%\setlist[itemize,1]{itemsep=2pt,topsep=2pt,parsep=2pt}
%\setlist[enumerate,1]{itemsep=0pt}
%\setlist[itemize,1]{itemsep=0pt}
\setlist[enumerate,1]{nosep}
\setlist[itemize,1]{nosep}

%\usepackage[T1]{fontenc}
%\usepackage{enumerate, amsmath, amsfonts, amssymb, amsthm, mathrsfs, wasysym, graphics, graphicx, xcolor, url, hyperref, hypcap,  shuffle, xargs, multicol, overpic, pdflscape, multirow, hvfloat, minibox, accents, array, multido, xifthen, a4wide, ae, aecompl, blkarray, pifont, mathtools, etoolbox, relsize}
%\usepackage{marginnote}
%\hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue}
%\usepackage[all]{xy}
%\usepackage[bottom]{footmisc}
%\usepackage{tikz}
%\usepackage{tkz-graph}
%\usetikzlibrary{trees, decorations, decorations.markings, shapes, arrows, matrix, calc, fit, intersections, patterns, angles}
%%\usepackage[noabbrev,capitalise]{cleveref}
%\graphicspath{{figures/}{figures/nodes/}}
%\makeatletter\def\input@path{{figures/}}\makeatother
%\usepackage{caption}
%\captionsetup{width=\textwidth}
%	\usepackage[export]{adjustbox}
%\usepackage{figures/picins/picins}
%\usepackage{comment}

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

% theorems
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem*{theorem*}{Theorem}%[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{assumption}[theorem]{Assumption}

% math special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\I}{\mathbb{I}} % set of integers
\newcommand{\HH}{\mathbb{H}} % hyperplane
\newcommand{\K}{k} % field
\newcommand{\fA}{\mathfrak{A}} % alternating group
\newcommand{\fS}{\mathfrak{S}} % symmetric group
\newcommand{\cA}{\mathcal{A}} % algebra
\newcommand{\cC}{\mathcal{C}} % collection
\newcommand{\cS}{\mathcal{S}} % ground set
\newcommand{\cI}{\mathcal{I}} % rays
\newcommand{\ucS}{\underline{\cS}} % underline ground set
\renewcommand{\b}[1]{{\boldsymbol{#1}}} % bold letters
\newcommand{\h}{\widehat} % hat letters

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

% operators
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\vect}{vect} % linear span
\DeclareMathOperator{\cone}{cone} % cone hull
\DeclareMathOperator{\inv}{inv} % inversions
\DeclareMathOperator{\ascents}{asc} % ascents
\DeclareMathOperator{\descents}{des} % descents
\DeclareMathOperator{\sign}{sign} % sign

% others
\newcommand{\fref}[1]{Figure~\ref{#1}} % reference figures
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % exempli gratia
\newcommand{\apriori}{\textit{a priori}} % a priori
\newcommand{\viceversa}{\textit{vice versa}} % vice versa
\newcommand{\versus}{\textit{vs.}~} % versus
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\perse}{\textit{per se}} % per se
\newcommand{\ordinal}{\textsuperscript{th}} % th for ordinals
\newcommand{\ordinalst}{\textsuperscript{st}} % st for ordinals
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
%\definecolor{green}{RGB}{57,181,74} % darkblue color
%\definecolor{violet}{RGB}{147,39,143} % darkblue color
%\newcommand{\darkblue}{\color{darkblue}} % darkblue command
%\newcommand{\darkblue}{\textcolor{darkblue}} % darkblue command
%\newcommand{\defn}[1]{\textsl{\darkblue{#1}}} % emphasis of a definition
\newcommand{\defn}[1]{\textsl{\textcolor{darkblue}{#1}}} % emphasis of a definition
\newcommand{\para}[1]{\smallskip\noindent\textbf{#1.}} % paragraph
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures
%\renewcommand\labelitemi{$\diamond$} % redefine itemize default symbol
\newcommand{\ex}{_{\textrm{exm}}} % examples
\newcommand{\pa}{_{\textrm{pa}}} % path
\newcommand{\identity}{12 \dots n} % identity

% SPECIFIC QUOTIENTOPES

% COMBINATORICS

% lattices
\newcommand{\meet}{\wedge} % meet
\newcommand{\join}{\vee} % join
\newcommand{\bigMeet}{\bigwedge} % meet
\newcommand{\bigJoin}{\bigvee} % join
\newcommand{\closure}[1]{#1^{\mathrm{cl}}} % closure operator
\newcommand{\coclosure}[1]{#1^{\mathrm{cocl}}} % coclosure operator
\newcommand{\uclosure}[1]{#1^{\underline{\mathrm{cl}}}} % loop free closure operator
\newcommand{\Bicl}[1]{\mathsf{Bic}(#1)} % biclosed sets
\newcommand{\projDown}{\pi_\downarrow} % down projection map
\newcommand{\projUp}{\pi^\uparrow} % up projection map
\newcommand{\JI}{\mathsf{JI}} % join-irreducible
\newcommand{\MI}{\mathsf{MI}} % meet-irreducible
\newcommand{\Cong}{\mathsf{Cong}} % congruence lattice
\newcommand{\con}{\mathrm{con}} % congruence contracting a cover relation
\newcommand{\ji}{\mathsf{ji}} % join irreducible
\newcommand{\mi}{\mathsf{mi}} % meet irreducible
\newcommand{\Pos}{\mathrm{Pos}} % poset of regions

% arc diagrams
\newcommand{\shard}{\Sigma}
\newcommand{\shards}{\boldsymbol{\Sigma}}
\newcommand{\arcs}{\mathcal{A}} % arcs
\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

% permutrees
\newcommand{\decoration}{\delta} % decoration
\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{\Decorations}{\{\noneCirc{}, \downCirc{}, \upCirc{}, \upDownCirc{}\}} % all decorations
\newcommand{\edgecut}[2]{\left( #1 \;\middle\|\; #2 \right)} % edge cut
\newcommand{\cl}{\ensuremath{\prec}} % inferieur curviligne
\newcommand{\cle}{\ensuremath{\preccurlyeq}} % inferieur ou egal curviligne

% GEOMETRY

% points, hyperplanes, half-spaces
\newcommand{\point}[1]{\boldsymbol{p}(#1)} % vertex of the grid associahedron corresponding to the cluster #1
\newcommandx{\ray}[1][1=r]{\boldsymbol{#1}} % ray
\newcommandx{\rays}[1][1=R]{\boldsymbol{#1}} % rays
\newcommand{\hs}{\boldsymbol{H}^{\le}} % half space
\newcommand{\HS}[1]{\boldsymbol{H}^{\le}(#1)} % half space
\newcommand{\hyp}{\mathbb{H}} % hyperplane
\newcommand{\Hyp}{\mathbf{H}} % hyperplane
\newcommand{\fix}[1]{\mathrm{Fix}(#1)} % fix space
\newcommand{\HA}{\mathcal{H}} % hyperplane arrangement

% polytopes
\newcommand{\polytope}[1]{\mathds{#1}} % polytope font
\newcommandx{\Perm}[1][1=n]{\polytope{P}\mathsf{erm}_{#1}} % permutahedron
\newcommandx{\Asso}[1][1=n]{\polytope{A}\mathsf{sso}_{#1}} % associahedron
\newcommandx{\Zono}[1][1=n]{\polytope{Z}\mathsf{ono}_{#1}} % zonotope
\newcommandx{\Fan}[1][1=F]{\mathcal{#1}} % fan
\newcommandx{\Permutreehedron}[1][1=\decoration]{\polytope{PT}_{#1}} % permutreehedron
\newcommandx{\Defo}[1][1=h]{\mathsf{Defo}_{#1}} % deformed permutahedron
\newcommandx{\Remo}[1][1=\cI]{\mathsf{Remo}_{#1}} % removahedron

% Type cone
\newcommand{\typeCone}{\mathbb{TC}} % type cone
\newcommand{\ctypeCone}{\smash{\overline{\mathbb{TC}}}} % type cone
\newcommandx{\coefficient}[3][1={\ray[t]}, 2=\ray, 3={\ray[s]}]{\alpha_{#2,#3}(#1)} % coefficient in linear dependence

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

\title{Type cones of permutree fans}

\author[Doriann Albertin, Vincent Pilaud, and Julian Ritter]{Doriann Albertin\thanks{\href{mailto:doriann.albertin@u-pem.fr}{doriann.albertin@u-pem.fr}}\addressmark{1},
Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. Supp. by ANR CAPPS~17\,CE40\,0018 and CHARMS~19\,CE40\,0017.}\addressmark{2}, \and
Julian Ritter\thanks{\href{mailto:julian.ritter@lix.polytechnique.fr}{julian.ritter@lix.polytechnique.fr}. Supp. by ANR CAPPS~17\,CE40\,0018.}\addressmark{3}}

\address{
	\addressmark{1}LIGM, Universit\'e Gustave Eiffel, Champs-sur-Marne, France \\
	\addressmark{2}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau, France \\
	\addressmark{3}LIX, \'Ecole Polytechnique, Palaiseau, France
}

\received{\today}

\abstract{
Permutreehedra are polytopes that interpolate between the permutahedron, the associahedron and the cube. They were constructed as removahedra, \ie by deleting inequalities in the facet description of the classical permutahedron. We investigate the type cone (the space of polytopal realizations) of permutree fans and prove that this removahedral construction works starting from any realization of the braid fan.}

%\resumetitle{R\'esum\'e}
\resume{
Les permutarbr\`edres sont des polytopes qui interpolent entre le permuta\`edre, l'associa\`edre et le cube. Ils sont construits comme des enlevo\`edres, \ie en supprimant des in\'egalit\'es de la description par facettes du permuta\`edre classique. Nous \'etudions le c\^one de type (l'espace de toutes les r\'ealisations polytopales) des \'eventails de permutarbres et nous montrons que cette construction par suppression de facettes fonctionne en partant de toute réalisation de l'\'eventail de tresses.
}

\keywords{Deformed permutahedra, removahedra, permutrees, type cones}

\usepackage[backend=bibtex]{biblatex}
%\DeclareFieldFormat[article,inbook,incollection,inproceedings,patent,thesis,unpublished]{title}{\textit{#1}\isdot}
%\renewbibmacro{in:}{}
%\addbibresource{quotientopesPermutreehedraRemovahedra.bib}
\addbibresource{10Albertin.bib}

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

\begin{document}

\maketitle

\section{Introduction}

\defn{Deformed permutahedra} (or \defn{generalized permutahedra}~\cite{Postnikov,PostnikovReinerWilliams}) form a fundamental family of polytopes whose geometry is closely connected to the combinatorics of permutations and posets on~$[n]$.
A polytope is a deformed permutahedron if its normal fan coarsens the braid fan, or equivalently if it can be obtained from the permutahedron~$\Perm$ by moving facets orthogonally to their normal vectors and without passing a vertex.
Prototypical examples of deformed permutahedra include the permutahedron~$\Perm$ itself and the associahedron~$\Asso$ of~\cite{ShniderSternberg, Loday}.
In fact, the associahedron~$\Asso$ belongs to a subclass of deformed permutahedra called \defn{removahedra}~\cite{Pilaud-removahedra}: it is obtained by deleting inequalities in the facet description of the permutahedron~$\Perm$.
This removahedral property is crucial to extend the construction of~\cite{ShniderSternberg, Loday} to generalized associahedra~\cite{HohlwegLange, HohlwegLangeThomas}, permutreehedra~\cite{PilaudPons-permutrees}, and accordiohedra~\cite{MannevillePilaud-accordion}.
Not all deformed permutahedra (not even all quotientopes~\cite{PilaudSantos-quotientopes, PadrolPilaudRitter}) are removahedra, since it is sometimes inevitable to move facets, not only to remove~them.

\defn{Permutrees} are oriented trees on~$[n]$ where each node has one or two parents and one or two children, and with a local condition at each node similar to the binary search tree condition.
They were introduced in~\cite{PilaudPons-permutrees} to generalize and interpolate between permutations and binary trees, and explain the combinatorial, geometric and algebraic similarities between them.
%They generalize Cambrian trees~\cite{ChatelPilaud} which provide a combinatorial model to the type~$A$ Cambrian lattices of~\cite{Reading-CambrianLattices}.
For any decoration~$\decoration$, there is a simple \defn{rotation operation} on \mbox{$\decoration$-permutrees}, and the rotation graph is the Hasse diagram of the \mbox{\defn{$\decoration$-permutree lattice}}, which generalizes the weak order on permutations and the Tamari lattice on binary trees.
This rotation graph is realized geometrically by the \defn{$\decoration$-permutree fan}~$\Fan_\decoration$ and the \defn{$\decoration$-permutreehedron}~$\Permutreehedron$ of~\cite{PilaudPons-permutrees}, obtained as a removahedron following~\cite{ShniderSternberg, Loday, HohlwegLange}.

The motivation of this paper is a more general removahedral construction for permutreehedra.
Indeed, we show that, for any decoration~$\decoration$, the $\decoration$-permutree fan is the normal fan of a polytope obtained by deleting inequalities in the facet description of any polytope whose normal fan is the braid fan, not necessarily the classical permutahedron~$\Perm$.
This statement is based on the understanding of the inequalities governing the facet heights that ensure to obtain a polytopal realization of the permutree fan.
These inequalities, given by pairs of adjacent cones of the fan and known as \defn{wall-crossing inequalities}, define the space of all realizations of the fan.
This space of realizations is a polyhedral cone called \defn{type cone}~\cite{McMullen-typeCone}, whose closure is called \defn{deformation cone}~\cite{Postnikov, PostnikovReinerWilliams}.
For instance, the deformation cone of the permutahedron~$\Perm$ is the space of \defn{submodular functions}, and corresponds to all deformed permutahedra.
Our main contribution is a combinatorial description of the facets of the type cone of any permutree fan, providing a complete description of all polytopal realizations of the permutree fans.
In particular, we obtain summation formulas for the number of facets of the type cones of permutree fans, leading to a characterization of the permutree fans whose type cone is simplicial.
As advocated in~\cite{PadrolPaluPilaudPlamondon}, this property is interesting because it leads on the one hand to a simple description of all polytopal realizations of the fan in the \defn{kinematic space}~\cite{ArkaniHamedBaiHeYan}, and on the other hand to canonical Minkowski sum decompositions of these~realizations.

These results open the door to a description of the type cone of the quotient fan~$\Fan_\equiv$ for any lattice congruence~$\equiv$ of the weak order~\cite{Reading-latticeCongruences, Reading-HopfAlgebras}, not only for permutree congruences.
Preliminary computations however indicate that the combinatorics of the facet description of the type cone of an arbitrary quotient fan is much more intricate than that of permutree fans.
In particular, we show in~\cite{AlbertinPilaudRitter} that if a lattice congrence~$\equiv$ is not a permutree congruence, then its quotient fan~$\Fan_\equiv$ is not the normal fan of a removahedron.

This extended abstract is organized as follows.
\cref{sec:preliminaries} presents some needed material, including brief recollections of type cones, of the geometry of permutations, and of permutrees.
\cref{sec:removahedra} describes the wall-crossing inequalities of the permutree fans, from which the general removahedral construction follows.
Finally, \cref{sec:typeConesPermutreeFans} describes the facet defining inequalities of the type cones of the permutree fans, and the kinematic permutreehedra derived when the type cone is simplicial.
All proofs, omitted here for space reasons, are based on the combinatorics of permutrees and can be found in~\cite{AlbertinPilaudRitter}.

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

%\newpage
\clearpage
\section{Preliminaries}
\label{sec:preliminaries}

\paragraph{\uline{Type cone.}}
Fix an essential complete simplicial fan\footnote{A \defn{polyhedral cone} is the positive span of finitely many vectors or equivalently, the intersection of finitely many closed linear half-spaces. The \defn{faces} of a cone are its intersections with its supporting hyperplanes. A \defn{fan}~$\Fan$ is a set of polyhedral cones such that any face of a cone of~$\Fan$ belongs to~$\Fan$, and any two cones of~$\Fan$ intersect along a face of both. A fan is \defn{essential} if the intersection of its cones is the origin, \defn{complete} if the union of its cones covers~$\R^n$, and \defn{simplicial} if all its cones are generated by dimension many rays.}~$\Fan$ in~$\R^n$.
Let~$\b{G}$ be the \mbox{$N \times n$-matrix} whose rows are (representative vectors for) the $N$ rays of~$\Fan$.
For any vector~$\b{h} \in \R^N$, we define the polytope\footnote{A \defn{polytope} is the convex hull of finitely many points or equivalently, a bounded intersection of finitely many closed affine half-spaces. The \defn{faces} of a polytope are its intersections with its supporting hyperplane. The \defn{vertices} (resp.~\defn{edges}, resp.~\defn{facets}) are the faces of dimension~$0$ (resp.~dimension~$1$, resp.~codimension~$1$).}~$\polytope{P}_\b{h} \eqdef \set{\b{x} \in \R^n}{\b{G}\b{x} \le \b{h}}$.
Unfortunately, the fan~$\Fan$ is not necessarily the normal fan\footnote{The \defn{normal cone} of a face~$\polytope{F}$ of a polytope~$\polytope{P}$ is the cone generated by the normal vectors of the facets of~$\polytope{P}$ containing~$\polytope{F}$. The \defn{normal fan} of~$\polytope{P}$ is the set of normal cones of all its faces.} of~$\polytope{P}_\b{h}$.
The vectors~$\b{h}$ for which this holds are characterized by the \defn{wall-crossing inequalities} given in the next statement (see \eg \cite[Lem.~2.1]{ChapotonFominZelevinsky}).

\begin{proposition}
\label{prop:characterizationPolytopalFan}
Let~$\Fan$ be an essential complete simplicial fan in~$\R^n$. Then the following are equivalent for any height vector~$\b{h} \in \R^N$:
\begin{enumerate}
\item The fan~$\Fan$ is the normal fan of the polytope~$\polytope{P}_\b{h} \eqdef \set{\b{x} \in \R^n}{\b{G}\b{x} \le \b{h}}$.
\item For any two adjacent maximal cones~$\R_{\ge0}\rays$ and~$\R_{\ge0}\rays'$ of~$\Fan$ with~$\rays \ssm \{\ray\} = \rays' \ssm \{\ray'\}$, we have
\(
{\displaystyle\sum}_{\ray[s] \in \rays \cup \rays'} \coefficient[{\ray[s]}][\rays][\rays'] \, h_{\ray[s]} > 0,
\)
where
\(
{\displaystyle\sum}_{\ray[s] \in \rays \cup \rays'} \coefficient[{\ray[s]}][\rays][\rays'] \, \ray[s] = 0
\)
is the unique linear dependence among the rays of~$\rays \cup \rays'$ such that~$\coefficient[{\ray[r]}][\rays][\rays'] + \coefficient[{\ray[r]'}][\rays][\rays'] = 2$. 
\end{enumerate}
\end{proposition}

\begin{definition}[\cite{McMullen-typeCone}]
The \defn{type cone} of~$\Fan$ is the cone~$\typeCone(\Fan)$ of all polytopal realizations of~$\Fan$:
\begin{align*}
\typeCone(\Fan) & \eqdef \set{\b{h} \in \R^N}{\Fan \text{ is the normal fan of } \polytope{P}_\b{h}} \\[-.1cm]
& = \Bigset{\b{h} \in \R^N}{\sum_{\ray[t] \in \rays \cup \rays[S]} \coefficient[{\ray[t]}][\rays][{\rays[S]}] \, \b{h}_{\ray[t]} > 0 \; \begin{array}{l} \text{for any adjacent chambers} \\ \text{$\R_{\ge0}\rays$ and~$\R_{\ge0}\rays[S]$ of~$\Fan$} \end{array}}.
\end{align*}
\end{definition}

Note that the type cone~$\typeCone(\Fan)$ is an open cone.
We denote by $\ctypeCone(\Fan)$ the closure of $\typeCone(\Fan)$, and call it the \defn{closed type cone} of~$\Fan$.
If $\Fan$ is the normal fan of the polytope~$P$, then $\ctypeCone(\Fan)$ is the \defn{deformation cone} of $P$ in~\cite{Postnikov,PostnikovReinerWilliams}.

Also observe that the lineality space of the type cone~$\typeCone(\Fan)$ has dimension~$n$ (it is invariant by translation in~$\b{G} \R^n$).
In particular, the type cone is simplicial when it has~$N-n$ facets.
While very particular, the fans for which the type cone is simplicial are very interesting as all their polytopal realizations can be described as follows.

\begin{proposition}[{\cite[Coro.~1.11]{PadrolPaluPilaudPlamondon}}]
\label{prop:simplicialTypeCone}
Let~$\Fan$ be an essential complete simplicial fan in~$\R^n$ with~$N$ rays, with a simplicial type cone~$\typeCone(\Fan)$.
Let~$\b{K}$ be the $(N-n) \times N$-matrix whose rows are the inner normal vectors of the facets of~$\typeCone(\Fan)$.
Then the polytope
\(
\smash{\polytope{Q}(\b{u}) \eqdef \bigset{\b{z} \in \R_{\ge 0}^N}{\b{K}\b{z} = \b{u}}}
\)
is a realization of the fan~$\Fan$ for any positive vector~$\smash{\b{u} \in \R_{>0}^{N-n}}$.
Moreover, the polytopes~$\smash{\polytope{Q}(\b{u})}$ for~$\b{u} \in \R_{>0}^{N-n}$ describe all polytopal realizations of~$\Fan$. \vspace{.05cm}
\end{proposition}

\clearpage

\paragraph{\uline{Permutahedron, braid arrangement, and submodular inequalities.}}

In this paper, we consider more specifically the classical permutahedron and braid fan.

\begin{definition}
The \defn{permutahedron} is the polytope~$\Perm \subset \R^n$ defined equivalently as
\begin{itemize}
\item the convex hull of the points~$\sum_{i \in [n]} i \, \b{e}_{\sigma_i}$ for all permutations~$\sigma \in \fS_n$,
\item the intersection of the hyperplane~$\Hyp \eqdef \smash{\bigset{\b{x} \in \R^n}{\sum_{i \in [n]} \b{x}_i = \binom{n+1}{2}}}$ with the halfspaces $\smash{\bigset{\b{x} \in \R^n}{\sum_{i \in I} \b{x}_i \ge \binom{|I|+1}{2}}}$ for all proper subsets~${\varnothing \ne I \subsetneq [n]}$.
\end{itemize}
\end{definition}

\begin{definition}
The \defn{braid fan} is the fan~$\Fan_n$ in~$\hyp \eqdef \bigset{\b{x} \in \R^n}{\sum_{i \in [n]} \b{x}_i = 0}$ with
\begin{itemize}
\item a chamber~$C(\sigma) \eqdef \set{\b{x} \in \hyp}{\b{x}_{\sigma_1} \le \b{x}_{\sigma_2} \le \dots \le \b{x}_{\sigma_n} }$ for each permutation~$\sigma$ of~$\fS_n$,
\item a ray~$C(I) \eqdef \bigset{\b{x} \in \hyp}{\b{x}_{i_1} = \dots = \b{x}_{i_p} \le \b{x}_{j_1} = \dots = \b{x}_{j_{n-p}}}$ for each subset~${\varnothing \ne I \subsetneq [n]}$, where~$I = \{i_1, \dots, i_p\}$ and~$[n] \ssm I = \{j_1, \dots, j_{n-p}\}$.
\end{itemize}
\end{definition}

\begin{proposition}
The braid fan~$\Fan_n$ is the normal fan of the permutahedron~$\Perm$.
\end{proposition}

The chamber~$C(\sigma)$ has rays~$C(\sigma([k]))$ for~$k \in [n]$.
Two chambers~$C(\sigma)$ and~$C(\tau)$ are adjacent if and only if~$\sigma$ and~$\tau$ differ by transposition of two consecutive entries.

We use the representative vector~$\ray(I) \eqdef |I| \one - n \one_I$ in~$C(I)$, where~$\one \eqdef \sum_{i \in [n]} \b{e}_i$ and $\one_I \eqdef \sum_{i \in I} \b{e}_i$. We also set~$\ray(\varnothing) = \ray([n]) = 0$ by convention.
These vectors satisfy the linear dependence~$\ray(I) + \ray(J) = \ray(I \cap J) + \ray(I \cup J)$ for any~$I, J \subseteq [n]$.
%
This yields the following classical description of the type cone of the braid fan~$\Fan_n$ (or deformation cone of the permutahedron~$\Perm$~\cite{Postnikov,PostnikovReinerWilliams}).
We identify a vector~$\b{h}$ with coordinates indexed by the rays of the braid fan~$\Fan_n$ with a height function~$h : 2^{[n]} \to \R_{\ge0}$~with~${h(\varnothing) = h([n]) = 0}$.

\begin{proposition}
The closed type cone of the braid fan~$\Fan_n$ (or deformation cone of the permutahedron~$\Perm$) is (isomorphic to) the set of functions~$h : 2^{[n]} \to \R_{\ge0}$ satisfying ${h(\varnothing) = h([n]) = 0}$ and the \defn{submodular inequalities} $h(I) + h(J) \ge h(I \cap J) + h(I \cup J)$ for any~${I, J \subseteq [n]}$.
The facets of~$\ctypeCone(\Fan_n)$ correspond to those submodular inequalities where~$|I \ssm J| = |J \ssm I| = 1$.
\end{proposition}

For instance, the height function for the permutahedron~$\Perm$ is given by
\[
h_\circ(I) = \max_{\sigma \in \fS_n} \dotprod{\ray(I)}{\sigma} = |I|n(n+1)/2 - n|I|(|I|+1)/2 = n|I|(n-|I|)/2.
\]
It is clearly submodular since~$h_\circ(I) + h_\circ(J) - h_\circ(I \cap J) - h_\circ(I \cup J) = 2n|I \ssm J||J \ssm I| \ge 0$.

The polytopes in the closed type cone~$\ctypeCone(\Fan_n)$ are known as \defn{deformed permutahedra}, or \defn{generalized permutahedra}~\cite{Postnikov}.
They are characterized as those polytopes whose normal fan coarsen the braid fan, or equivalently as those polytopes obtained from the permutahedron~$\Perm$ by moving facets without passing a vertex~\cite{Postnikov,PostnikovReinerWilliams}.
In this paper, we are interested in the following special way of moving facet inequalities.

\begin{definition}[\cite{Pilaud-removahedra}]
A \defn{removahedron} is a deformed permutahedron obtained by deleting inequalities in the facet description of the permutahedron~$\Perm$.
In other words, it can be written as ${\bigset{\b{x} \in \Hyp}{\sum_{i \in I} \b{x}_i \le h_\circ(I) \text{ for all } I \in \cI}}$ for some collection~$\cI$ of proper subsets of~$[n]$.
\end{definition}

Examples of removahedra include the permutahedron~$\Perm$ itself (remove no inequality), the associahedron~$\Asso$ (remove the inequalities that do not correspond to intervals), and more generally the permutreehedra~\cite{PilaudPons-permutrees} described below.

%\clearpage
\paragraph{\uline{Permutrees.}}

In an oriented tree~$T$, we call \defn{parents} (resp.~\defn{children}) of a node~$j$ the outgoing (resp.~incoming) neighbors of~$j$, and \defn{ancestor} (resp.~\defn{descendant}) subtrees of~$j$ the connected components of the parents (resp.~children) of~$j$ in~$T \ssm \{j\}$.

\begin{definition}[\cite{PilaudPons-permutrees}]
A \defn{permutree} is an oriented tree~$T$ with nodes~$[n]$, such that 
\begin{itemize}
\item any node has either one or two parents and either one or two children, and 
\item if $j$ has two parents (resp.~children), then~$i < j < k$ for every~$i$ in the left ancestor (resp.~descendant) subtree of~$j$ and every~$k$ in the right ancestor (resp.~descendant) subtree~of~$j$.
\end{itemize}
\end{definition}

\begin{figure}[h]
	\capstart
	\centerline{
	\includegraphics[scale=.93]{permutreeGeneric} \qquad
	\includegraphics[scale=.93]{permutreePermutation} \qquad
	\includegraphics[scale=.93]{permutreeBinaryTree} \qquad
	\includegraphics[scale=.93]{permutreeBinarySequence}
	}
	\caption{Four examples of permutrees. While the first is generic, the last three use specific decorations corresponding to permutations, binary trees, and binary sequences.}
	\label{fig:permutrees}
\end{figure}

\cref{fig:permutrees} provides four examples of permutrees, with the following conventions:
\begin{itemize}
\item All edges are oriented bottom-up and the nodes appear in order from left to right.
\item We decorate the nodes with \noneCirc{}, \downCirc{}, \upCirc{}, \upDownCirc{} depending on their number of parents and children. The sequence of these symbols is the \defn{decoration}~$\decoration$ of~$T$.
We set~$\decoration^- \eqdef \set{i \in [n]}{\decoration_i = \downCirc{} \text{ or } \upDownCirc{}}$ and~$\decoration^+ \eqdef \set{i \in [n]}{\decoration_i = \upCirc{} \text{ or } \upDownCirc{}}$.
\end{itemize}
In the sequel, we fix a decoration~$\decoration$ and consider only $\decoration$-permutrees.
\cref{fig:permutrees} illustrates that $\decoration$-permutrees extend and interpolate between permutations when~$\decoration = \noneCirc^n$, binary trees when~$\decoration = \downCirc^n$, and binary sequences when~$\decoration = \upDownCirc^n$.

\begin{remark}
There is a simple \defn{rotation operation} on $\decoration$-permutrees and the graph of right rotations is the Hasse diagram of the \defn{$\decoration$-permutree lattice}.
This lattice specializes to the weak order when ${\decoration = \noneCirc^n}$, the Tamari lattice when~$\decoration = \downCirc^n$, the Cambrian lattices~\cite{Reading-CambrianLattices} when~$\decoration \in \{\downCirc, \upCirc\}^n$ and the boolean lattice when~${\decoration = \upDownCirc^n}$.
In general, it is the quotient of the weak order by the \mbox{\defn{$\decoration$-permutree congruence}}, whose equivalence classes are defined by the sets of linear extensions of \mbox{$\decoration$-permutrees}.
The $\decoration$-permutree fan and $\decoration$-permutreehedron defined below are geometric realizations of the rotation graph.
We skip the lattice perspective to focus on the geometric perspective.
\end{remark}

Deleting an oriented edge~$e$ of a permutree~$T$, we obtain a partition~$[n] = I \sqcup J$ into the connected component~$I$ of the source of~$e$ and the connected component~$J$ of the target of~$e$. We say that such a partition is an \defn{edge cut} of~$T$ and write it~$\edgecut{I}{J}$.
We denote by~$\cI_\decoration$ the collection of proper subsets~$\varnothing \ne I \ne [n]$ that define an edge cut~$\edgecut{I}{[n] \ssm I}$ in at least one $\decoration$-permutree.
These subsets will be characterized in \cref{prop:raysPermutreeFan}.

%\newpage
\clearpage % For fitting one less page
We now recall the constructions of the $\decoration$-permutree fan and $\decoration$-permutreehedron~\cite{PilaudPons-permutrees}.

\begin{definition}[\cite{PilaudPons-permutrees}]
\label{def:permutreeFan}
The \defn{$\decoration$-permutree fan} is the fan~$\Fan_\decoration$ in~$\hyp$ with
\begin{itemize}
\item a chamber~$C(T)$ for each $\decoration$-permutree~$T$, which can be defined either as the union of the chambers~$C(\sigma)$ for all linear extensions~$\sigma$ of~$T$, or by the inequalities~$\b{x}_i \le \b{x}_j$ for all edges~$i \to j$ in~$T$, or as the cone generated by~$|I| \one_J - |J| \one_I$ for all edge cuts~$\edgecut{I}{J}$ of~$T$,
\item a ray~$C(I)$ for each~$I \in \cI_\decoration$.
\end{itemize}
\end{definition}

See \cref{fig:permutreeFan}.
%
\begin{figure}
	\capstart
	\centerline{\includegraphics[width=.96\textwidth]{permutreeFan}}
	\caption{Stereographic projections of the permutree fans~$\Fan_{\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}}$ and~$\Fan_{\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}}$.}
	\label{fig:permutreeFan}
\end{figure}
%
The $\decoration$-permutree fan~$\Fan_\decoration$ specializes to the braid fan when~$\decoration = \noneCirc{}^n$, the (type~$A$) Cambrian fans of N.~Reading and D.~Speyer~\cite{Reading-CambrianLattices,ReadingSpeyer} when~$\decoration \in \{\downCirc{}, \upCirc{}\}^n$, and the fan defined by the hyperplane arrangement~$\b{x}_i = \b{x}_{i+1}$ for each~$i \in [n-1]$ when~$\decoration = \upDownCirc{}^n$.

\begin{definition}[\cite{PilaudPons-permutrees}]
\label{def:permutreehedron}
The \defn{$\decoration$-permutreehedron}~$\Permutreehedron$ is the polytope defined equivalently as:
\begin{itemize}
\item the convex hull of the points~$\smash{\sum_{j \in [n]} \big( 1 + d(T,j) + \underline{\ell}(T,j) \, \underline{r}(T,j) - \overline{\ell}(T,j) \, \overline{r}(T,j) \big) \, \b{e}_j}$ for all $\decoration$-permutrees~$T$, where $d(T,j), \underline{\ell}(T,j), \underline{r}(T,j), \overline{\ell}(T,j), \overline{r}(T,j)$ respectively denote the numbers of nodes in the descendant, left descendant, right descendant, left ancestor, right ancestor subtrees of~$j$ in~$T$,
\item the intersection of the hyperplane~$\Hyp \eqdef \smash{\bigset{\b{x} \in \R^n}{\sum_{i \in [n]} \b{x}_i = \binom{n+1}{2}}}$ with the halfspaces $\smash{\bigset{\b{x} \in \R^n}{\sum_{i \in I} \b{x}_i \ge \binom{|I|+2}{2}}}$ for all~$I$ in~$\cI_\decoration$.
\end{itemize}
\end{definition}

See \cref{fig:permutreehedron}.
%
\begin{figure}[t]
	\capstart
	\centerline{\includegraphics[width=\textwidth]{permutreehedron}}
	\caption{The permutreehedra~$\Permutreehedron[\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}]$ and~$\Permutreehedron[\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}]$.}
	\label{fig:permutreehedron}
\end{figure}
%
The $\decoration$-permutreehedron~$\Permutreehedron$ specializes to the permutahedron~$\Perm$ when~${\decoration = \noneCirc{}^n}$, J.-L.~Loday's associahedron~$\Asso$~\cite{ShniderSternberg, Loday} when~$\decoration = \downCirc{}^n$, C.~Hohlweg and C.~Lange's associahedra~$\Asso[\decoration]$~\cite{HohlwegLange, LangePilaud} when~${\decoration \in \{\downCirc{}, \upCirc{}\}^n}$, and the parallelepiped with directions~$\b{e}_i - \b{e}_{i+1}$ for each~$i \in [n-1]$ when~$\decoration = \upDownCirc{}^n$.

Finally, the following statement relates \cref{def:permutreeFan,def:permutreehedron} as expected.

\begin{proposition}[\cite{PilaudPons-permutrees}]
\label{prop:permutreehedron}
The $\decoration$-permutree fan~$\Fan_\decoration$ is the normal fan of the $\decoration$-permutreehedron~$\Permutreehedron$.
\end{proposition}

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

\section{Permutreehedra and removahedra}
\label{sec:removahedra}

\cref{def:permutreehedron} implies that the $\decoration$-permutreehedron~$\Permutreehedron$ is the removahedron~$\Remo[\cI_\decoration]$ for the set~$\cI_\decoration$ (that will be characterized in \cref{prop:raysPermutreeFan}).
This intriguing property is in fact not a coincidence, as it extends to the following stronger property.

\begin{theorem}
\label{thm:strongRemovahedra}
For any decoration~$\decoration$, deleting the inequalities corresponding to the proper subsets not in~$\cI_\decoration$ in the facet description of any polytope whose normal fan is the braid fan~$\Fan_n$ yields a polytope whose normal fan is the $\decoration$-permutree fan~$\Fan_\decoration$.
\end{theorem}

\begin{remark}
In view of \cref{thm:strongRemovahedra}, it is natural to wonder whether this removahedron construction would enable to realize any lattice quotient of the weak order~\cite{Reading-latticeCongruences}.
However, it turns out that there is a strong dichotomy between the permutree congruences and the other congruences of the weak order.
Namely, we show in~\cite[Thm.~21]{AlbertinPilaudRitter} that if a lattice congrence~$\equiv$ is not a permutree congruence, then its quotient fan~$\Fan_\equiv$ is not the normal fan of the corresponding removahedron.
\end{remark}

We obtain \cref{thm:strongRemovahedra} as a consequence of the following observation concerning the wall-crossing inequalities of the $\decoration$-permutree fan~$\Fan_\decoration$.

\begin{proposition}
\label{prop:wallCrossingInequalitiesPermutreeFan}
Consider two adjacent chambers~$\R_{\ge0}\rays$ and~$\R_{\ge0}\rays[S]$ of the $\decoration$-permutree fan~$\Fan_\decoration$ with~$\rays \ssm \rays[S] = \{\ray(I)\}$ and~$\rays[S] \ssm \rays = \{\ray(J)\}$.
Then the rays~$\ray(I \cap J)$ and~$\ray(I \cup J)$ are also rays of the $\decoration$-permutree fan~$\Fan_\decoration$ and belong to~$\rays \cap \rays[S]$.
Therefore, all wall-crossing inequalities of the $\decoration$-permutree fan~$\Fan_\decoration$ are of the form
\(
h(I) + h(J) > h(I \cap J) + h(I \cup J),
\)
with~$h(\varnothing) = h([n]) = 0$ by convention.
Thus, any submodular function belongs to the type cones of all permutree fans.
\end{proposition}

Our next section is devoted to the description of those wall-crossing inequalities defining the facets of the type cone~$\ctypeCone(\Fan_\decoration)$.

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

\section{Type cones of permutree fans}
\label{sec:typeConesPermutreeFans}

In this section, we provide a complete facet description of the type cone~$\typeCone(\Fan_\decoration)$ of the $\decoration$-permutree fan~$\Fan_\decoration$.
As an immediate corollary of \cref{prop:wallCrossingInequalitiesPermutreeFan}, the linear dependence between the rays of two adjacent chambers~$C = \R_{\ge0}\rays$ and~$C' = \R_{\ge0}\rays[S]$ of the $\decoration$-permutree fan~$\Fan_\decoration$ with~$\rays \ssm \rays[S] = \{\ray\}$ and~$\rays[S] \ssm \rays = \{\ray[s]\}$ only depend on the rays~$\ray$ and~$\ray[s]$, not on the chambers~$C$ and~$C'$.
This property is called \defn{unique exchange relation property} in~\cite{PadrolPaluPilaudPlamondon} and allows to describe the type cone by inequalities associated with exchangeable rays rather than with walls.
Our combinatorial description of the type cone~$\typeCone(\Fan_\decoration)$ of the $\decoration$-permutree fan~$\Fan_\decoration$ thus proceeds in three steps. Namely, we identify:
\begin{itemize}
\item the subsets of~$[n]$ corresponding to rays of the $\decoration$-permutree fan~$\Fan_\decoration$~(\cref{prop:raysPermutreeFan}),
\item the pairs of rays that are exchangeable in the $\decoration$-permutree fan~$\Fan_\decoration$~(\cref{prop:exchangeablePairsPermutreeFan}),
\item the pairs of exchangeable rays that define a facet of~$\typeCone(\Fan_\decoration)$ (\cref{prop:extremalExchangeablePairsPermutreeFan}).
\end{itemize}
These characterizations also enable us to derive explicit summation formulas that count the number of rays of~$\Fan_\decoration$, pairs of exchangeable rays of~$\Fan_\decoration$, and facets of the type cone~$\typeCone(\Fan_\decoration)$.
We will use these formulas to determine the decorations~$\decoration$ for which the type cone~$\typeCone(\Fan_\decoration)$ is simplicial (\cref{coro:simplicialTypeCone}), and derive in that case an explicit embedding of all $\decoration$-permutreehedra in the kinematic space (\cref{coro:kinematicSpace}).
We start with the characterization of the rays of the $\decoration$-permutree fan~$\Fan_\decoration$.
Recall that for a decoration~$\decoration$, we defined~$\decoration^- \eqdef \set{i \in [n]}{\decoration_i = \downCirc{} \text{ or } \upDownCirc{}}$ and~$\decoration^+ \eqdef \set{i \in [n]}{\decoration_i = \upCirc{} \text{ or } \upDownCirc{}}$.


\begin{proposition}
\label{prop:raysPermutreeFan}
The following conditions are equivalent for a proper subset~$\varnothing \ne I \ne [n]$:
\begin{itemize}
\item $C(I)$ is a ray of the $\decoration$-permutree fan~$\Fan_\decoration$,
\item $I$ defines an edge cut~$\edgecut{I}{[n] \ssm I}$ in at least one $\decoration$-permutree,
\item for all~$a < b < c$, if~$a,c \in I$ then~$b \notin \decoration^- \ssm I$, and if~$a,c \notin I$ then~$b \notin \decoration^+ \cap I$.
\end{itemize}
\end{proposition}

\begin{example}
In \cref{fig:permutreeFan}, the rays of~$\Fan_{\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}}$ correspond to the subsets~$1$, $2$, $3$, $4$, $12$, $13$, $23$, $34$, $123$, $134$, $234$ while the rays of~$\Fan_{\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}}$ correspond to the subsets~$1$, $4$, $12$, $34$, $123$, $124$,~$234$.
\end{example}

\begin{example}
Specializing \cref{prop:raysPermutreeFan}, we recover the following classical descriptions:
\begin{itemize}
\item if~$\decoration = \noneCirc^n$, the rays of the braid fan~$\Fan_{\noneCirc^n}$ are all proper subsets~$\varnothing \ne I \subsetneq [n]$,
\item if~$\decoration = \downCirc^n$, the rays of~$\Fan_{\downCirc^n}$ are all proper intervals~$[i,j]$ of~$[n]$, (equivalently, one can think of the interval~$[i,j]$ as corresponding to the internal diagonal $(i-1,j+1)$ of a polygon with vertices labeled~$0, \dots, n+1$),
\item if~$\decoration = \upDownCirc^n$, the rays of~$\Fan_{\noneCirc^n}$ are all proper initial intervals~$[1,i]$ or final intervals~$[i,n]$.
\end{itemize}
\end{example}

\begin{corollary}
\label{coro:numberRaysPermutreeFan}
The number~$\rho(\decoration)$ of rays of the $\decoration$-permutree fan~$\Fan_\decoration$ is
\[
\rho(\decoration) = n - 1 + \sum_{\substack{1 \le i < j \le n \\ \forall \, i < k < j, \, \decoration_k \ne \upDownCirc}} \!\!\!\!\! 2^{\left|\set{i < k < j}{\decoration_k = \noneCirc}\right|}.
\]
\end{corollary}

\begin{example}
In \cref{fig:permutreeFan}, we have $\rho(\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}) = 11$ and~$\rho(\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}) = 7$.
\end{example}

\begin{example}
Specializing the formula of \cref{coro:numberRaysPermutreeFan}, we recover the following numbers:
\begin{itemize}
\item if~$\decoration = \noneCirc^n$, the braid fan~$\Fan_{\noneCirc^n}$ has~$2^n-2$ rays,
\item if~$\decoration = \downCirc^n$, the fan~$\Fan_{\downCirc^n}$ has $\binom{n+1}{2}-1$ rays (equalling the number of internal diagonals of the $(n+2)$-gon),
\item if~$\decoration = \upDownCirc^n$, the fan~$\Fan_{\upDownCirc^n}$ has~$2n-2$ rays.
\end{itemize}
\end{example}

We now identify the pairs of exchangeable rays of the $\decoration$-permutree fan~$\Fan_\decoration$.
We consider two subsets~$I, J \in \cI_\decoration$ as characterized in \cref{prop:raysPermutreeFan}.

\begin{proposition}
\label{prop:exchangeablePairsPermutreeFan}
The rays~$\ray(I)$ and~$\ray(J)$ are exchangeable in the $\decoration$-permutree fan~$\Fan_\decoration$ if and only if, up to swapping the roles of~$I$ and~$J$,
\begin{enumerate}[label=(\arabic*)]
\item $i \eqdef \max(I \ssm J) < \min(J \ssm I) \defeq j$,
\item $I \ssm J = \{i\}$ or $\decoration_i \ne \noneCirc$ \quad and \quad $J \ssm I = \{j\}$ or $\decoration_j \ne \noneCirc$,
\item ${]i,j[} \cap \decoration^- \subseteq I \cap J$ \quad and \quad ${]i,j[} \cap \decoration^+ \cap I \cap J = \varnothing$.
\end{enumerate}
\end{proposition}

\begin{example}
In \cref{fig:permutreeFan}, the pairs of exchangeable rays of~$\Fan_{\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}}$ correspond to the pairs of subsets~$\{1, 2\}$,\,$\{1, 3\}$,\,$\{1, 34\}$,\,$\{12, 13\}$, $\{12, 134\}$, $\{12, 23\}$, $\{12, 234\}$, $\{123, 134\}$, $\{123, 234\}$, $\{123, 4\}$, $\{13, 23\}$, $\{13, 34\}$, $\{13, 4\}$, $\{134, 234\}$, $\{2, 3\}$, $\{2, 34\}$, $\{23, 34\}$, $\{23, 4\}$, $\{3, 4\}$, while the pairs of exchangeable rays of~$\Fan_{\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}}$ correspond to the pairs of subsets~$\{1, 234\}$, $\{12, 34\}$, $\{12, 4\}$, $\{123, 124\}$, $\{123, 4\}$, $\{124, 34\}$.
\end{example}

\begin{example}
\label{exm:exchangeablePairsPermutreeFan}
Specializing \cref{prop:exchangeablePairsPermutreeFan}, we recover that the pairs of exchangeable rays in~$\Fan_\decoration$ correspond to the pairs of proper subsets $\{I, J\}$ where
\begin{itemize}
\item if~$\decoration = \noneCirc^n$, we have~$I = K \cup \{i\}$ and~$J = K \cup \{j\}$ for~$1 \le i < j \le n$ and~${K \subseteq [n] \ssm \{i,j\}}$,
\item if~$\decoration = \downCirc^n$, we have~$I = {[h,j[}$ and~$J = {]i,k]}$ for some~${1 \le h \le i < j \le k \le n}$, (equivalently, the internal diagonals $(h-1,j)$ and~$(i,k+1)$ of the $(n+2)$-gon intersect),
\item if~$\decoration = \upDownCirc^n$, we have~$I = {[1,i]}$ and~$J = {]i,n]}$ for some~$1 \le i < n$.
\end{itemize}
\end{example}

\begin{corollary}
\label{coro:numberExchangeablePairsPermutreeFan}
The number~$\chi(\decoration)$ of pairs of exchangeable rays in the $\decoration$-permutree fan~$\Fan_\decoration$~is
\[
\chi(\decoration) = \sum_{\substack{1 \le i < j \le n \\ \forall \, i < k < j, \, \decoration_k \ne \upDownCirc}} \!\!\!\!\! \Omega(\decoration_1 \dots \decoration_{i-1})^{\decoration_i \ne \upDownCirc} \cdot 2^{\left|\set{i < k < j}{\decoration_k = \noneCirc}\right|} \cdot \Omega(\decoration_n \dots \decoration_{j+1})^{\decoration_j \ne \upDownCirc},
\]
where $\Omega(\varepsilon) = 1$ and 
\(
\Omega(\decoration_1 \dots \decoration_k) = \begin{cases} 2 \cdot \Omega(\decoration_1 \dots \decoration_{k-1}) & \text{if } \decoration_k = \noneCirc, \\ 1 + \Omega(\decoration_1 \dots \decoration_{k-1}) & \text{if } \decoration_k \in \{\downCirc, \upCirc\}, \\ 2 & \text{if } \decoration_k = \upDownCirc. \end{cases}
\) 
\end{corollary}

\begin{example}
In \cref{fig:permutreeFan}, we have $\chi(\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}) = 19$ and~$\chi(\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}) = 6$.
\end{example}

\begin{example}
Specializing the formula of \cref{coro:numberExchangeablePairsPermutreeFan}, we recover the following numbers:
\begin{itemize}
\item when~$\decoration = \noneCirc^n$, the braid fan~$\Fan_{\noneCirc^n}$ has~$2^{n-2} \binom{n}{2}$ pairs of exchangeable rays,
\item when~$\decoration = \downCirc^n$, the fan~$\Fan_{\downCirc^n}$ has~$\binom{n+2}{4}$ pairs of exchangeable rays (equalling the number of quadruples of vertices of the $(n+2)$-gon),
\item when~$\decoration = \upDownCirc^n$, the fan~$\Fan_{\upDownCirc^n}$ has~$n-1$ pairs of exchangeable rays.
\end{itemize}
\end{example}

%\pagebreak
%\newpage
%\clearpage
In view of the unique exchange property of the $\decoration$-permutree fan~$\Fan_\decoration$, each pair of exchangeable rays of~$\Fan_\decoration$ yields a wall-crossing inequality for the type cone~$\typeCone(\Fan_\decoration)$.
However, not all pairs of exchangeable rays yield facet-defining inequalities of~$\typeCone(\Fan_\decoration)$.
The characterization of the facets of~$\typeCone(\Fan_\decoration)$ is very similar to that of the exchangeable rays, only point (ii) slightly differs.

\begin{proposition}
\label{prop:extremalExchangeablePairsPermutreeFan}
The rays~$\ray(I)$ and~$\ray(J)$ define a facet of the type cone~$\typeCone(\Fan_\decoration)$ if and only if, up to swapping the roles of~$I$ and~$J$,
\begin{enumerate}[label=(\arabic*)]
\item $i \eqdef \max(I \ssm J) < \min(J \ssm I) \defeq j$,
\item $I \ssm J = \{i\}$ or $\decoration_i = \upDownCirc$ \quad and \quad $J \ssm I = \{j\}$ or $\decoration_j = \upDownCirc$,
\item ${]i,j[} \cap \decoration^- \subseteq I \cap J$ \quad and \quad ${]i,j[} \cap \decoration^+ \cap I \cap J = \varnothing$.
\end{enumerate}
\end{proposition}

\begin{example}
In \cref{fig:permutreeFan}, the facets of the type cone~$\typeCone(\Fan_{\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}})$ correspond to the pairs of subsets\,$\{1, 2\}$,\,$\{1, 3\}$,\,$\{12, 13\}$,\,$\{12, 23\}$,\,$\{123, 134\}$,\,$\{123, 234\}$,\,$\{13, 23\}$,\,$\{13, 34\}$,\,$\{134, 234\}$, $\{2, 3\}$, $\{23, 34\}$, $\{3, 4\}$, while the facets of the type cone~$\typeCone(\Fan_{\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}})$ correspond to the pairs of subsets~$\{1, 234\}$, $\{12, 4\}$, $\{123, 124\}$, $\{124, 34\}$.
\end{example}

\begin{example}
Specializing \cref{prop:extremalExchangeablePairsPermutreeFan}, we recover that all pairs of exchangeable rays of~$\Fan_\decoration$ described in \cref{exm:exchangeablePairsPermutreeFan} define facets of the type cone~$\typeCone(\Fan_\decoration)$ when~$\decoration = \noneCirc^n$ or~$\decoration = \upDownCirc^n$. In contrast, when~$\decoration = \downCirc^n$, only the pairs of intervals~$\{{[i,j[}, {]i,j]}\}$ for some ${1 \le i < j \le n}$ correspond to facets of~$\typeCone(\Fan_{\downCirc^n})$ (equivalently, the internal diagonals ${(i-1,j)}$ and~$(i,j+1)$ of the $(n+2)$-gon that just differ by a shift).
\end{example}

\begin{corollary}
\label{coro:numberExtremalExchangeablePairsPermutreeFan}
The number~$\phi(\decoration)$ of facets of the type cone~$\typeCone(\Fan_\decoration)$ of the $\decoration$-permutree fan~$\Fan_\decoration$~is
\[
\phi(\decoration) = \sum_{\substack{1 \le i < j \le n \\ \forall \, i < k < j, \, \decoration_k \ne \upDownCirc}} \!\!\!\!\! \Omega(\decoration_1 \dots \decoration_{i-1})^{\decoration_i = \noneCirc} \cdot 2^{\left|\set{i < k < j}{\decoration_k = \noneCirc}\right|} \cdot \Omega(\decoration_n \dots \decoration_{j+1})^{\decoration_j = \noneCirc},
\]
where~$\Omega(\decoration_1 \dots \decoration_k)$ is defined inductively as in \cref{coro:numberExchangeablePairsPermutreeFan}.
\end{corollary}

\begin{example}
In \cref{fig:permutreeFan}, we have $\phi(\noneCirc{}\noneCirc{}\downCirc{}\noneCirc{}) = 12$ and~$\phi(\noneCirc{}\upDownCirc{}\upCirc{}\noneCirc{}) = 4$.
\end{example}

\begin{example}
Specializing the formula of \cref{coro:numberExtremalExchangeablePairsPermutreeFan}, we recover the following numbers:
\begin{itemize}
\item when~$\decoration = \noneCirc^n$, the type cone~$\typeCone(\Fan_{\noneCirc^n})$ has~$2^{n-2} \binom{n}{2}$ facets,
\item when~$\decoration = \downCirc^n$, the type cone~$\typeCone(\Fan_{\downCirc^n})$ has~$\binom{n}{2}$ facets (equalling the number of squares of the form~$(i-1,i,j,j+1)$ in the $(n+2)$-gon),
\item when~$\decoration = \upDownCirc^n$, the type cone~$\typeCone(\Fan_{\upDownCirc^n})$ has~$n-1$ facets.
\end{itemize}
\end{example}

\begin{corollary}
\label{coro:numberExtremalExchangeablePairsPermutreeFanNoI}
If~$\decoration \! \in \! \{\downCirc, \upCirc, \upDownCirc\}^n$, we have~$\phi(\decoration) = \left|\set{1 \le i < j \le n}{\forall \, i < k < j, \, \decoration_k \ne \upDownCirc}\right|$.
\end{corollary}

Using \cref{coro:numberRaysPermutreeFan,coro:numberExtremalExchangeablePairsPermutreeFan}, it is now immediate to characterize the decorations~$\decoration$ for the type cone~$\typeCone(\Fan_\decoration)$ is simplicial, \ie for which the number~$\rho(\decoration)$ of rays of~$\Fan_\decoration$ and the number~$\phi(\decoration)$ of facets of~$\typeCone(\Fan_\decoration)$ satisfy the equality $\phi(\decoration) = \rho(\decoration) + n - 1$.

\begin{corollary}
\label{coro:simplicialTypeCone}
The type cone~$\typeCone(\Fan_\decoration)$ is simplicial if and only if~$\decoration_k \ne \noneCirc{}$ for any~$k \in {]1,n[}$.
\end{corollary}

\newcommandx{\Fd}{\mathfrak{F}}
\newcommandx{\Rd}{\mathfrak{R}}
\newcommandx{\ldij}[3][1=i, 2=j]{\smash{p^{#3}_{#1,#2}}}
\newcommandx{\rdij}[3][1=i, 2=j]{\smash{q^{#3}_{#1,#2}}}
Applying \cref{prop:simplicialTypeCone}, we obtain the following explicit realizations of the $\decoration$-permu\-tree fans in the kinematic space~\cite{ArkaniHamedBaiHeYan} when~$\decoration \in \{\downCirc, \upCirc, \upDownCirc\}^n$.
To simplify our statement, we assume that~${\decoration_1 = \decoration_n = \upDownCirc}$ (this assumption does not lose generality as the decorations~$\decoration_1$ and~$\decoration_n$ are irrelevant in all constructions).
Consider the sets
\[
\Fd \eqdef \set{1 \le i < j \le n}{\forall \, i < k < j, \, \decoration_k \ne \upDownCirc}
\quad\text{and}\quad
\Rd \eqdef \{0, 1\} \times [n]^2 \times \{0, 1\}
\]
and define~$\ldij{\varepsilon}$ and~$\rdij{\varepsilon}$ for~$(i,j) \in \Fd$ and~$\varepsilon \in \{+, -\}$ by
\[
\ldij{\varepsilon} \! \eqdef \! \begin{cases} \min \big( \{j\} \cup \big( {]i,j[} \cap \decoration^\varepsilon \big) \big) - 1  \!\!\!\! & \text{if } i \in \decoration^\varepsilon, \\ i-1 & \text{if } i \notin \decoration^\varepsilon, \end{cases}
\quad
\rdij{\varepsilon} \! \eqdef \! \begin{cases} \max \big( \{i\} \cup \big( {]i,j[} \cap \decoration^\varepsilon \big) \big) + 1  \!\!\!\! & \text{if } j \in \decoration^\varepsilon, \\ j+1 & \text{if } j \notin \decoration^\varepsilon. \end{cases}
\]
Using these notations, we obtain the following realizations of the $\decoration$-permutree fan.

\begin{corollary}
\label{coro:kinematicSpace}
Let~$\decoration \in \{\downCirc, \upCirc, \upDownCirc\}^n$ with~${\decoration_1 = \decoration_n = \upDownCirc}$, and the notations introduced above.
Then, for any~$\b{u} \in \R_{>0}^{\Fd}$, the polytope~$\polytope{Q}_\decoration(\b{u})$ defined by
\[
\mathclap{
\set{\b{z} \in \R_{\ge0}^{\Rd}\!}{\begin{array}{@{}l@{}} \b{z}_{(\ell, \, p, \, q, \, r)} = 0 \text{ if } (p, q) \notin \Fd, \; \b{z}_{(\ell, \, p, \, q, \, r)} = \b{z}_{(\ell', \, p, \, q, \, r')} \text{ if } p + 1 \ne q, \text{ and } \forall \, (i,j) \in \Fd, \\ \b{z}_{(1, \, \ldij{+}, \, \rdij{-}, \, 0)} \! + \b{z}_{(0, \, \ldij{-}, \, \rdij{+}, \, 1)} \! - \b{z}_{(i \notin \decoration^-, \, \ldij[i][j+1]{-}, \, \rdij[i-1][j]{-}, \, j \notin \decoration^-)} \! - \b{z}_{(i \in \decoration^+, \, \ldij[i][j+1]{+}, \, \rdij[i-1][j]{+}, \, j \in \decoration^+)} \! = \b{u}_{(i, \, j)} \end{array}}}
\]
is a \defn{kinematic $\decoration$-permutreehedron}, whose normal fan is affinely equivalent to the the $\decoration$-permutree fan~$\Fan_\decoration$.
Moreover, the polytopes~$\polytope{Q}_\decoration(\b{u})$ for~$\b{u} \in \R_{>0}^{\Fd}$ describe all polytopal realizations of the $\decoration$-permutree fan~$\Fan_\decoration$.
\end{corollary}

\begin{example}
Specializing the construction of \cref{coro:kinematicSpace}, we obtain:
\begin{itemize}
\item when~$\decoration = \upDownCirc\downCirc^{n-2}\upDownCirc$, we have
\[
\ldij{-} = \begin{cases} j-1 & \text{if } i = 1, \\ i-1 & \text{if } i \ne 1, \end{cases}
\qquad
\ldij{+} = i,
\qquad
\rdij{-} = \begin{cases} i+1 & \text{if } j = n, \\ j+1 & \text{if } j \ne n, \end{cases}
\quad\text{and}\quad
\rdij{+} = j,
\]
so that the polytope~$\polytope{Q}_\decoration(\b{u})$ is affinely equivalent to the \defn{kinematic associahedron} of~\cite{ArkaniHamedBaiHeYan}:
\[
\set{\b{y} \in \R^{\binom{[0,n+1]}{2}}\!}{\begin{array}{@{}l@{}} \b{y} \ge 0, \qquad \b{y}_{(i, \, j)} = 0 \text{ if } i + 1 = j, \qquad \b{y}_{(0,n+1)} = 0, \qquad\text{and} \\ \b{y}_{(i, \, j+1)} \! + \b{y}_{(i-1, \, j)} \! - \b{y}_{(i-1, \, j+1)} \! - \b{y}_{(i, \, j)} \! = \b{u}_{(i, \, j)} \text{ for all } (i,j) \in \binom{[n]}{2} \end{array}}.
\]
(The map is given by~$\b{y}_{(0, \, j)} = \b{z}_{(1, \, j-1, \, j, \, 0)}$, $\b{y}_{(i, \, n+1)} = \b{z}_{(0, \, i, \, i+1, \, 1)}$ and~$\b{y}_{(i, \, j)} = \b{z}_{(\ell, \, i, \, j, \, r)}$ for any~$\ell, r \in \{0,1\}$.)
\item when~$\decoration = \upDownCirc^n$, we have~$\ldij{-} = \ldij{+} = i$ and $\rdij{-} = \rdij{+} = j$, so that the polytope~$\polytope{Q}_\decoration(\b{u})$ is affinely equivalent to the following \defn{kinematic cube}:
\[
\qquad
\set{\b{y} \in \R^{\{0,1\} \times [n-1]}\!}{\b{y} \ge 0 \quad\text{and}\quad \b{y}_{(0, \, i)} \! + \b{y}_{(1, \, i)} \! = \b{u}_{(i, \, i+1)} \text{ for all } i \in [n-1]}
\]
(The map is given by~$\b{y}_{(0, \, i)} = \b{z}_{(0, \, i, \, i+1, \, 1)}$ and~$\b{y}_{(1, \, i)} = \b{z}_{(1, \, i, \, i+1, \, 0)}$.)
\end{itemize}
\end{example}

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

%\acknowledgements{
%We are grateful to J.-C. Novelli for multiple discussions and suggestions, to N.~Reading for bibliographic inputs, and to A.~Padrol for comments on a preliminary version.
%}

\printbibliography

\end{document}
