%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\articlenumber{98}
\addbibresource{98.bib}
%% note that the class file already loads {amsmath, amsthm, amssymb}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{defi}[thm]{Definition}
\newtheorem{defitheorem}[thm]{Definition/Theorem}
\newtheorem{defiprop}[thm]{Definition/Proposition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{ex}[thm]{Example}
\usepackage{lipsum}
%% define your title in the usual way
\title[Generalized Coxeter permutohedra]{Deformations of Coxeter permutahedra and \\
Coxeter submodular functions}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Federico Ardila\addressmark{1}\thanks{\href{mailto:federico@sfsu.edu}{federico@sfsu.edu}},
Federico Castillo\addressmark{2}\thanks{\href{mailto:fcastillo@ku.edu}{fcastillo@ku.edu}},
Christopher Eur\addressmark{3}\thanks{\href{mailto:ceur@math.berkeley.edu}{ceur@math.berkeley.edu}}, \and
Alex Postnikov\addressmark{4}\thanks{\href{mailto:apost@math.mit.edu}{apost@math.mit.edu}\newline \indent\hspace{0.4em}FA was partially supported by NSF Award DMS-1600609 and the Simons Foundation.
FA, FC, and AP were partially supported by NSF Award DMS-1440140 to MSRI.}
}
%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}San Francisco State University \\ \addressmark{2}University of Kansas\\
\addressmark{3}University of California, Berkeley\\
\addressmark{4}Massachusetts Institute of Technology}
%% put the date of submission here
\received{\today}
%% leave this blank until submitting a revised version
%\revised{}
%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study the cone of deformations of a Coxeter permutahedron. This family contains polyhedral models for the Coxeter-theoretic analogs of compositions, graphs, matroids, posets, and associahedra. Our description extends the known correspondence between generalized permutahedra and submodular functions to any finite reflection group.}
\resumetitle{Resumen}
%% put your French abstract here, or comment this out if you don't have one
\resume{Estudiamos el cono de deformaciones de un permutaedro de Coxeter. Esta familia contiene modelos poliedrales para las composiciones, grafos, matroides, posets, y asociaedros de tipo Coxeter. Nuestra descripci\'on extiende la correspondencia entre permutaedros generalizados y funciones submodulares a cualquier grupo de reflexiones finito.}
%% put your keywords here, or comment this out if you don't have them yet
\keywords{Permutahedron, generalized permutahedron, polymatroid, {C}oxeter group, root system, Coxeter complex, polytope deformation, submodular function, nef cone, {M}ori cone.}
%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text
%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{biblio.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands
\newcommand{\I}{{\cal I}}
\newcommand{\B}{{\cal B}}
\renewcommand{\AA}{{\cal A}}
\newcommand{\Z}{{\cal Z}}
\newcommand{\W}{{\cal{W}}}
\newcommand{\HH}{{\cal H}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\df}{\textrm{Def}}
\newcommand{\nf}{\textrm{Nef}}
\newcommand{\pf}{\textrm{Pef}}
\newcommand{\id}{\textrm{id}}
\newcommand{\ncone}{\textrm{ncone}}
\newcommand{\cone}{\textrm{cone}}
\newcommand{\conv}{\textrm{conv}}
\newcommand{\PL}{\textrm{PL}}
\begin{document}
\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
\section{Introduction}
The permutahedron $\Pi_n$ is the convex hull of the $n!$ permutations of $\{1, \ldots, n\}$ in $\RR^n$. This polytopal model for the symmetric group $S_n$ appears in and informs numerous combinatorial, algebraic, and geometric settings.
There are two natural generalizations, which we now discuss.
1. Reflection groups: Instead of the group $S_n$, we may consider any finite reflection group $W$ with corresponding root system $\Phi \subset V$. This group can similarly be modeled by the $\Phi$-permutahedron, which is the convex hull of the $W$-orbit of a generic point in $V$. Most of the geometric and representation theoretic properties of the permutahedron extend to this setting.
2. Deformations: We may deform the polytope by moving its faces while preserving their directions. The resulting family of \emph{generalized permutahedra} or \emph{polymatroids} is special enough to be amenable to combinatorial analysis, and it is flexible enough to include useful geometric models of many combinatorial families of interest, such as partitions, compositions, graphs, matroids, and posets.
The goal of this paper is to initiate a theory of \emph{deformations of $\Phi$-permutahedra} or \emph{$\Phi$-polymatroids} generalizing these two directions simultaneously.
This theory is motivated by the field of \emph{Coxeter combinatorics}, which recognizes that many classical combinatorial constructions are intimately related to the symmetric group, and have natural generalizations to the setting of reflection groups.
There are natural Coxeter-theoretic analogs of compositions, graphs, matroids, and posets, and we observe that they are all part of this geometric framework of \emph{generalized $\Phi$-permutahedra}.
A central result is that generalized permutahedra are in bijection with the functions $f: 2^{[n]} \rightarrow \RR$ that satisfy the \emph{submodular inequalities} $f(A) + f(B) \geq f(A \cup B) + f(A\cap B)$. This means that the important field of submodular optimization is essentially a study of this family of polytopes.
Our main result extends this to all finite reflection groups:
\begin{thm} \label{thm:main}
Let $\Phi$ be a root system and $\W$ be its set of weights. Generalized $\Phi$-permutahedra are in bijection with the functions $h: \W \rightarrow \RR$ that satisfy the \emph{$\Phi$-submodular inequalities}:
For every element $w \in W$ of the Weyl group and every simple reflection $s_i$ and corresponding fundamental weight $\lambda_i$,
\begin{equation}\label{ineq:localsubmod}
h(w \cdot \lambda_i) + h(ws_i \cdot \lambda_i) \geq
\sum_{j\neq i}-
A_{ij} \,
%2\dfrac{\langle \alpha_i,\alpha_j \rangle}{\langle \alpha_i,\alpha_i\rangle}
h(w \cdot \lambda_j)
\end{equation}
where $A$ is the Cartan matrix. Furthermore this is a minimal set of inequalities; there are
\[
\displaystyle \sum_{i=1}^d \dfrac{|W|}{|W_{[d]-N(i)}|}
\]
such inequalities, where $N(i)$ is the set of neighbors of $i$ in the Dynkin diagram and $W_{[d]-N(i)}$ is the parabolic subgroup generated by the complement of $N(i)$.
\end{thm}
%These inequalities are very sparse: The right hand side of the $\Phi$-submodular inequality only has $1, 2,$ or $3$ non-zero terms, depending on the number of neighbors of $i$ in the Dynkin diagram of $\Phi$.
\section{Polytopes and their deformations}\label{sec:polytopes}
\subsection{Polytopes and their support functions}
Let $U$ and $V$ be two real vector space of finite dimension $d$ in duality via a perfect bilinear form $\langle \cdot,\cdot\rangle: U\times V \longrightarrow \RR$.
A \emph{polyhedron} $P\subset V$ is an intersection of finitely many half-spaces; it is a \emph{polytope} if it is bounded. %We adopt the max convention for the faces of a polyhedron $P$; that is,
We will regard each vector $u \in U$ as a linear functional on $V$, which gives rise to the \emph{$u$-maximal face} $P_u := \{v\in P: \langle u,v\rangle =\max_{x\in P} \langle u, x \rangle\}$
whenever $\max_{x\in P}\langle u , x\rangle$ is finite.
Let $\Sigma_P$ be the \emph{(outer) normal fan} in $U$. For each $\ell$-codimensional face $F$ of $P$, the normal fan $\Sigma_P$ has a dual $\ell$-dimensional face $\Sigma_P(F) = \{u \in U \, : \, P_u = F\}.$
%The support $|\Sigma_P|$ of $\Sigma_P$ is the union of its faces.
A polytope $P$ is \emph{simple} if each vertex is in exactly $d$ facets, or equivalently if every cone in $\Sigma_P$ is \emph{simplicial} in that its generating rays are linearly independent. Each cone in a fan $\Sigma$ is called a \emph{face}. Let $\Sigma(\ell)$ be the set of $\ell$-dimensional cones of $\Sigma$. We call the elements of $\Sigma(d)$ \emph{chambers}, the elements of $\Sigma(d-1)$ \emph{walls}, and the elements of $\Sigma(1)$ \emph{rays}.
All fans we consider in this paper will be \emph{projective}, i.e., normal fans $\Sigma_P$ of polyhedra $P$.
\medskip
Given a fan $\Sigma \subset U$, the space of \emph{continuous piecewise linear functions on $\Sigma$} is
\[
\operatorname{PL}(\Sigma) := \{f: |\Sigma| \to \RR \ | \ f \textnormal{ linear on each cone of $\Sigma$ and continuous}\}.
\]
The \emph{support function} of a polytope $P$ is an element $h_P \in \operatorname{PL}(\Sigma_P)$ defined by
\begin{equation} \label{eq:h_P}
h_P(u):=\max_{v\in P} \langle u,v\rangle.
\end{equation}
Notice that we can recover $P$ from $h_P$ by $P = \{v\in V: \langle u, v \rangle\leq h_P(u) \ \textrm{ for all } u\in |\Sigma_P|\},$
so a polyhedron and its support function uniquely determine each other. Also notice that the translation $P+v$ of a polytope $P$ has support function $h_{P+v}=h_P+h_{\{v\}}$, where $h_{\{v\}}$ is the linear functional $\langle \cdot,v\rangle$.
Therefore translating a polytope $P$ is equivalent to adding a global linear functional to its support function $h_P$.
\medskip
We say two polyhedra $P,Q$ are \emph{normally equivalent} (or \emph{strongly combinatorially equivalent}) if $\Sigma_P = \Sigma_Q$. A fan $\Sigma$ is a \emph{coarsening} of another fan $\Sigma'$, or $\Sigma'$ is a \emph{refinement} of $\Sigma$, if each cone of $\Sigma$ is a union of cones in $\Sigma'$; we denote this by $\Sigma\preceq \Sigma'$.
%\subsection{Deformations of polytopes}
%
%We are interested in studying the deformations of a polytope $P$.
\begin{defi}\label{def:deformation}
A polytope $Q$ is a \emph{deformation} %or \emph{weak Minkowski summand}
of $P$ if the normal fan $\Sigma_Q$ is a coarsening of the normal fan $\Sigma_P$.
\end{defi}
%When $P$ is simple, it is shown in \cite[Theorem 15.3]{PostnikovReinerWilliams} that we may think of the deformations of $P$ equivalently as being obtained by any of the following three procedures:
%
%$\bullet$ moving the vertices of $P$ while preserving the direction of each edge, or
%
%$\bullet$ changing the edge lengths of $P$ while preserving the direction of each edge, or
%
%$\bullet$ moving the facets of $P$ while preserving their directions, without allowing a facet to move past a vertex.
%\begin{figure}[h]
%\centering
%\includegraphics[scale=.4]{perm.pdf} \qquad \qquad
%\includegraphics[scale=.5]{genperm.pdf}
%\caption{The standard 3-permutahedron and one of its deformations.\label{f:genperm}}
%\end{figure}
%The justification for the name \emph{weak Minkowski summand}, comes from the following theorem.
%
%\begin{thm}[Shepard \cite{grunbaum}]
%If $P$ and $Q$ be polytopes, then $Q$ is a deformation of $P$ if and only if there exist a polytope $R$ and a scalar $\lambda >0$ such that $Q+R=\lambda P$.
%\end{thm}
%\begin{rem}\label{rem:translation}
%At the level of support functions we have $h_{\lambda Q+\mu R}=\lambda\cdot h_Q+\mu\cdot h_R$. The translation of a polytope can be expressed as a Minkowski sum with a point (a zero dimensional polytope). Note that we have in this case $h_{P+v}=h_P+h_{\{v\}}$, and $h_{\{v\}}$ is the linear functional $\langle \cdot,v\rangle$. So the support functions of $P$ and its translates differ exactly by a global linear functional.
%\end{rem}
\subsection{Deformations of zonotopes}
Let $\AA = \{v_1,\cdots,v_m\} \subset V$ be a set of vectors and let
$\mathcal H = \{H_1,\cdots, H_m\}$ be the corresponding hyperplane arrangement in $U$ given by the hyperplanes $H_i=\{u\in U: \langle u,v_i\rangle=0\}$ for $1 \leq i \leq m$.
\begin{defi}
%Let $\HH=\{H_1,\cdots, H_m\}$ be a hyperplane arrangement in $U$ together with normals
Let $\AA = \{v_1,\cdots,v_m\} \subset V$. The \emph{zonotope} of $\AA$ is the Minkowski sum
\[
{\Z}(\AA):=[0,v_1]+\cdots+[0,v_m].
\]
\end{defi}
Notice that the normal fan of the zonotope $\Z(\AA)$ is given by the faces of the arrangement $\HH$. We can describe the deformations of $\mathcal Z(\AA)$ easily as follows:
\begin{prop}\label{prop:zonoedges}
Let $\AA$ be a finite set of vectors in $V$. A polytope $P$ is a deformation of the zonotope $\Z(\AA)$ if and only if all edges of $P$ are parallel to vectors in $\AA$.
\end{prop}
\begin{proof}
If $P$ is a deformation of $\Z(\AA)$ then its normal fan $\Sigma_P$ coarsens the arrangement $\HH$. Every edge $e$ is normal to a codimension 1 wall of $\Sigma_P$, which is part of a wall of $\HH$, and hence of a hyperplane $H_i$ for some $i$. Therefore $e$ is parallel to $v_i$ as desired.
Conversely, if every edge of $P$ is parallel to a vector in $\AA$, every wall of $\Sigma_P$ is contained in a hyperplane $H_i$. We can refine $\Sigma_P$ by extending each wall to the hyperplane that it spans. The result is a subarrangement of $\HH$, which is further refined by $\HH$. Thus $P$ is a deformation of $\Z(\AA)$.
\end{proof}
\subsection{Deformation cones}
Let $P$ be a polytope in $V$ and $\Sigma = \Sigma_P$ be its normal fan.
For each deformation $Q$ of $P$, the normal fan $\Sigma_Q$ coarsens $\Sigma$, and hence the support function $h_Q$ defined in \eqref{eq:h_P} is piecewise-linear on $\Sigma$. Thus, by identifying $Q$ with its support function $h_Q$, we can define the following.
\begin{defitheorem} \cite[Theorems 6.1.5--6.1.7]{toric}.
Let $P$ be a polytope in $V$ and $\Sigma = \Sigma_P$ be its normal fan.
The \emph{deformation cone} of $P$ (or of $\Sigma$) is
\begin{equation*}
\df(P) = \df(\Sigma) := \{h_Q \, | \, Q \textrm{ is a deformation of } P\} =\{h \in \operatorname{PL}(\Sigma) \ | \ h \textrm{ is convex}\}.
\end{equation*}
\end{defitheorem}
\begin{rem}
For each ray $\rho \in \Sigma(1)$ let $u_\rho$ be a vector in the direction of $\rho$. When $\Sigma$ is a rational fan, we let $u_\rho$ be the first lattice point on the ray $\rho$. Let $R = \{u_{\rho} \, : \, \rho \in \Sigma(1)\}$. A piecewise linear function on $\Sigma$ is determined by its values on the $u_\rho$s, so we may regard it as a function $h: R \rightarrow \RR$. When the fan $\Sigma$ is simplicial, those values may be chosen arbitrarily, so $\operatorname{PL}(\Sigma)$ may be identified with $\RR^R$.
\end{rem}
%
%In the toric geometry literature it is well known that $\operatorname{Def}(\Sigma)$ is a polyhedral cone. There is a \emph{wall-crossing criterion} to test whether a piecewise linear function $h \in \PL(\Sigma) \subseteq \RR^R$ is convex, and this criterion consists of finitely many linear inequalities. We now review two versions of this wall-crossing criterion; a general one in Section \ref{sec:wallcrossing}, and a simpler one that holds for simple polytopes (or simplicial fans) in Section \ref{sec:Batyrev}.
\subsubsection{The wall crossing criterion} \label{sec:wallcrossing}
\begin{defi}\label{defi:wallcross} \emph{(Wall-crossing inequalities)}
Let $\tau\in \Sigma(d-1)$ be a wall separating two chambers $\sigma$ and $\sigma'$.
Choose any $d-1$ linearly independent rays $\rho_1, \ldots, \rho_{d-1}$ of $\tau$ and any two rays $\rho, \rho'$ of $\sigma,\sigma'$, respectively, that are not in $\tau$. Up to scaling, there is a unique linear dependence of the form
\begin{equation}\label{eq:wallcross}
\displaystyle c\cdot u_{\rho} + c'\cdot u_{\rho'} = \sum_{i=1}^{d-1}c_i\cdot u_{\rho_{i}}
\end{equation}
with $c, c' >0$. To the wall $\tau$ we associate the \emph{wall-crossing inequality}
\begin{equation}\label{ineq:wallcross}
\displaystyle
I_\tau^\Sigma(h) := c\cdot h(u_{\rho}) + c'\cdot h(u_{\rho'}) - \sum_{i=1}^{d-1}c_i\cdot h(u_{\rho_{i}}) \geq 0,
\end{equation}
which a piecewise linear function $h \in \PL(\Sigma)$ must satisfy in order to be convex.
\end{defi}
When $\Sigma$ is complete and simplicial, the element $I_\tau^\Sigma \in \PL(\Sigma)^\vee$ is well-defined up to positive scaling. Notice that $I_\tau^\Sigma(h)=0$ if and only if $h$ is represented by the same linear functional at both sides on $\tau$, which happens if and only if $\tau$ is no longer a wall in the underlying fan of $h$.
%
%For each wall $\tau\in \Sigma(d-1)$ denote the ray $I_\tau^\Sigma$ in $\operatorname{PL}(\Sigma)^\vee$ by
%$$I_\tau^\Sigma:= c\cdot h(u_{\rho}) + c'\cdot h(u_{\rho'}) - \sum_{i=1}^{d-1}c_i\cdot h(u_{\rho_{i}}).$$
%The wall crossing inequality \eqref{ineq:wallcross} then reads $I_\tau^\Sigma(h)\geq 0$. The choice of $u_\rho, u_{\rho'}$ is unique to $\tau$ only when $\sigma,\sigma'$ are simplicial, so the notation $I_\tau^\Sigma$ is an abuse of notation. However, we will mostly deal only with cases where the fan $\Sigma$ is complete and simplicial.
\begin{lem} \emph{(Wall-Crossing Criterion)}\label{lem:wallcross} \cite[Theorems 6.1.5--6.1.7]{toric} Let $\Sigma$ be a complete fan in $U$. A continuous piecewise linear function $h\in \operatorname{PL}(\Sigma)$ is a support function of a polytope $Q$ with $\Sigma_Q \preceq \Sigma$ if and only if it satisfies the wall-crossing inequality \eqref{ineq:wallcross} for each wall $\tau$ of $\Sigma$.
%of Definition \ref{defi:wallcross}.
%$I_{\tau}^\Sigma(h)\geq 0$ for all $\tau\in\Sigma(d-1)$.
\end{lem}
%\begin{proof}[Sketch of Proof.]
%To check whether $h$ is convex, it suffices to check its convexity on a line segment $xy$. Furthermore, it suffices to check this condition locally, on short segments $xy$ where $x$ and $y$ are in adjacent domains of lineality $\sigma$ and $\sigma'$. If $\tau = \sigma \cap \sigma'$ is the wall separating $\sigma$ and $\sigma'$ and $z = xy \cap \tau$, it is enough to check convexity between the extreme points $x$ and $y$ and their intermediate point $z$. One verifies, using the linearity of $h$ in $\sigma$, that it is enough to check this when $x$ and $y$ are rays of $\sigma$ and $\sigma'$ respectively; but these are precisely the wall-crossing inequalities \ref{ineq:wallcross}.
%\end{proof}
Note that $V$ embeds into $\operatorname{PL}(\Sigma)$ by $v\mapsto \langle v, \cdot \rangle$. The following is a rephrasing of \cite[4.2.12, 6.3.19--22]{toric}.
\begin{prop}\label{def:nef}
Let $\Sigma$ be the normal fan of a polytope $P$. Say $h\sim h'$ for two functions $h,h'\in \operatorname{PL}(\Sigma)$ if $h-h'$ is a globally linear function on $U$, or equivalently, if $h-h' \in V \subset \operatorname{PL}(\Sigma)$. Then:
\begin{itemize}
\item \textit{Def Cone: }$ \df(\Sigma)$ is the polyhedral cone parametrizing deformations of $P$. It is full dimensional in $\operatorname{PL}(\Sigma)$. Its linearity space is the $d$-dimensional space $V \subset \PL(\Sigma)$ of global linear functions on $|\Sigma| = U$, corresponding to the $d$-dimensional space of translations of $P$.
\item \textit{Nef Cone: }$ \nf(\Sigma) := \operatorname{Def}(\Sigma)/V = \operatorname{Def}(\Sigma)/\sim$ is the quotient of $\df(\Sigma)$ by its linearity space $V$ of globally linear functions. It is a strongly convex cone in $\operatorname{PL}(\Sigma)/V$ parametrizing the deformations of $P$ up to translation.
\end{itemize}
\end{prop}
\begin{rem} When $\Sigma$ is a rational fan, $\nf(\Sigma)$ is the \emph{Nef (numerically effective) cone} of the toric variety associated to $\Sigma$ \cite[Chapter 6.3]{toric}. The \emph{Mori cone} $\overline{NE}(\Sigma)$ is the cone polar to $Def(\Sigma)$. More precisely,
$$\overline{NE}(\Sigma) := \operatorname{Cone}\left(I_\tau^\Sigma \ | \ \tau\in \Sigma(d-1)\right) \subset \operatorname{PL}(\Sigma)^\vee,$$
%The Wall-Crossing Criterion of Lemma \ref{lem:wallcross} states that %the cone of deformations of $\Sigma$ is dual to the Mori cone $\overline{NE}(\Sigma)$. The proposition above states that
%the Nef cone and the Mori cone are dual cones in $\operatorname{PL}(\Sigma)/V$ and $(\operatorname{PL}(\Sigma)/V)^\vee$, respectively; in the toric setting, this is \cite[Theorem 6.3.22]{toric}. The structure of the strongly convex cones $\operatorname{Nef}(\Sigma)$ and $\overline{NE}(\Sigma)$ plays an important role in the geometry of the minimal model program for associated toric varieties. For details in this direction see \cite[\S15]{toric}.
\end{rem}
%Two things must be kept in mind when applying Lemma \ref{lem:wallcross}. It is not true that all the wall crossing inequalities are facet defining for $\df(\Sigma)$. Furthermore, it may happen that two walls give the exact same inequality. %Both situations are illustrated in \cite[Example 2.13]{deformation}.
%
\subsubsection{Batyrev's criterion}\label{sec:Batyrev}
When $\Sigma$ is simplicial, Batyrev's criterion (\cite[Lemma 6.4.9]{toric}) offers another useful test for convexity, and hence an alternative description of the deformation cone $\operatorname{Def}(\Sigma) = \operatorname{Def}(P)$ when $\Sigma = \Sigma_P$. To state it, we need the following notion.
\begin{defi} Let $\Sigma$ be a simplicial fan. A \emph{primitive collection} $F$ is a set of rays of $\Sigma$ such that any proper subset $F'\subsetneq F$ forms a cone in $\Sigma$ but $F$ itself does not. In other words, the primitive collections of a simplicial fan correspond to the minimal non-faces of the associated simplicial complex.
\end{defi}
\begin{lem}\label{lem:Batyrev} \emph{(Batyrev's Criterion)} \cite[Theorem 6.4.9]{toric}
Let $\Sigma$ be a complete simplicial fan.
%which is the normal fan of a polytope $P$.
A piecewise linear function $h\in \operatorname{PL}(\Sigma)$ is in the deformation cone $\operatorname{Def}(\Sigma)$ (and hence the support function of a polytope)
%=\operatorname{Def}(P)$
if and only if
\[
\sum_{\rho\in F} h(u_\rho)
\geq
h\left(\sum_{\rho \in F} u_\rho\right)
\]
for any primitive collection $F$ of rays of $\Sigma$.
\end{lem}
The material in this section can be rephrased in terms of triangulations of point configurations (see \cite[Section 5]{triangulations}). Deformation cones are instances of secondary cones for the collection of vectors $\{u_\rho: \rho\in \Sigma(1)\}$. The Wall-Crossing criterion \cref{lem:wallcross} is called the \emph{local folding condition} in \cite[Theorem 2.3.20]{triangulations}. %The secondary cones form a \emph{secondary fan} whose faces are in bijection with the regular subdivisions of the configuration. When the configuration is \emph{acyclic} (so it can be visualized as a point configuration), this secondary fan is complete, and it is the normal fan of the \emph{secondary polytope}. Our situation is more subtle because our vector configurations is not acyclic, so the secondary fan is not complete, and there is no secondary polytope.
%\begin{rem}
%The notions wall-crossing, nef and Mori cones, and Batyrev's criterion all naturally generalize to the case when $\Sigma$ is not necessarily complete but has convex support of full dimension.
%
%The notions of nef and Mori cones, and the Wall-Crossing and Batyrev criteria naturally generalize to the case when $\Sigma$ is not necessarily complete but has convex support of full dimension.
%
%\end{rem}
\section{Reflection groups and Coxeter complexes}\label{sec:coxeter}
In this section we review the combinatorial aspects of finite reflection groups that we will need.
\subsection{Root systems and Coxeter complexes}\label{subsec:rootsystems}
We will identify $V$ with its own dual by means of a positive definite inner product $\langle\cdot,\cdot\rangle:V\times V\to \mathbb{R}$.
Any vector $v\in V$ defines a linear automorphism $s_v$ on $V$ by reflecting across the hyperplane orthogonal to $v$; that is,
\begin{equation}\label{eq:reflex}
s_v(x) := x-\dfrac{2\langle x,v \rangle}{\langle v,v \rangle}v.
\end{equation}
\begin{defi}
A \emph{root system} $\Phi$ is a finite set of vectors in an inner product real vector space $V$ satisfying
\begin{itemize}
\item[(R0)] $\textrm{span}(\Phi)=V$,
\item[(R1)] for each root $\alpha \in \Phi$, the only scalar multiples of $\alpha$ that are roots are $\alpha$ and $-\alpha$, and %$R\cap\RR\alpha=\{\alpha,-\alpha\}$ for all $\alpha\in R$, and
\item[(R2)] for each root $\alpha \in \Phi$ we have $s_\alpha(\Phi)=\Phi$.
%\item[(R3)] for each pair of roots $\alpha, \beta \in \Phi$ we have that $2\langle\alpha, \beta \rangle/\langle \alpha,\alpha \rangle$ is an integer.
\end{itemize}
%We call $d = \dim V$ the \emph{rank} of $\Phi$.
\end{defi}
Each root $\alpha\in \Phi$ gives rise to a hyperplane $H_\alpha=\{x\in V: \langle\alpha,x\rangle = 0\}$. This set of hyperplanes $\HH_\Phi = \{H_\alpha: \alpha\in \Phi\}$ is called the \emph{Coxeter arrangement}. The \emph{Coxeter complex} is the associated fan $\Sigma_\Phi$, which is simplicial. We will often use these two terms interchangeably, and drop the subscript $\Phi$ when the context is clear.
\medskip
The combinatorial structure of the Coxeter complex $\Sigma_\Phi$ is closely related to the algebraic structure of the group $W_\Phi$, as we now explain. Let us fix a chamber (maximal cone) of $\Sigma_\Phi$ to be the \emph{fundamental domain} $D$; recall that it is simplicial. Then the \emph{simple roots} $\Delta=\{\alpha_1,\cdots,\alpha_d\}\subset \Phi$ are the roots whose positive halfspaces minimally cut out the fundamental domain; that is, $
D = \{x \in V \, : \, \langle \alpha_i, x \rangle \geq 0 \textrm{ for } 1 \leq i \leq d\}.$
The simple roots form a basis for $V$, and we call $d = \dim V$ the \emph{rank} of the root system $\Phi$. The \emph{positive roots} are those that are non-negative combinations of simple roots; we denote this set by $\Phi^+ \subset \Phi$. We have that $\Phi = \Phi^+ \sqcup (-\Phi^+)$. The \emph{Cartan matrix} is the $d\times d$ integer matrix $A$ whose entries are $A_{ij} := 2\frac{\langle \alpha_i, \alpha_j\rangle}{\langle\alpha_i, \alpha_i \rangle} \textrm{ for } 1 \leq i, j \leq d.$
%The diagonal entries of the Cartan matrix are 2. The rigid conditions imposed on a root system imply that all the off-diagonal entries are either $0,-1,-2$, or $-3$. A row or column of $A$ contains at most four nonzero entries.
%
%The \emph{Coxeter matrix} has entries $m_{ij} = m_{ji} = 2,3,4,6,1$ if $A_{ij}A_{ji} = 0,1,2,3,4$, respectively. This information is encoded in the \emph{Dynkin diagram} $\Gamma(\Phi)$ of $W_\Phi$, which has vertices $\{s_1, \ldots, s_d\}$,
% %, obtained from the presentation $W_\Phi = \langle s_1, \ldots, s_d \ | \ (s_is_j)^{m_{ij}}\rangle$ by having
%and an edge labelled $m_{ij}$ between $s_i$ and $s_j$ whenever $m_{ij} >2$. Labels equal to 3 are customarily omitted.
%
%The \emph{direct sum} of two root systems $\Phi_1$ and $\Phi_2$, spanning $V_1$ and $V_2$ respectively, is the root system $\Phi_1 \oplus \Phi_2 := \{(\alpha, 0)\in V_1\oplus V_2 : \alpha \in R_1\} \cup \{(0,\beta)\in V_1\oplus V_2 : \beta\in R_2\}$ which spans $V_1 \oplus V_2$.
%An \emph{irreducible} root system is a root system that is not a non-trivial direct sum of root systems. The connected components of the Dynkin diagram $\Gamma(\Phi)$ correspond to the irreducible root systems whose direct sum is $\Phi$.
\subsection{Weyl groups, parabolic subgroups, and the Coxeter complex}\label{subsec:groups}
\begin{prop}
Let $\Phi$ be a root system spanning $V$ and let $W=W_\Phi$ be the subgroup of $\textrm{GL}(V)$ generated by the reflections $s_\alpha$ for $\alpha\in \Phi$. Then $W$ is a finite group, called the \emph{Weyl group} of $\Phi$. %For any choice of simple roots $\Delta = \{\alpha_1, \ldots, \alpha_d\} \subset \Phi$, the Weyl group is generated by the set of simple reflections $S := \{s_1, \ldots, s_d\}$. %with presentation given by the Coxeter matrix as follows:
%\begin{equation}\label{eq:presentation}
%W = \langle s_1, \ldots, s_d \ | \ (s_is_j)^{m_{ij}} \ \textrm{ for } 1\leq i,j\leq d)\rangle
%\end{equation}
\end{prop}
\medskip
The action of $W$ on $V$ induces an action on the Coxeter complex $\Sigma_\Phi$. This action behaves especially well on the top-dimensional faces:
\begin{prop}
The Weyl group $W$ acts regularly on the set $\Sigma_\Phi(d)$ of chambers of the Coxeter arrangement; that is, for any two chambers $\sigma$ and $\sigma'$ there is a unique element $w \in W$ such that $w \cdot \sigma = \sigma'$. In particular, the chambers of the Coxeter arrangement are in bijection with $W$.
\end{prop}
%The previous proposition implies that a different choice $wD$ of a fundamental domain (where $w\in W$) gives rise to a new set of simple roots $w \Delta$ that is linearly isomorphic to the original set $\Delta$ of simple roots, since $W$ acts by isometries. %It follows that the presentation for the Weyl group in \eqref{eq:presentation} and the Cartan matrix $A$ are independent of the choice of fundamental domain $D$.
\medskip
The lower dimensional faces of $\Sigma_\Phi$ correspond to certain subgroups of $W$ and their cosets. The \emph{parabolic subgroups} of $W$ are the subgroups $W_I := \langle s_\alpha: \alpha\in I\rangle \subset W $ for each $I \subseteq \Delta$.
They are in bijection with the faces of the fundamental domain, where $W_I$ is mapped to the face
\[
C_I := \{x\in D: \langle x,\alpha \rangle = 0 \textrm{ for all }\alpha\in I, \langle x,\alpha \rangle \geq 0 \textrm{ for all }\alpha\in\Delta\backslash I\} \qquad \textrm{ for } I \subseteq \Delta.
\]
The \emph{parabolic cosets} are the right cosets of parabolic subgroups.
\begin{prop}\label{prop:stab}
The faces of the Coxeter complex are in bijection with the parabolic cosets of $W$, through the labeling $F \mapsto \{w \, : \, F \subseteq wD\}$.
Under the action of $W$ on the Coxeter complex $\Sigma$, the orbit of the face $C_I$ (which is labeled $W_I$) is the set of faces labeled by the right cosets of $W_I$.
Furthermore, for any $v$ in the interior of $C_I$, the stabilizer of $v$ under the action of $W$ is the parabolic subgroup $W_I$.
\end{prop}
Two special cases, stated in the following corollaries, are especially important to us.
\begin{cor}
The walls of the Coxeter complex are labeled by the pairs $\{w, ws_i\} = w W_{\{i\}}$ for $w \in W$ and $s_i \in S$. The wall labeled $\{w, ws_i\}$ separates the chambers labeled $w$ and $ws_i$.
\end{cor}
\begin{defiprop}
Let the \emph{fundamental weights} $(\lambda_1,\cdots,\lambda_d)$ form the basis of $V$ dual to the simple roots $(\alpha_1,\cdots,\alpha_d)$; that is, $\langle \lambda_i,\alpha_j \rangle = \delta_{ij}$. Let the set of \emph{weights} be $\W = W \cdot \{\lambda_1,\cdots,\lambda_d\}$. Each weight can be expressed as $w \cdot \lambda_i$ for a unique $i$ (although the $w$ is not unique).
\end{defiprop}
\begin{cor}
The $d$ rays of the fundamental domain are spanned by the fundamental weights $\lambda_1, \ldots, \lambda_d$, and the rays of the Coxeter complex are spanned by the weights. These correspondences are bijective.
\end{cor}
%Note that the faces of the fundamental chamber are given by
%\[
%C_I = D \cap ( \bigcap_{i\in I} H_{\alpha_i}) = \operatorname{Cone}(\lambda_i \ | \ i\notin I) \textrm{ for } I\subseteq \Delta.
%\]
%Parabolic subgroups arise as isotropy groups for the action of $W$ on $V$ \cite[Theorem 1.12, Proposition 1.15]{reflection}.
\begin{thm}\label{thm:isotropy}
If $V'$ is any subset of $V$ then the subgroup $W_{V'} \leq W$ fixing $V'$ pointwise is generated by the reflections $s_\alpha$ that it contains.
\end{thm}
\section{Coxeter permutahedra and some important deformations} \label{sec:examples}
Throughout this section, let $\Phi$ be a root system and $W$ be its Weyl group.
\begin{defiprop}
The \emph{standard Coxeter permutahedron of type $\Phi$} or \linebreak {$\Phi$-permutahedron} is the Minkowski sum of the roots of $\Phi$; that is, $\Pi_\Phi := \sum_{\alpha \in \Phi} [0,\alpha]$.
%This is the same as %\operatorname{Conv}(w \cdot \delta : w\in W),$
%where $\delta = \frac12(\sum_{\alpha \in \Phi^+} \alpha) = \lambda_1 + \cdots + \lambda_d$.
A \emph{generalized $\Phi$-permutahedron} or \emph{$\Phi$-polymatroid} is a deformation of the $\Phi$-permutahedron $\Pi_\Phi$; that is, a polytope whose normal fan coarsens the Coxeter complex $\Sigma_\Phi$.
\end{defiprop}
%\begin{prop}
%\emph{Orbit polytopes}, defined as $P_\Phi(x) = \conv(W \cdot x)$ for $x \in V$, are generalized Coxeter permutahedra.
%\end{prop}
\begin{prop}
The following families of polytopes are generalized Coxeter permutahedra:
1. the \emph{orbit polytopes} $P_\Phi(x) = \conv(W \cdot x)$ for $x \in V$.,
2. the \emph{Coxeter-graphic zonotopes} $\sum_{\alpha \in \Psi} [0, \alpha]$ for $\Psi \subseteq \Phi$,
3. the \emph{Coxeter matroids} of Gelfand--Serganova \cite{BGW03},
4. the \emph{Coxeter cones} of Reiner \cite{Reiner} and Stembridge \cite{Stembridge}, and
5. the \emph{Coxeter associahedra} of Hohlweg-Lange-Thomas \cite{HLT}.
\noindent These families of polyhedra model the Coxeter-theoretic analogs of compositions, graphs, matroids, posets, and clusters, respectively.
\end{prop}
%
%One of the main goals of this paper is to describe the cone of deformations of the $\Phi$-permutahedron; we will do so in Theorem \ref{thm:thecone}. Before we do that, we motivate that result by discussing some notable examples of generalized $\Phi$-permutohedra.
%
%\subsection{Orbit polytopes}
%
%Coming from a hyperplane arrangement, we already saw a way to construct a polytope with normal fan equal to $\Sigma$. There is another way using the $W$-action.
%
%\begin{defi}
%The \emph{orbit polytope} $P_\Phi(x)$ of a point $x \in V$ is the convex hull of the orbits of $x$ under the action of the Weyl group $W$: $P_\Phi(x) := \operatorname{Conv}(w\cdot x : w\in W).$
%\end{defi}
%
An orbit polytope $P_\Phi(x)$ can always be defined by a point $x$ in the fundamental domain $D$, and its normal fan depends only on the minimal face of $D$ containing it:
%Proposition \ref{prop:stab} implies that two orbit polytopes $P_\Phi(x), P_\Phi(y)$ for $x,y\in D$ are normally equivalent if and only if $x$ and $y$ are in the interior of the same face $C_I$ of $D$.
%%; in other words, the normal fan of $P_\Phi(x)$ depend only on the open face of $\Sigma_\Phi$ containing $x$.
%More precisely:
\begin{prop} \label{prop:orbit}
For $x$ in the interior of $C_I$, the chambers of the normal fan of $P_\Phi(x)$ are in bijection with $W/W_I$. The chamber of $\Sigma_{P_\Phi(x)}$ corresponding to the coset $wW_I$ is the union of the $|W_I|$ chambers of the Coxeter complex $\Sigma_\Phi$ labeled $ww_I$ for $w_I \in W_I$.
%
%For $x \in C_I$, the chambers of the normal fan $\Sigma_{P_\Phi(x)}$, are obtained by taking the union of all cones in $\Sigma_\Phi$ (which are labelled by elements of $W$) on each left coset of $W/W_I$.
\end{prop}
The following special case will be important below: When $x$ is in the interior of $C_{\{i\}}$, the normal fan of $P_\Phi(x)$ is obtained by merging the chambers $w \cdot D$ and $s_iw \cdot D$ for each $w \in W$.
\section{Deformation cone for Coxeter complexes}
Our next goal is to describe the deformation cone of Coxeter permutahedra. Recall that a piecewise linear function on a fan is uniquely determined by its restriction to the rays of the fan. Since each ray of the Coxeter complex $\Sigma_\Phi$ contains a weight, and this correspondence is bijective, we may identify the space $\operatorname{PL}(\Sigma_\Phi)$ of piecewise-linear functions on $\Sigma_\Phi$, with the space $\RR^{\W}$ of functions from $\W$ to $\RR$.
\subsection{$\Phi$-submodular functions}
\begin{defi}
A function $h: \W \rightarrow \RR$ is \emph{$\Phi$-submodular} if the following equivalent conditions hold:
$\bullet$
$h\in \operatorname{Def}(\Sigma_\Phi)$.
$\bullet$
When regarded as a piecewise linear function in $\PL(\Sigma_\Phi)$, the function $h$ is convex.
$\bullet$
The polytope $\{v \in V \, : \, \langle \lambda, v \rangle \leq h(\lambda) \textrm{ for all } \lambda \in \W\}$ is a generalized $\Phi$-permutahedron.
$\bullet$
The polytope $\{v \in V \, : \, \langle \lambda, v \rangle \leq h(\lambda) \textrm{ for all } \lambda \in \W\}$ has edges parallel to roots in $\Phi$.
\noindent
We call $\operatorname{Def}(\Sigma_\Phi) \subset \RR^\W$ the \emph{$\Phi$-submodular cone}.
\end{defi}
We now describe the $\Phi$-submodular. The Coxeter complex is simplicial which makes it easier to apply the results in \cref{sec:polytopes}.
\begin{thm} \label{thm:main}
A function $h: \W \rightarrow \RR$ is \emph{$\Phi$-submodular} if and only if the following two equivalent sets of inequalities hold:
\begin{enumerate}
\item
\emph{(Local $\Phi$-submodularity)}
For every element $w \in W$ of the Weyl group and every simple reflection $s_i$ and corresponding fundamental weight $\lambda_i$,
\begin{equation}\label{ineq:localsubmod}
h(w \cdot \lambda_i) + h(ws_i \cdot \lambda_i) \geq
\sum_{j\neq i}-
A_{ij} \,
%2\dfrac{\langle \alpha_i,\alpha_j \rangle}{\langle \alpha_i,\alpha_i\rangle}
h(w \cdot \lambda_j)
\end{equation}
where $A$ is the Cartan matrix.
\item
\emph{(Global $\Phi$-submodularity)}
For any two weights $\lambda, \lambda' \in \W$
\begin{equation}\label{ineq:Batyrev}
h(\lambda) + h(\lambda') \geq
h(\lambda + \lambda')
\end{equation}
where $h$ is regarded as a piecewise-linear function on $\Sigma_\Phi$.
\end{enumerate}
\end{thm}
%\begin{rem}
%The sparseness of the Cartan matrix implies that the local $\Phi$-submodular inequalities \eqref{ineq:localsubmod} have at most three terms on the right hand side.
%\end{rem}
\begin{rem}
To interpret the global $\Phi$-submodular inequalities \eqref{ineq:Batyrev} directly in terms of the function $h \in \RR^\W$, we need to find the minimal cone $C$ of $\Sigma_\Phi$ containing $\lambda + \lambda'$. If $\W_C$ is the set of weights in the cone $C$, we can write $\lambda + \lambda' = \sum_{w \in \W_C} c_w w$ for a unique choice of positive constants $c_w$, and \eqref{ineq:Batyrev} means that $h(\lambda) + h(\lambda') \geq \sum_{w \in \W_C} c_w h(w)$. In particular, \eqref{ineq:Batyrev} holds trivially when $\lambda$ and $\lambda'$ span a face of $\Sigma_\Phi$.
\end{rem}
\begin{proof}[Proof of \cref{thm:main}, Part 1]
We know that the deformation cone $\df(\Sigma_\Phi)$ is given by the wall crossing inequalities of \cref{lem:wallcross}. We first compute them for the walls of the fundamental domain $D$.
Let us apply \cref{defi:wallcross} to the wall $H_i = H_{\alpha_i}$ of $D$ orthogonal to the simple root $\alpha_i$, which separates the chambers $D$ and $s_i \cdot D$. Notice that the only ray of $D$ that is not on the wall $H_i$ is the one spanned by the fundamental weight $\lambda_i$. Similarly, the only ray of $s_iD$ that is not on $H_i$ is the one spanned by the weight $s_i \cdot \lambda_i$. Therefore we need to find the coefficients such that
\[
c \lambda_i + c' s_i \cdot \lambda_i = \sum_{j \neq i} c_j\lambda_j.
\]
Since $\lambda_i$ and $s_i \lambda_i$ are symmetric with respect to the wall $H_i$ the coefficients $c$ and $c'$ in the equation above are equal, and we may set them both equal to $1$. Then, to compute the coefficient $c_j$ for $j \neq i$, let us take the inner product of both sides with $\alpha_j$. We obtain that
\[
\langle s_i \cdot \lambda_i, \alpha_j \rangle = c_j,
\]
keeping in mind that the bases $\Delta = \{\alpha_1, \ldots, \alpha_d\}$ and $\{\lambda_1, \ldots, \lambda_d\}$ are dual, so $\langle \alpha_j, \lambda_k \rangle$ equals $1$ if $j=k$ and $0$ otherwise. Using the formula \eqref{eq:reflex} for the reflection $s_i$ we obtain $c_j=-A_{ij}$.
%\[
%c_j =
% \left\langle
%\lambda_i - 2\dfrac{\langle \alpha_i,\lambda_i\rangle}{\langle \alpha_i,\alpha_i\rangle}\alpha_i \, , \, \alpha_j
%\right\rangle =
%0 - 2\dfrac{\langle \alpha_i,\alpha_j \rangle}{\langle \alpha_i,\alpha_i\rangle}
%= -A_{ij}.
%\]
It follows that
\begin{equation} \label{eq:wall}
\lambda_i + s_i \cdot \lambda_i = \sum_{i\neq j} - A_{ij} \lambda_j,
\end{equation}
so the wall-crossing inequality is
\begin{equation}\label{ineq:wallcox}
h(\lambda_i) + h(s_i \cdot \lambda_i)
\geq
\sum_{j\neq i} -A_{ij} h(\lambda_j),
\end{equation}
in agreement with \eqref{ineq:localsubmod}.
Let us now compute the wall-crossing inequality for a general wall $wH_i$, which separates chambers $w \cdot D$ and $ws_i \cdot D$. The rays of these chambers that are not on the wall are spanned by $w\cdot \lambda_i$ and $w s_i \cdot \lambda_i$, respectively. Since $W$ acts linearly, \eqref{eq:wall} implies the linear relation
\[
w\cdot \lambda_i + w s_i \cdot \lambda_i \geq \sum_{j \neq i} - A_{ij} w \cdot \lambda_j.
\]
Therefore the wall-crossing inequalities are indeed the ones given in \eqref{ineq:localsubmod}.
\end{proof}
%Before proving Theorem \ref{thm:main}.2], we introduce a directed graph $G(W)$ on the set $\W$ of weights of $\Sigma_\Phi$, defined as follows. Fix any ordering of the fundamental weights as $\lambda_1 < \cdots < \lambda_d$, and recall that any weight can be written as $w \cdot \lambda_i$ for a unique $i$. There is an edge in $G(W)$ between any two weights $\mu, \mu' \in \W$ that are in the same chamber $wD$ for some $w$, directed
%\[
%\mu \rightarrow \mu' \qquad \textrm{ if and only if } \qquad \mu = w \lambda_i \textrm{ and } \mu' = w\lambda_j \textrm{ for some } 1\leq ii$}) \to s_i \lambda_i\to \cdots$$
%which is a contradiction since there is no path from $\lambda_{k>i}$ to $s_i\lambda_i$.
%\textcolor{red}{I'm not sure I understand / buy this argument. Why should this path start at $\lambda_i$ and end at $s_i \cdot \lambda_i$?}
%\end{proof}
\begin{proof}[Proof of \cref{thm:main}, Part 2]
Sketch: This follows from Batyrev's criterion (\cref{lem:Batyrev}) and the fact that the Coxeter complex is flag.
\end{proof}
\begin{ex}
In type $A$, when $W=S_d$, the weights $\W$ are in bijection with the subsets of $[d]$. The local submodular inequalities produced by \cref{thm:main} say that
\[
h(A \cup b) + h(A \cup c) \geq h(A) + h(A \cup b \cup c) \qquad \textrm{ for } A \subset [d] \textrm{ and } b,c \notin A,
\]
whereas the global submodular inequalities say that
\[
h(B) + h(C) \geq h (B \cup C) + h(B \cap C) \qquad \textrm{ for } B, C \subseteq [d].
\]
The second set of inequalities is the usual definition of submodularity, but it is known in the optimization literature that the first subset of conditions (which corresponds to $B = A \cup b$ and $C = A \cup c$) minimally determine the others. The same phenomenon happens in all Coxeter types.
\end{ex}
%
%\begin{lem}\label{lemma:prim}
%The primitive collections of the rays $\Sigma_\Phi(1)$ in the fan associated to $W$ are exactly pairs $\{\lambda,\lambda'\}$ that do not form a cone.
%\end{lem}
%
%\begin{proof}[Proof of \ref{lem:prim}]
%That the pairs described in the propositions are primitive is clear. For the converse, if $\{u_1, \ldots, u_k\}$ is a primitive collection with $k>2$, then without loss of generality we have a path $u_1 \to u_2 \to \cdots \to u_{k-1}$. Now, as there is an edge between $u_i$ and $u_k$ for each $i=1, \ldots, k-1$, we have that $u_k$ fits into a path $u_1 \to \cdots u_i \to u_k \to u_{i+1} \to \cdots u_{k-1}$ for some $i=0, \ldots, k-1$.
%\textcolor{red}{Apparently this is
%\end{proof}
%
%The result follows.
%\end{proof}
\section{Facets of the $\Phi$-submodular cone}
In this section we enumerate the facets of the $\Phi$-submodular cone, after proving that they are precisely given by the wall crossing inequalities \eqref{ineq:wallcox}.
It is not always the case that every wall-crossing inequality for a fan $\Sigma$ defines a facet of the deformation cone $\operatorname{Def}(\Sigma)$. To prove it in this special case $\Sigma = \Sigma_\Phi$, we will show equivalently that the rays spanned by $I_{\tau}$ are extremal in the Mori cone
$\overline{NE}(\Sigma_\Phi) = \textrm{cone}(I_{\tau} \, : \, \tau \textrm{ is a wall of } \Sigma_\Phi)$ in $\left(\operatorname{PL}(\Sigma_\Phi)\right)^\vee$.
Before proving this, it is useful to remark that the action of $W$ on the Coxeter complex naturally gives rise to actions of $W$ on the vector space $\PL(\Sigma_\Phi)$, the deformation cone $\df(\Sigma_\Phi) \subset \PL(\Sigma_\Phi)$, and the Mori cone $\overline{NE}(\Sigma_\Phi) \subset \left(\operatorname{PL}(\Sigma_\Phi)\right)^\vee$.
\begin{thm}\label{thm:facet}
Every local $\Phi$-submodular inequality \eqref{ineq:localsubmod} is a facet of the $W$-submodular cone.
\end{thm}
\begin{proof}
By \cref{prop:orbit} and the comment following it, we can produce, for each $1 \leq i \leq d$, a generalized $\Phi$-permutahedron $Q_i$ whose normal fan is obtained from $\Sigma_\Phi$ by removing the walls $wH_i$ separating chambers $w \cdot D$ and $ws_i \cdot D$ for all $w\in W$. The support function of this polytope satisfies
\begin{eqnarray}
I_{\tau}^\Sigma(h_{Q_i}) &=& 0, \quad \textrm{ if } \tau= wH_i \textrm{ for some } w\in W, \textrm{ and } \label{eq:trick}\\
I_{\tau}^\Sigma(h_{Q_i}) &>& 0, \quad \textrm{ otherwise}.
\end{eqnarray}
This means that the set of rays $\{I_{wH_i} \, : \, w\in W\}$ form a face $F_i$ of the Mori cone, so at least one of them must be extremal. But these rays form an orbit of the action of $W$ on the Mori cone, so if one of them is extremal, all are extremal.
\end{proof}
\begin{thm}\label{thm:count}
The number of facets of the $\Phi$-submodular cone is equal to
\[
\displaystyle \sum_{i=1}^d \dfrac{|W|}{|W_{[d]-N(i)}|},
\]
where $N(i)$ is the set of neighbors of $i$ in the Dynkin diagram and $W_{[d]-N(i)}$ is the parabolic subgroup generated by the complement of $N(i)$.
\end{thm}
\begin{proof}[Sketch of Proof:]
We have one inequality for each pair of an element $1 \leq i \leq d$ and a group element $w \in W$, but there are many repetitions. For each $i$ we claim that the set of elements $w$ stabilizing the wall-crossing inequality \eqref{ineq:wallcox} is $W_{[d]-N(i)}$.
If an element $w$ stabilizes \eqref{ineq:wallcox}, it must stabilize the support of the right hand side, that is, the set of weights $\{\lambda_j \, : \, A_{ij} \neq 0\} = \{\lambda_j \, : \, j \in N(i)\}$. Therefore $w$ stabilizes the sum of those weights, which is in the interior of cone $C_{[d]-N(i)}$. By \cref{prop:stab}, $w \in W_{[d]-N(i)}$.
Conversely, suppose $w \in W_{[d]-N(i)}$. Then for each $j \in N(i)$ we have $w \in W_{[d]-j}$, so $w$ stabilizes $\lambda_j$ individually. Therefore $w$ does stabilize the right hand side of \eqref{ineq:wallcox}. Now, each simple reflection $s_k$ with $k \notin [d]-N(i)-i$ stabilizes $\lambda_i$ because $k \neq i$, and it stabilizes $s_i \cdot \lambda_i$ since $s_i$ and $s_k$ commute. The remaining reflection $s_i$ interchanges $\lambda_i$ and $s_i \cdot \lambda_i$. It follows that each generator of $W_{[d]-N(i)}$, and hence the whole parabolic subgroup, stabilizes the left-hand side of \eqref{ineq:wallcox} as well.
We conclude that, for fixed $i$, each inequality in \eqref{ineq:wallcox} is repeated ${|W_{[d]-N(i)}|}$, and hence the number of different inequalities is ${|W|}/{|W_{[d]-N(i)}|}$. The desired result follows.
%
%
%
%We first prove that the pointwise stabilizer of the set $\{\lambda_i,s_i\lambda_i\}$ is the parabolic subgroup $W_{[d]\backslash N(i)\backslash i}$.
% By Theorem \ref{thm:isotropy}, this is the subgroup generated by the reflections $s_\alpha$ that fix them both. The set of reflections which $\lambda_i$ belongs to is exactly the simple reflections $s_j$ with $j\neq i$. Now assume $s_j(s_i\lambda_i)= s_i\lambda_i$ or equivalently, $s_is_js_i$ fixes $\lambda_i$ with $j\neq i$. Again by Theorem \ref{thm:isotropy} $s_is_js_i\in W_{[d]\backslash i}$ and this can only happen if $j\notin N(i)$. Indeed, $s_is_js_i$ can't be reduced since it uses $s_i$, so strong exchange says that either $s_is_js_i=s_j$ or $s_i$. That is equivalent to commuting or $j\notin N(i)$.
%
%But also an element $w$ can stabilize the subset $\{\lambda_i,s_i\lambda_i\}$ by exchanging the two elements. In this case $w$ stabilizes the vector $\lambda_i+s_i\lambda_i$. Once again, Theorem \ref{thm:isotropy} says that the stabilizer of $\lambda_i+s_i\lambda_i$ is generated by the reflections fixing it. A similar reasoning as above shows that the stabilizer is $W_{[d]\backslash N(i)}$.
%
%Hence if $w$ fixes the subset $\{\lambda_i,s_i\lambda_i\}$ be it pointwise or by exchanging, then $w\in W_{[d]\backslash N(i)}$. Alternatively, all such elements fixes the subset. Conclusion follows.
\end{proof}
\acknowledgements{Part of this work was carried out while FA, FC, and AP were in residence at the Mathematical Sciences Research Institute in Berkeley, California, in the Fall of 2017. We thank MSRI and the organizers of the program in Geometric and Topological Combinatorics for providing the ideal conditions to carry out this work.}
%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography
\end{document}