# Bruhat intervals, subword complexes and brick polyhedra for finite Coxeter
groups

Dennis Jahn  Fakultät für Mathematik, Ruhr-Universität Bochum, Germany
<EMAIL_ADDRESS>and  Christian Stump  Fakultät für Mathematik, Ruhr-
Universität Bochum, Germany<EMAIL_ADDRESS>
###### Abstract.

We study the interplay between the discrete geometry of Bruhat poset intervals
and subword complexes of finite Coxeter systems. We establish connections
between the cones generated by cover labels for Bruhat intervals and of root
configurations for subword complexes, culminating in the notion of brick
polyhedra for general subword complexes.

The authors are supported by the DFG Heisenberg grant STU 563/4-1 “Noncrossing
phenomena in Algebra and Geometry”.

###### Contents

  1. 1 Introduction
  2. 2 Background on Coxeter systems and subword complexes
    1. 2.1 Reduced words and weak order
    2. 2.2 Bruhat order
    3. 2.3 The Demazure product
    4. 2.4 Subword complexes for Coxeter systems
    5. 2.5 Ongoing examples
  3. 3 The interplay between Bruhat intervals and subword complexes
    1. 3.1 Properties of Bruhat cones
    2. 3.2 Bruhat cones and non-flipable vertices in subword complexes
    3. 3.3 Constructing antigreedy facets inside certain half-spaces
    4. 3.4 Uniqueness of $f$-antigreedy facets
  4. 4 Brick polyhedra for subword complexes
    1. 4.1 Local cones of brick polyhedra at brick vectors
    2. 4.2 Normal fans of brick polyhedra from Coxeter fans
    3. 4.3 Containment properties of brick polyhedra for a fixed word

##  1\. Introduction

This paper develops the relationship between Bruhat intervals in finite
Coxeter groups and subword complexes by describing the interplay between
Bruhat interval cones and root configurations. Based on this newly developed
relationship, properties of brick polytopes for spherical root-independent
subword complexes are extended towards general subword complexes by
introducing _brick polyhedra_.

Bruhat interval cones were introduced and studied by Dyer in the study of
positivity properties of Kazhdan-Lusztig and Stanley polynomials [Dye94].
Subword complexes are simplicial complexes that have been introduced by
Knutson and Miller in the context of Gröbner geometry of Schubert varieties
[KM04, KM05]. Based on the notion of root configurations from [CLS14], this
paper reconsiders the combinatorial and discrete-geometric understanding of
subword complexes by closely tightening them to Dyer’s Bruhat interval cones.

Brick polytopes for spherical root-independent subword complexes were
introduced and studied by Pilaud and Stump [PS15]. These generalized brick
polytopes for sorting networks by Pilaud and Santos [PS12]. As shown by
Ceballos, Labbé and Stump in [CLS14], cluster complexes of finite type cluster
algebras can be realized as spherical root-independent subword complexes and
one main motivation for studying brick polytopes in [PS15] was to show that
generalized associahedra for cluster algebras previously constructed by
Chapoton, Fomin and Zelevinsky [CFZ02] and by Hohlweg, Lange and Thomas
[HLT11] can be realized as brick polytopes.

Motivated by the conjecture that important properties of brick polytopes for
spherical root-independent subword complexes hold for all spherical subword
complexes [PS15, Conjecture 7.1], this paper introduces and studies brick
polyhedra for general (spherical and non-spherical) subword complexes of
finite type. It turns out that subtle properties of Bruhat interval cones are
at the core of their understanding.

Subword complexes have a canonical recursive decomposition into smaller
subword complexes. Previous considerations in [CLS14, PS15] were mainly
developed for spherical subword complexes which are not closed und this
recursive structure. The presented constructions still rely on elementary
properties of the two fundamental notions _root_ and _weight functions_ for
subword complexes. Otherwise, all constructions are based on newly developed
properties of Bruhat interval cones that are then applied to general subword
complexes.

This newly presented approach allows inductive arguments using the recursive
structure as done in the proof of Proposition 3.14. This is then used to
deduce the uniqueness properties of certain facets constructed in 3.16 that in
turn are the central ingredient in the structural understanding of the
construction of brick polyhedra. After recalling standard notions and
properties of finite type Coxeter groups, their root systems and their subword
complexes in Section 2, we start the discussion of the interplay between
Bruhat intervals and subword complexes in Section 3. The main results of this
interplay are the following, we refer below for proper definitions. Let
$(W,\mathcal{S})$ be a finite Coxeter system and let $\mathcal{SC}({\rm Q},w)$
be a subword complex associated to a word ${\rm Q}$ in the simple reflections
$\mathcal{S}$ with Demazure product ${\operatorname{Dem}}({\rm Q})$ and an
element $w\in W$ in the Coxeter group.

  * •

Theorem 3.1 yields that the Bruhat interval cone of the Bruhat interval
$[w,{\operatorname{Dem}}({\rm Q})]$ equals the intersection of all cones over
root configurations of $\mathcal{SC}({\rm Q},w)$.

  * •

Theorem 3.4 and Corollaries 3.5, LABEL: and 3.6 exhibits containment
properties of Bruhat interval cones that are fundamental for all further
considerations.

  * •

Proposition 3.9 shows that the Bruhat interval cone describes the non-
flippable vertices in facets.

  * •

3.16 provides an algorithm to compute $f$-antigreedy facets for linear
functionals $f$ that are non-negative on the Bruhat interval cone.

  * •

Based on this algorithm, Corollary 3.24 proves [PS15, Conjeture 7.1] for
general subword complexes.

Section 4 then introduces and studies brick polyhedra of subword complexes.

  * •

Definition 4.1 defines the brick polyhedron of a finite type subword complex.

  * •

Theorem 4.4 shows that the local cone of the brick polyhedron at a brick
vector coincides with the cone over the root configuration.

  * •

Theorem 4.17 shows how to glue together chambers in the Coxeter fan to obtain
the normal fan of the brick polyhedron.

  * •

Theorem 4.21 shows that all brick polyhedra for a fixed word are contained in
each other in a natural way.

##  2\. Background on Coxeter systems and subword complexes

This section recalls standard notions for finite Coxeter systems. These are
mostly following the notions from [CLS14, PS15]. We also refer to [BB05] for
further background material. Ongoing examples are collected in Section 2.5.

Let ${(W,\mathcal{S})}$ be a finite type Coxeter system of rank
$n=|\mathcal{S}|$ acting on a Euclidean vector space $V\cong\mathbb{R}^{n}$
with inner form $\langle\cdot,\cdot\rangle$. Let
$\Delta\subseteq\Phi^{+}\subseteq\Phi\subseteq V$ be a root system for
${(W,\mathcal{S})}$ with simple roots
$\Delta=\left\\{\alpha_{s}\;|\;s\in\mathcal{S}\right\\}$, positive roots
$\Phi^{+}$, and negative roots $\Phi^{-}=-\Phi^{+}$. For $\beta\in\Phi$ we
write $|\beta|\in\Phi^{+}$ for the positive root in $\\{\pm\beta\\}$. The
reflections in $W$ are
$\mathcal{R}=\left\\{s_{\beta}\;|\;\beta\in\Phi^{+}\right\\}$ where
$s_{\beta}$ denotes the reflection sending $\beta$ to its negative while
fixing pointwise its orthogonal complement $\beta^{\perp}=\left\\{v\in
V\;|\;\langle\beta,v\rangle=0\right\\}$.

The corresponding Cartan matrix $(a_{st})_{s,t\in\mathcal{S}}$ is given by
$s(\alpha_{t})=\alpha_{t}-a_{st}\alpha_{s}$. The fundamental weights
$\nabla=\left\\{\omega_{s}\;|\;s\in\mathcal{S}\right\\}\subseteq V$ are then
$\alpha_{s}=\sum_{t\in\mathcal{S}}a_{ts}\omega_{t}$ and $W$ acts on the
fundamental weights by $s(\omega_{t})=\omega_{t}-\delta_{s=t}\alpha_{s}$ for
$s,t\in\mathcal{S}$.

###  2.1. Reduced words and weak order

The _length_ $\ell(w)$ of an element $w\in W$ is the smallest length of a word
${\rm s}_{1}\dots\rm s_{\ell(w)}$ such that its product is an expression
$w=s_{1}\cdots s_{\ell(w)}$ for $w$. Words (and also expressions) of smallest
length are called _reduced_. Here and below, we mildly distinguish between
words in $\mathcal{S}$ and the corresponding expressions for elements in $W$
by writing ${\rm s}_{1}\dots\rm s_{\ell}\in\mathcal{S}^{*}$ for the word and
$s_{1}\cdots s_{\ell}\in W$ for the expression. It is well-known that for
$w\in W,s\in\mathcal{S}$ we have

(2.1) $\ell(ws)=\begin{cases}\ell(w)+1&\text{ if }w(\alpha_{s})\in\Phi^{+}\\\
\ell(w)-1&\text{ if }w(\alpha_{s})\in\Phi^{-}\end{cases}\ .$

This in particular means that a word ${\rm s}_{1}\dots\rm s_{\ell}$ is reduced
if and only if for all $1<i\leq\ell$ we have $s_{1}\cdots
s_{i-1}(\alpha_{s_{i}})\in\Phi^{+}$. The _(right) weak order_
$\leq_{\mathsf{R}}$ on $W$ is the partial order defined by the cover relations
$w\prec_{\mathsf{R}}ws$ for $w\in W,s\in\mathcal{S}$ with
$\ell(ws)=\ell(w)+1$. The _inversion set_ of an element $w\in W$ with reduced
expression $w=s_{1}\cdots s_{\ell}$ is given by

(2.2) $\operatorname{Inv}(w)=\left\\{s_{1}\cdots
s_{k-1}(\alpha_{s_{k}})\;\big{|}\;1\leq k\leq\ell\right\\}.$

This is independent of the chosen reduced word and it is not hard to see that
$\operatorname{Inv}(w)=\Phi^{+}\,\cap\,w(\Phi^{-})$. In particular,
$\ell(w)=|\operatorname{Inv}(w)|$ and
$x\leq_{\mathsf{R}}y\Leftrightarrow\operatorname{Inv}(x)\subseteq\operatorname{Inv}(y)$.
The _longest element_ ${w_{\circ}}\in W$ is the unique element of longest
length $|\Phi^{+}|$ which is equivalently described as the unique element with
$\operatorname{Inv}({w_{\circ}})=\Phi^{+}$. For any $w\in W$, we have a
decomposition

(2.3)
$\Phi^{+}=\operatorname{Inv}(w)\sqcup\operatorname{Inv}(w\cdot{w_{\circ}}),$

and a subset $X\subseteq\Phi^{+}$ is the inversion set of an element if and
only if $X$ and $\Phi^{+}\setminus X$ are separated by a hyperplane, i.e.,
there is a linear functional $f:V\rightarrow\mathbb{R}$ such that for all
$\beta\in\Phi^{+}$, we have

(2.4) $f(\beta)>0\Longleftrightarrow\beta\in X.$

We record the following well-known lemma.

######  Lemma 2.1 ([BB05, Lemma 1.4.4]).

Let $w\in W$ with reduced expression $w=s_{1}\cdots s_{\ell}$ and let
$s_{\beta}\in\mathcal{R}$. Then the following properties are equivalent:

  1. (a)

$\ell(s_{\beta}w)<\ell(w)$,

  2. (b)

$s_{\beta}w=s_{1}\cdots\widehat{s}_{k}\cdots s_{\ell}$ for some index $k$,

  3. (c)

$\beta=s_{1}\cdots s_{k-1}(\alpha_{s_{k}})$ for some index $k$.

Moreover, the index $k$ is unique in both cases.

Since (c) is the defining property for $\beta$ to be an inversion of $w$, we
obtain from this lemma that

(2.5)
$\operatorname{Inv}(w)=\left\\{\beta\in\Phi^{+}\;\big{|}\;\ell(s_{\beta}w)<\ell(w)\right\\}.$

###  2.2. Bruhat order

The _Bruhat order_ $\leq$ on $W$ is the partial order defined by the cover
relations $w\prec rw$ for $w\in W,r\in\mathcal{R}$ with $\ell(rw)=\ell(w)+1$.
Observe that $w\prec_{\mathsf{R}}ws\Rightarrow w\prec ws$ because
$ws=(wsw^{-1})w$ for $wsw^{-1}\in\mathcal{R}$. For the positive root
$\beta\in\Phi^{+}$ with $r=s_{\beta}$, we say that the cover relation $w\prec
rw$ is _labelled by_ $\beta$. In particular, the cover $w\prec ws$ is labelled
by $w(\alpha_{s})$ which is a positive root by (2.1). A _Bruhat interval_
$[x,y]$ is defined for $x\leq y$ in Bruhat order by

$[x,y]=\left\\{z\in W\;\big{|}\;x\leq z\leq y\right\\}.$

The following properties of the Bruhat order are needed in subsequent
sections.

######  Lemma 2.2 ([BB05, Proposition 2.2.7]).

Let $x,y\in W$ and $s\in\mathcal{S}$ such that $x\leq y$, $x\prec sx$ and
$sy\prec y$. Then $x\leq sy$ and $sx\leq y$.

This lemma immediately yields the following known lifting property for Bruhat
intervals.

######  Corollary 2.3.

Let $x,y\in W$ and $s\in\mathcal{S}$ such that $x\leq y$, $x\prec sx$,
$sy\prec y$ and $sx\not\leq sy$. Then $[x,sy]\cong[sx,y]$ and the isomorphism
is given by $w\mapsto sw$.

######  Lemma 2.4 ([BB05, Corollary 2.2.8]).

Let $w\in W$, $s\in\mathcal{S}$ and $r\in\mathcal{R}$ such that $s\neq r$ and
$w\prec sw,rw$. Then $sw,rw\prec srw$.

Putting these properties together, we obtain the following proposition.

######  Proposition 2.5.

Let $x,y\in W$, $s\in\mathcal{S}$ and $r\in\mathcal{R}$ such that $s\neq r$
and $x\prec sx,rx\leq y$. If moreover $srx\not\leq y$ then $y\prec sy$,
$srx\leq sy$ and $[rx,y]\cong[srx,sy]$.

###### Proof.

Lemma 2.4 yields $x\prec sx,rx\prec srx$. Assuming $sy\prec y$ and applying
Lemma 2.2 to $rx\prec srx$ and to $sy\prec y$ would imply $srx\leq y$, a
contradiction. Hence $y\prec sy$. Again by Lemma 2.2 applied to $rx\prec srx$
and to $y\prec sy$ we obtain $srx\leq sy$ and by Corollary 2.3 we get
$[rx,y]\cong[srx,sy]$. ∎

For later reference, we further recollect the following property.

######  Lemma 2.6 ([BB05, Lemma 2.2.10]).

Let $x,y\in W$ and $r\in\mathcal{R}$. If both, $x\leq xr$ and $y\leq ry$, then
$xy\leq xry$.

###  2.3. The Demazure product

For a (not necessarily reduced) word ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$ in
$\mathcal{S}$ and a subset $X\subseteq\\{1,\dots,m\\}$, we write ${\rm Q}_{X}$
to be the subword of ${\rm Q}$ of the letters ${\rm s}_{i}$ with $i\in X$. The
_Demazure product_ ${\operatorname{Dem}}({\rm Q})\in W$ may be defined in
terms of the weak order recursively by

${\operatorname{Dem}}({\rm Q})=\begin{cases}{\operatorname{Dem}}({\rm
Q}_{\\{1,\dots,m-1\\}})\cdot s_{m}&\text{ if }{\operatorname{Dem}}({\rm
Q}_{\\{1,\dots,m-1\\}})(\alpha_{s_{m}})\in\Phi^{+}\\\
{\operatorname{Dem}}({\rm Q}_{\\{1,\dots,m-1\\}})&\text{ if
}{\operatorname{Dem}}({\rm
Q}_{\\{1,\dots,m-1\\}})(\alpha_{s_{m}})\in\Phi^{-}\end{cases}\ ,$

with initial condition ${\operatorname{Dem}}({\varepsilon})={e}\in W$ for the
empty word ${\varepsilon}$. By (2.1), these conditions say that the Demazure
product of ${\rm Q}$ is obtained by scanning through ${\rm Q}$ from left to
right, starting at the identity and going upwards in weak order whenever
possible. One may equivalently define the Demazure product in terms of the
Bruhat order as the unique maximal element in Bruhat order among all
expressions obtained from the word ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$ by
removing letters,

(2.6) ${\operatorname{Dem}}({\rm Q})=\max{}_{\leq}\left\\{\Pi{{\rm
Q}}_{X}\;\big{|}\;X\subseteq\\{1,\dots,m\\}\right\\}.$

Here and below, $\Pi{{\rm Q}}_{X}\in W$ denotes the product of the simple
reflections $s_{i}$ with $i\in X$ in the given order.

###  2.4. Subword complexes for Coxeter systems

For $w\in W$ and ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$, the _subword complex_
$\mathcal{SC}({\rm Q},w)$ is the simplicial complex of sets of (positions of)
letters in ${\rm Q}$ whose complements contain reduced words for $w$. Knutson
and Miller introduced subword complexes in the context of Gröbner geometry of
Schubert varieties [KM04, KM05]. By (2.6), $\mathcal{SC}({\rm Q},w)$ is non-
empty if and only if $w\leq{\operatorname{Dem}}({\rm Q})$. Facets of
$\mathcal{SC}({\rm Q},w)$ are subwords of ${\rm Q}$ whose complements are
reduced words for $w$. As shown in [KM04, Theorem 3.7, Corollary 3.8] the non-
empty complex $\mathcal{SC}({\rm Q},w)$ is a topological sphere if and only if
$w={\operatorname{Dem}}({\rm Q})$ and a topological ball otherwise. In these
cases we call $\mathcal{SC}({\rm Q},w)$ _spherical_ and _non-spherical_ ,
respectively.

For two facets $I\neq J$ of $\mathcal{SC}({\rm Q},w)$ we say $I$ and $J$ are
_adjacent_ if there are $i\in I$ and $j\in J$ such that
$I\setminus\\{i\\}=J\setminus\\{j\\}$. We call the transition from $I$ to $J$
the _flip_ of $i$ in $I$ and furthermore say the flip is _increasing_ if $i<j$
and _decreasing_ otherwise. The _root function_ ${{\sf
r}}(I,\cdot):[m]\rightarrow\Phi=W(\Delta)\subseteq V$ is defined by

${{\sf r}}(I,k)=\Pi{{\rm Q}}_{\\{1,\dots,k-1\\}\setminus I}(\alpha_{s_{k}}).$

As above, $\Pi{{\rm Q}}_{X}$ denotes the product of the simple reflections
$s_{i}$, for $i\in X$ in the given order. Observe here that the root ${{\sf
r}}(I,k)$ only depends on $I\cap\\{1,\dots,k-1\\}$ and not on the complete
facet $I$. The ordered multiset111We think of facets of subword complexes as
being _ordered sets_ (sorted lists of indices written in set notation) and we
think of root configurations of facets as _ordered multisets_ (lists of roots
written in multiset notation with ordering inherited from the order of the
facet). ${{\sf R}}(I)=\left\\{\\!\\!\left\\{{{\sf r}}(I,i)\;|\;i\in
I\right\\}\\!\\!\right\\}$ is called _root configuration_ of the facet $I$.

The following lemma recalls several properties of flips in subword complexes
in terms of root configurations. These can be found in [PS13, Proposition 2].

######  Lemma 2.7.

Let $I$ be a facet of the non-empty subword complex $\mathcal{SC}({\rm Q},w)$.

  1. (a)

The map ${{\sf r}}(I,\cdot):k\mapsto{{\sf r}}(I,k)$ is a bijection between the
complement of $I$ and $\operatorname{Inv}(w)$.

  2. (b)

For $i\in I$, there exists a facet $J$ and an index $j\in J$ such that
$I\setminus\\{i\\}=J\setminus\\{j\\}$ if and only if $|{{\sf
r}}(I,i)|\in\operatorname{Inv}(w)$. In this case, the index $j$ is the unique
position in the complement of $I$ for which ${{\sf r}}(I,j)=|{{\sf r}}(I,i)|$
and the sign is determined by

${{\sf r}}(I,j)=\begin{cases}{{\sf r}}(I,i)&\text{if }i<j,\\\ -{{\sf
r}}(I,i)&\text{if }i>j.\end{cases}$

  3. (c)

In the situation of (b), the map ${{\sf r}}(J,\cdot)$ is obtained from ${{\sf
r}}(I,\cdot)$ by

${{\sf r}}(J,k)=\begin{cases}s_{{{\sf r}}(I,i)}\big{(}{{\sf
r}}(I,k)\big{)}&\text{if }\min(i,j)<k\leq\max(i,j),\\\ {{\sf
r}}(I,k)&\text{otherwise. }\end{cases}$

Non-empty subword complexes come with two extremal facets. Considering facets
as ordered sets1, the _greedy facet_ $I_{\operatorname{g}}$ is the
lexicographically first facet and the _antigreedy facet_
$I_{\operatorname{ag}}$ is the lexicographically last facet. Using Lemma 2.7,
one can describe these greedy facets by their root configurations. We also
refer to [PS13, Section 4.2] for a discussion of greedy facets.

######  Lemma 2.8.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex. Its greedy facet
$I_{\operatorname{g}}$ is the unique facet with ${{\sf
R}}(I_{\operatorname{g}})\subseteq\Phi^{+}$ and its antigreedy facet
$I_{\operatorname{ag}}$ is the unique facet with ${{\sf
R}}(I_{\operatorname{ag}})\subseteq w(\Phi^{+})$.

###### Proof.

As shown in [PS13, Proposition 6], the greedy facet is the unique facet for
which all flips are increasing, and the antigreedy facet is the unique facet
for which all flips are decreasing. These properties are equivalent to the
respective descriptions in terms of root configurations: For the greedy facet,
this immediately follows from Lemma 2.7(b), while it follows for the
antigreedy facet from this lemma together with the computation

$\displaystyle{{\sf R}}(I_{\operatorname{ag}})$
$\displaystyle\subseteq\big{(}\Phi^{+}\setminus\operatorname{Inv}(w)\big{)}\cup-\operatorname{Inv}(w)$
$\displaystyle=\big{(}\Phi^{+}\setminus\big{(}\Phi^{+}\cap-w(\Phi^{+})\big{)}\big{)}\cup\big{(}\Phi^{-}\cap
w(\Phi^{+})\big{)}$ $\displaystyle=\big{(}\Phi^{+}\cap
w(\Phi^{+})\big{)}\cup\big{(}\Phi^{-}\cap w(\Phi^{+})\big{)}$
$\displaystyle=w(\Phi^{+}),$

where the first inclusion is the describing property that all flips are
decreasing and the others are elementary reformulations. ∎

###  2.5. Ongoing examples

Throughout this paper we present examples in Coxeter systems of types $A_{2}$,
$B_{2}$ and $B_{3}$. We generally write $\mathcal{S}=\\{s_{1},\dots,s_{n}\\}$
for concrete generators $s_{i}$ and also
$\Delta=\\{\alpha_{1},\dots,\alpha_{n}\\}$ for simple roots with
$\alpha_{i}=\alpha_{s_{i}}$. To keep examples compact, we write shorthand
${\rm Q}=123212={\rm s}_{1}{\rm s}_{2}{\rm s}_{3}{\rm s}_{2}{\rm s}_{1}{\rm
s}_{2}$ for words in $\mathcal{S}$ and also for elements
$w=1231=s_{1}s_{2}s_{3}s_{1}\in W$ as reduced words, and we abbreviate
${{213}_{\Delta}}=2\alpha_{1}+\alpha_{2}+3\alpha_{3}$ and
${\overline{213}_{\Delta}}=-{{213}_{\Delta}}$ for vectors written in the basis
of simple roots.

######  Example 2.9 (Type $A_{2}$).

We have $\mathcal{S}=\\{s_{1},s_{2}\\}$, the simple and positive roots
$\Delta\subset\Phi^{+}$ given by
$\\{{{10}_{\Delta}},{{01}_{\Delta}}\\}\subset\\{{{10}_{\Delta}},{{01}_{\Delta}},{{11}_{\Delta}}\\}$
and

$s_{1}({{10}_{\Delta}})={\overline{10}_{\Delta}},\quad
s_{1}({{01}_{\Delta}})={{11}_{\Delta}},\quad
s_{2}({{10}_{\Delta}})={{11}_{\Delta}},\quad
s_{2}({{01}_{\Delta}})={\overline{01}_{\Delta}}.$

The fundamental weights are
$\nabla=\\{\omega_{1}=\tfrac{1}{3}({{21}_{\Delta}}),\omega_{2}=\tfrac{1}{3}({{12}_{\Delta}})\\}.$

######  Example 2.10 (Type $B_{2}$).

We have $\mathcal{S}=\\{s_{1},s_{2}\\}$, the simple and positive roots
$\Delta\subset\Phi^{+}$ given by
$\\{{{10}_{\Delta}},{{01}_{\Delta}}\\}\subset\\{{{10}_{\Delta}},{{01}_{\Delta}},{{11}_{\Delta}},{{12}_{\Delta}}\\}$
and

$s_{1}({{10}_{\Delta}})={\overline{10}_{\Delta}},\quad
s_{1}({{01}_{\Delta}})={{11}_{\Delta}},\quad
s_{2}({{10}_{\Delta}})={{12}_{\Delta}},\quad
s_{2}({{01}_{\Delta}})={\overline{01}_{\Delta}}.$

The fundamental weights are
$\nabla=\\{\omega_{1}={{11}_{\Delta}},\omega_{2}=\tfrac{1}{2}({{12}_{\Delta}})\\}.$

######  Example 2.11 (Type $B_{3}$).

We have $\mathcal{S}=\\{s_{1},s_{2},s_{3}\\}$, the simple and positive roots
$\Delta\subset\Phi^{+}$ given by
$\\{{{100}_{\Delta}},{{010}_{\Delta}},{{001}_{\Delta}}\\}\subset\\{{{100}_{\Delta}},{{010}_{\Delta}},{{001}_{\Delta}},{{110}_{\Delta}},{{011}_{\Delta}},{{111}_{\Delta}},{{012}_{\Delta}},{{112}_{\Delta}},{{122}_{\Delta}}\\}$
and

$\displaystyle s_{1}({{100}_{\Delta}})={\overline{100}_{\Delta}},\quad
s_{1}({{010}_{\Delta}})={{110}_{\Delta}},\quad
s_{1}({{001}_{\Delta}})={{001}_{\Delta}},$ $\displaystyle
s_{2}({{100}_{\Delta}})={{110}_{\Delta}},\quad
s_{2}({{010}_{\Delta}})={\overline{010}_{\Delta}},\quad
s_{2}({{001}_{\Delta}})={{011}_{\Delta}},$ $\displaystyle
s_{3}({{100}_{\Delta}})={{100}_{\Delta}},\quad
s_{3}({{010}_{\Delta}})={{012}_{\Delta}},\quad
s_{3}({{001}_{\Delta}})={\overline{001}_{\Delta}},$

The fundamental weights are
$\nabla=\\{\omega_{1}=({{111}_{\Delta}}),\omega_{2}=({{110}_{\Delta}}),\omega_{3}=\tfrac{1}{2}({{112}_{\Delta}})\\}.$

##  3\. The interplay between Bruhat intervals and subword complexes

This section studies the interplay between Bruhat intervals and subword
complexes via root configurations. To this end, we recall the _(closed) cone_
over a finite set $X\subseteq V$ to be

$\operatorname{cone}(X)=\textstyle\sum_{v\in
X}\mathbb{R}_{+}v=\left\\{\textstyle\sum_{v\in
X}\lambda_{v}v\;|\;\lambda_{v}\geq 0\right\\}.$

The following notions of Bruhat cones were studied by Dyer in the context of
Kazhdan-Lusztig polynomials [Dye94]. For a Bruhat interval $[x,y]$, the _upper
Bruhat cone_ ${\mathcal{C}^{+}(x,y)}$ and the _lower Bruhat cone_
${\mathcal{C}^{-}(x,y)}$ are defined by
${\mathcal{C}^{+}(x,y)}=\operatorname{cone}{\mathcal{E}^{+}(x,y)}$ and
${\mathcal{C}^{-}(x,y)}=\operatorname{cone}{\mathcal{E}^{-}(x,y)}$ for

${\mathcal{E}^{+}(x,y)}=\left\\{\beta\in\Phi^{+}\;\big{|}\;x\prec
s_{\beta}x\leq
y\right\\},\quad{\mathcal{E}^{-}(x,y)}=\left\\{\beta\in\Phi^{+}\;\big{|}\;x\leq
s_{\beta}y\prec y\right\\}.$

This is, the upper Bruhat cone is the cone spanned by the labels of the atoms
in the Bruhat interval $[x,y]$ and the lower Bruhat cone is the cone spanned
by the labels of the coatoms. Since we mainly discuss upper Bruhat cones, we
simply call these _Bruhat cones_.

The goal of this section is to develop tools connecting Bruhat cones and root
configurations, culminating in the following theorem.

######  Theorem 3.1.

Let ${\rm Q}$ be a word in $\mathcal{S}$ and let $w\in W$ with
$w\leq{\operatorname{Dem}}({\rm Q})$. Then

${\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}=\bigcap_{I}\operatorname{cone}{{\sf R}}(I)$

where the intersection is taken over all facets $I$ of the subword complex
$\mathcal{SC}({\rm Q},w)$.

###  3.1. Properties of Bruhat cones

We first recall several properties of Bruhat cones from [Dye94] and then
exhibit further recursive properties of these.

######  Lemma 3.2.

[Dye94, Proposition 1.4, Proposition 3.6] Let $[x,y]$ be a Bruhat interval and
let $w\in W$. Then

  1. (a)

${\mathcal{C}^{-}(e,w)}\cap{\mathcal{C}^{+}(w,{w_{\circ}})}=\\{0\\}$ and
$\Phi^{+}\subseteq{\mathcal{C}^{-}({e},w)}\cup{\mathcal{C}^{+}(w,{w_{\circ}})}$.

  2. (b)

${\mathcal{E}^{+}(x,y)}$ are the rays of ${\mathcal{C}^{+}(x,y)}$ and
${\mathcal{E}^{-}(x,y)}$ are the rays of ${\mathcal{C}^{-}(x,y)}$.

  3. (c)

For $\beta\in{\mathcal{E}^{+}(x,y)}$ we have
${\mathcal{C}^{+}(x,y)}\subseteq{\mathcal{C}^{+}(s_{\beta}x,y)}+\mathbb{R}(\beta)$,
and similar for ${\mathcal{C}^{-}(x,y)}$.

  4. (d)

For $\beta\in\Phi^{+}$ with $x\leq s_{\beta}x\leq y$ we have
$\beta\in{\mathcal{C}^{+}(x,y)}$, and similar for ${\mathcal{C}^{-}(x,y)}$.

This lemma has the following consequence, which is interesting in itself while
not used in our further considerations. It can also be directly deduced from
(2.4) and (2.5).

######  Corollary 3.3.

Let $w\in W$. Then ${\mathcal{E}^{-}({e},w)}$ are the extremal rays of
$\operatorname{cone}\operatorname{Inv}(w)$ and
${\mathcal{E}^{+}(w,{w_{\circ}})}={\mathcal{E}^{-}({e},w\cdot{w_{\circ}})}$
are the extremal rays of
$\operatorname{cone}\operatorname{Inv}(w\cdot{w_{\circ}})$. In particular,

${\mathcal{C}^{-}({e},w)}\cap\Phi=\operatorname{Inv}(w),\quad{\mathcal{C}^{+}(w,{w_{\circ}})}\cap\Phi=\operatorname{Inv}(w\cdot{w_{\circ}}).$

###### Proof.

It is immediate from (2.5) that
${\mathcal{E}^{-}({e},w)}\subseteq\operatorname{Inv}(w)$, and thus
${\mathcal{E}^{+}(w,{w_{\circ}})}={\mathcal{E}^{-}({e},w\cdot{w_{\circ}})}\subseteq\operatorname{Inv}(w\cdot{w_{\circ}})$.
The statements then follow with (2.4) and (2.3) from Lemma 3.2(b) and (a). ∎

We provide the following additional properties needed in subsequent
considerations.

######  Theorem 3.4.

Let $x,y\in W$ and $s\in\mathcal{S}$ such that $x\leq y\prec sy$. Then

${\mathcal{C}^{+}(x,sy)}\subseteq{\mathcal{C}^{+}(x,y)}+\mathbb{R}_{+}(\alpha_{s}).$

######  Corollary 3.5.

Let $x,y\in W$ and $s\in\mathcal{S}$ such that $sx\prec x\leq y$. Let
furthermore $\tau\in\\{sy,y\\}$ be the Bruhat smaller element. Then

$s\big{(}{\mathcal{C}^{+}(x,y)}\big{)}\subseteq{\mathcal{C}^{+}(sx,\tau)}.$

We also need this corollary for the weak order, so we also provide that
version individually.

######  Corollary 3.6.

Let $x,y\in W$ and $s\in\mathcal{S}$ such that $xs\prec x\leq y$. Let
furthermore $\tau\in\\{ys,y\\}$ be the Bruhat smaller element. Then

${\mathcal{C}^{+}(x,y)}\subseteq{\mathcal{C}^{+}(xs,\tau)}.$

The first step in the proof is to strengthen Lemma 3.2(c) for simple roots in
${\mathcal{E}^{+}(x,y)}$ as follows.

######  Proposition 3.7.

Let $x,y\in W$, $s\in\mathcal{S}$ and $r=s_{\beta}\in\mathcal{R}$ such that
$s\neq r$ and $x\prec sx,rx\leq y$. Then

$s(\beta)\in{\mathcal{C}^{+}(sx,y)}+\mathbb{R}_{+}(\alpha_{s}).$

###### Proof.

By Lemma 2.4 we have $x\prec sx,rx\prec srx$ with $srx=s_{s(\beta)}sx$.

If $srx\leq y$ then
$s(\beta)\in{\mathcal{C}^{+}(sx,y)}\subseteq{\mathcal{C}^{+}(sx,y)}+\mathbb{R}_{+}(\alpha_{s})$
by definition, so we have to consider the situation $srx\not\leq y$. In this
case $s(\beta)\not\in{\mathcal{C}^{+}(sx,y)}$, and the situation with their
cover labels is

$x$$sx$$rx$$srx$$y$$sy$$\alpha_{s}$$\alpha_{s}$$\alpha_{s}$$\beta$$s(\beta)$

We may thus apply Proposition 2.5 and obtain $y\prec sy$, $srx\leq sy$ and
$[rx,y]\cong[srx,sy]$ given by $w\mapsto sw$, and get

($\ast$) ${\mathcal{C}^{+}(rx,y)}=s\big{(}{\mathcal{C}^{+}(srx,sy)}\big{)}.$

By Lemma 3.2(a) we have $\beta\not\in{\mathcal{C}^{+}(rx,sy)}$, and by Lemma
3.2(b) we have $\alpha_{s}\in{\mathcal{C}^{+}(rx,sy)}$ is a ray, implying in
particular $\alpha_{s}\not\in{\mathcal{C}^{+}(rx,y)}$. Because
$\alpha_{s}\in\Delta$ is simple and because
${\mathcal{C}^{+}(rx,y)}\subseteq{\mathcal{C}^{+}(rx,sy)}$ we obtain

${\mathcal{C}^{+}(rx,y)}\cap P\subseteq\mathbb{R}_{+}\\{\alpha_{s},\beta\\},$

where the situation is considered inside the two-dimensional plane
$P=\langle\alpha_{s},\beta\rangle_{\mathbb{R}}$. This situation is sketched as

$\alpha_{s}$$\beta$${\mathcal{C}^{+}(rx,sy)}$$s({\mathcal{C}^{+}(srx,sy)})$$={\mathcal{C}^{+}(rx,y)}$

Together with ($\ast$ ‣ 3.1), this implies

($\ast\ast$) $s(\beta)\in\big{(}{\mathcal{C}^{+}(srx,sy)}\cap
P\big{)}+\mathbb{R}_{+}(\alpha_{s}).$

By the assumption $x\prec rx\leq y$, we know $\beta\in{\mathcal{C}^{+}(x,y)}$.
Together with Lemma 3.2(c), this implies

($\ast\ast$$\ast$)
$\beta\in{\mathcal{C}^{+}(x,y)}\subseteq{\mathcal{C}^{+}(sx,y)}+\mathbb{R}(\alpha_{s}).$

The cone ${\mathcal{C}^{+}(sx,y)}$ therefore intersects the plane $P$ non-
trivially, ${\mathcal{C}^{+}(sx,y)}\cap P\neq\\{0\\}$. We have
${\mathcal{C}^{+}(sx,y)}\subseteq{\mathcal{C}^{+}(sx,sy)}$ by definition and
we have
${\mathcal{C}^{+}(sx,sy)}\subseteq{\mathcal{C}^{+}(srx,sy)}+\mathbb{R}(s(\beta))$
by Lemma 3.2(c). So we obtain
${\mathcal{C}^{+}(sx,y)}\subseteq{\mathcal{C}^{+}(srx,sy)}+\mathbb{R}(s(\beta))$,
sketched as

$\alpha_{s}$$s(\beta)$${\mathcal{C}^{+}(srx,sy)}$${\mathcal{C}^{+}(srx,sy)}+\mathbb{R}(s(\beta))$

Since ${\mathcal{C}^{+}(sx,y)}$ is spanned by positive roots, ($\ast\ast$ ‣
3.1) and ($\ast\ast$$\ast$ ‣ 3.1) finally yield

$s(\beta)\in\big{(}{\mathcal{C}^{+}(sx,y)}\cap
P\big{)}+\mathbb{R}_{+}(\alpha_{s})\subseteq{\mathcal{C}^{+}(sx,y)}+\mathbb{R}_{+}(\alpha_{s}).\qed$

The following example details the situation in the proof of Proposition 3.7.

######  Example 3.8 (Type $B_{3}$).

Let $x=13231$ and $r=s_{{{122}_{\Delta}}}$. Then

$s_{2}x=213231,\quad rx=132312,\quad s_{2}rx=2132312$

and we have $x\prec s_{2}x,rx\prec s_{2}rx$ in accordance with Lemma 2.4. Let
$y=32312321$ so that $s_{2}x,rx\leq y$ while $s_{2}rx\not\leq y$. We draw the
interval $[x,s_{2}y]$ where crucial cover relations and elements are drawn in
black while others are drawn in light grey for better readability.

$x=13231$$s_{2}x=213231$$rx=132312$$s_{2}rx=2132312$$3213231$$2312321$$3212321$$3231232$$y=32312321$$23212321$$23231232$$s_{2}y=232312321$$123231$$323123$${{010}_{\Delta}}$${{010}_{\Delta}}$${{010}_{\Delta}}$${{100}_{\Delta}}$${{100}_{\Delta}}$${{100}_{\Delta}}$${{100}_{\Delta}}$${{001}_{\Delta}}$${{001}_{\Delta}}$${{001}_{\Delta}}$${{001}_{\Delta}}$${{112}_{\Delta}}$${{122}_{\Delta}}$${{110}_{\Delta}}$${{110}_{\Delta}}$${{011}_{\Delta}}$${{011}_{\Delta}}$

We see $[rx,y]\cong[s_{2}rx,s_{2}y]$ realized by $w\mapsto s_{2}w$ as
predicted by Proposition 2.5 and furthermore

${\mathcal{C}^{+}(rx,y)}=\operatorname{cone}\\{{{110}_{\Delta}},{{011}_{\Delta}}\\}=s_{2}\big{(}\operatorname{cone}\\{{{100}_{\Delta}},{{001}_{\Delta}}\\}\big{)}=s_{2}\big{(}{\mathcal{C}^{+}(s_{2}rx,s_{2}y)}\big{)}.$

The plane ${P=\langle{{010}_{\Delta}},{{122}_{\Delta}}\rangle_{\mathbb{R}}}$
contains the sub root system of type $A_{2}$ with simple roots
$\Delta_{P}=\\{{{010}_{\Delta}},{{112}_{\Delta}}\\}$ and we have $\Phi^{+}\cap
P=\\{{{010}_{\Delta}},{{122}_{\Delta}},{{112}_{\Delta}}\\}$

${{010}_{\Delta}}$${{122}_{\Delta}}$${{112}_{\Delta}}$${{102}_{\Delta}}$${\mathcal{C}^{+}(s_{2}rx,s_{2}y)}\cap
P$${\mathcal{C}^{+}(rx,y)}\cap P$${\mathcal{C}^{+}(s_{2}x,y)}\cap P$

and see
$s_{2}({{122}_{\Delta}})={{112}_{\Delta}}\in{\mathcal{C}^{+}(s_{2}x,y)}+\operatorname{cone}\\{{{010}_{\Delta}}\\}$
as predicted by Proposition 3.7.

###### Proof of Theorem 3.4.

Let $r\in\mathcal{R}$ with $x\prec rx\leq sy$. If $rx\leq y$ or $r=s$ the
statement is trivial, so let $rx\not\leq y$ and $r\neq s$.

As $rx\leq sy$ while $rx\not\leq y$, we have $y\prec sy$. Hence there is a
reduced word for $sy$ that starts with the letter ${\rm s}$ and from which we
may delete letters to obtain a reduced word for $rx$. Observe that we must not
delete the initial letter ${\rm s}$ in this process, so we obtain a reduced
word for $rx$ with initial letter ${\rm s}$. Now by deleting this initial
${\rm s}$, we get $srx\prec rx$ and $srx\leq y$.

As $r\neq s$ we have $x\neq srx$ and $x,srx\prec rx$. We thus obtain

$sx\prec x,srx\prec rx\text{ and }x,srx\leq y,$

and conclude with Proposition 3.7. ∎

###### Proof of Corollary 3.5.

If $x=y$ we have ${\mathcal{C}^{+}(x,y)}=\\{0\\}$ and the statement is
trivial, hence let $x<y$. We first prove for any
$\beta\in{\mathcal{E}^{+}(x,y)}$, that

($\ast$) $s(\beta)\in{\mathcal{C}^{+}(sx,s_{\beta}x)}.$

We have $\ell(s_{\beta}x)=\ell(sx)+2$, hence

$\ell(s_{s(\beta)}sx)=\ell(ss_{\beta}x)=\ell(s_{\beta}x)\pm 1=\ell(sx)+2\pm
1>\ell(sx),$

and therefore by Lemma 3.2(d), $s(\beta)\in{\mathcal{C}^{+}(sx,ss_{\beta}x)}$.
If $ss_{\beta}x\prec s_{\beta}x$ then

$s(\beta)\in{\mathcal{E}^{+}(sx,ss_{\beta}x)}\subseteq{\mathcal{E}^{+}(sx,s_{\beta}x)}\subseteq{\mathcal{C}^{+}(sx,s_{\beta}x)}.$

If otherwise $s_{\beta}x\prec ss_{\beta}x$ we apply Theorem 3.4 to obtain

${\mathcal{C}^{+}(sx,ss_{\beta}x)}\subseteq{\mathcal{C}^{+}(sx,s_{\beta}x)}+\mathbb{R}_{+}(\alpha_{s}).$

But as $sx\prec x\prec s_{\beta}x$ we have
${\mathcal{C}^{+}(sx,s_{\beta}x)}+\mathbb{R}_{+}(\alpha_{s})={\mathcal{C}^{+}(sx,s_{\beta}x)}$
and thus $s(\beta)\in{\mathcal{C}^{+}(sx,s_{\beta}x)}$. This concludes the
proof of ($\ast$ ‣ 3.1).

If $\tau=y$ we clearly have
${\mathcal{C}^{+}(sx,s_{\beta}x)}\subseteq{\mathcal{C}^{+}(sx,y)}$ for every
$\beta\in{\mathcal{E}^{+}(x,y)}$, hence by ($\ast$ ‣ 3.1) we get

$s({\mathcal{C}^{+}(x,y)})\subseteq{\mathcal{C}^{+}(sx,\tau)}.$

If $\tau=sy$ we consider the following cases.

Case 1: If $x\not\leq sy$ we apply Corollary 2.3 to $sx\prec x$ and $sy\prec
y$ and obtain $[sx,sy]\cong[x,y]$, hence
$s({\mathcal{C}^{+}(x,y)})={\mathcal{C}^{+}(sx,\tau)}$.

Case 2: If $x\leq sy$ but $s_{\beta}x\not\leq sy$ take a reduced word for $y$
that starts with ${\rm s}$, say ${\rm s}\leavevmode\nobreak\ {\rm
s}_{1}\dots\rm s_{m},$ so that ${\rm s}_{1}\dots\rm s_{m}$ is a reduced word
for $sy=\tau$. A reduced word for $s_{\beta}x$ can be obtained by deleting
letters different from the initial letter ${\rm s}$. Therefore $s$ is a
descent of $s_{\beta}x$ and furthermore $ss_{\beta}x\leq\tau$. Thus
$s(\beta)\in{\mathcal{C}^{+}(sx,ss_{\beta}x)}\subseteq{\mathcal{C}^{+}(sx,\tau)}$.

Case 3: If $s_{\beta}x\leq sy$ we apply ($\ast$ ‣ 3.1) to obtain ${\rm
s}(\beta)\in{\mathcal{C}^{+}(sx,s_{\beta}x)}\subseteq{\mathcal{C}^{+}(sx,\tau)}$
for every $\beta\in{\mathcal{E}^{+}(x,y)}$. ∎

###### Proof of Corollary 3.6.

We first show the identity

($\ast$)
${\mathcal{C}^{+}(x^{-1},y^{-1})}=x^{-1}\big{(}{\mathcal{C}^{+}(x,y)}\big{)}.$

If $x=y$ the statement is trivial, hence let $x<y$ and take
$\beta\in{\mathcal{E}^{+}(x,y)}$. We then have $x\prec s_{\beta}x\leq y$ or,
equivalently,

$x^{-1}\prec x^{-1}s_{\beta}=s_{x^{-1}(\beta)}x^{-1}\leq y^{-1}.$

This implies $x^{-1}(\beta)\in{\mathcal{E}^{+}(x^{-1},y^{-1})}$ and we obtain
($\ast$ ‣ 3.1).

Again the main statement is trivial for $x=y$, hence let $x<y$ and take
$\beta\in{\mathcal{E}^{+}(x,y)}$. We then have similar as above

$sx^{-1}\prec x^{-1}\prec s_{x^{-1}(\beta)}x^{-1}\leq y^{-1}.$

By Corollary 3.5 we get

$sx^{-1}(\beta)\in{\mathcal{C}^{+}(sx^{-1},\tau^{-1})}.$

Applying ($\ast$ ‣ 3.1) we finally conclude with

$xssx^{-1}(\beta)=\beta\in{\mathcal{C}^{+}(xs,\tau)}.\qed$

###  3.2. Bruhat cones and non-flipable vertices in subword complexes

For a non-empty subword complex $\mathcal{SC}({\rm Q},w)$, we connect in this
section the cone ${\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$ to the
non-flippable vertices in facets of $\mathcal{SC}({\rm Q},w)$. We then use
this description to show in Proposition 3.14 the first containment for Theorem
3.1,

${\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}\ \subseteq\
\bigcap_{F}\operatorname{cone}{{\sf R}}(F),$

by showing that all cover labels of atoms in the Bruhat interval
$[w,{\operatorname{Dem}}({\rm Q})]$ are contained in all cones over root
configurations.

######  Proposition 3.9.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex. Then

${\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}=\left\\{{{\sf
r}}(I,i)\;\big{|}\;I\text{ facet of }\mathcal{SC}({\rm Q},w)\text{ and }i\in
I\text{ not flippable }\right\\}.$

Moreover, if $i\in I$ is a flippable index in a facet $I$ of
$\mathcal{SC}({\rm Q},w)$ then ${{\sf
r}}(I,i)\notin{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$.

First observe that

$\displaystyle{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}\neq\emptyset$
$\displaystyle\Longleftrightarrow w<{\operatorname{Dem}}({\rm Q})$
$\displaystyle\Longleftrightarrow\mathcal{SC}({\rm Q},w)\text{ is a ball }$
$\displaystyle\Longleftrightarrow\mathcal{SC}({\rm Q},w)\text{ has facets
containing non-flippable vertices }.$

So the interesting case is if these conditions are satisfied: For a given
$\beta\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$, i.e., $w\prec
s_{\beta}w\leq{\operatorname{Dem}}({\rm Q})$, consider the map

(3.1) $\iota:\mathcal{SC}({\rm Q},s_{\beta}w)\rightarrow\mathcal{SC}({\rm
Q},w)$

from facets of $\mathcal{SC}({\rm Q},s_{\beta}w)$ to facets of
$\mathcal{SC}({\rm Q},w)$ given by $J\mapsto J\cup\\{k\\}$ where $k$ is the
unique index in the complement of $J$ such that ${\rm
Q}_{\\{1,\dots,m\\}\setminus(J\cup\\{k\\})}$ is a reduced word for $w$. This
unique index is well-defined by Lemma 2.1 saying that for any reduced word
${\rm s}_{1}\dots\rm s_{\ell}$ for $s_{\beta}w$ there is a unique index $k$
such that ${\rm s}_{1}\dots\widehat{\rm s}_{k}\dots\rm s_{\ell}$ is a word of
$w$ and this word is reduced because $w\prec s_{\beta}w$ implies
$\ell(w)=\ell(s_{\beta}w)-1$.

This discussion shows that every facet of $\mathcal{SC}({\rm Q},s_{\beta}w)$
is also a face of $\mathcal{SC}({\rm Q},w)$, and this face is of codimension
$2$. It is in particular not surprising that the map $\iota$ is not injective
in general as seen in the following example.

######  Example 3.10 (Type $A_{1}\times A_{1}$).

We write this example in type $B_{3}$ to use the above example scheme. Let
${\rm Q}=131$ and $w=13=31$. The complex $\mathcal{SC}({\rm Q},w)$ then
contains the two facets

$I_{\operatorname{g}}=\\{1\\}\text{ and }I_{\operatorname{ag}}=\\{3\\}.$

If we consider the lower cover $s_{3}\prec w$ we obtain

$\iota(I_{\operatorname{g}})=\\{1,3\\}=\iota(I_{\operatorname{ag}}).$

######  Lemma 3.11.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex, let
$I\in\mathcal{SC}({\rm Q},w)$ be a facet and let $i\in I$ non-flippable. Then
$I\setminus\\{i\\}$ is a facet of $\mathcal{SC}({\rm Q},s_{\beta}w)$ for
$\beta={{\sf r}}(I,i)$. In particular, the complement of $I\setminus\\{i\\}$
is a reduced word and $\beta\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}$.

###### Proof.

For ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$ the complement of the facet ${\rm
Q}_{\\{1,\dots,m\\}\setminus I}$ is a reduced word for $w$. We split this word
into its prefix ${\rm w}_{1}={\rm Q}_{\\{1,\dots,i\\}\setminus I}$ and its
suffix ${\rm w}_{2}={\rm Q}_{\\{i+1,\dots,m\\}\setminus I}$. We then have for
the corresponding elements

$w=w_{1}\cdot w_{2}.$

Now $i\in I$ is not flippable, hence by Lemma 2.7(b) we have
$\beta=w_{1}(\alpha_{s_{i}})\in\Phi^{+}$ and therefore $w_{1}\prec w_{1}\cdot
s_{i}$. For ${\rm Q}_{rev}={\rm s}_{m}\dots\rm s_{1}$, we have the obvious
isomorphism $\mathcal{SC}({\rm Q},w)\cong\mathcal{SC}({\rm Q}_{rev},w^{-1})$
given by $i\mapsto m+1-i$. The position $m+1-i$ is thus not flippable in
$\mathcal{SC}({\rm Q}_{rev},w^{-1})$ and we obtain by the same argument that
$w_{2}\prec s_{i}\cdot w_{2}$. Applying now Lemma 2.6 we obtain

$w=w_{1}\cdot w_{2}\prec w_{1}\cdot s_{i}\cdot w_{2}=s_{\beta}w.$

Hence $\ell(s_{\beta}w)=\ell(w)+1$ and we conclude the statement. ∎

######  Lemma 3.12.

Let $w\prec s_{\beta}w\leq{\operatorname{Dem}}({\rm Q})$. Then:

  1. (a)

There is a facet $I\in\mathcal{SC}({\rm Q},w)$ and an index $i\in I$ with
${{\sf r}}(I,i)=\beta$.

  2. (b)

A facet $I\in\mathcal{SC}({\rm Q},w)$ is in the image of $\iota$ if and only
if $\beta\in{{\sf R}}(I)$.

###### Proof.

For (a), take any facet $I\in\mathcal{SC}({\rm Q},s_{\beta}w)$ and let $i_{k}$
be defined as above with $\iota(I)=I\cup\\{i_{k}\\}$. We then obtain the
subword ${\rm s}_{i_{1}}\dots\rm s_{i_{\ell}}={\rm
Q}_{\\{1,\dots,m\\}\setminus I}$ of ${\rm Q}$ with

$s_{\beta}w=s_{i_{1}}\dots s_{i_{k}}\dots s_{i_{\ell}},\quad
w=s_{i_{1}}\dots\widehat{s}_{i_{k}}\dots s_{i_{\ell}}$

being reduced expressions for $s_{\beta}w$ and for $w$, respectively. This
shows that

$\beta=s_{i_{1}}\dots s_{i_{k-1}}(\alpha_{s_{i_{k}}})={{\sf
r}}(I\cup\\{i_{k}\\},i_{k}).$

Clearly $i_{k}$ is not flippable in the facet $I\cup\\{i_{k}\\}$ of
$\mathcal{SC}({\rm Q},w)$, as otherwise the given reduced expression of
$s_{\beta}w$ would contain two different reduced expressions for $w$, and this
is not the case by the uniqueness property in Lemma 2.1.

For (b), we have already seen in the proof of (a) that $\beta={{\sf
r}}(I\cup\\{i_{k}\\},i_{k})$ if $I\cup\\{i_{k}\\}=\iota(I)$ is in the image of
$\iota$. Conversely, let $I$ be a facet of $\mathcal{SC}({\rm Q},w)$ such that
$\beta={{\sf r}}(I,i_{k})$ for some $i_{k}\in I$. As $w\prec s_{\beta}w$
especially $\beta\not\in\operatorname{Inv}(w)$, hence $i_{k}$ is not flippable
in $I$. Therefore by Lemma 3.11 we have $I\setminus\\{i_{k}\\}$ is a facet in
$\mathcal{SC}({\rm Q},s_{\beta}w)$ and furthermore
$I=\iota(I\setminus\\{i_{k}\\})$ is in the image of $\iota$, which concludes
the proof. ∎

###### Proof of Proposition 3.9.

If $\beta\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$ by Lemma
3.12(a) there is a facet $I\in\mathcal{SC}({\rm Q},w)$ and a non-flippable
index $i\in I$ with ${{\sf r}}(I,i)=\beta$ and thus

${\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}\subseteq\left\\{{{\sf
r}}(I,i)\;\big{|}\;I\text{ facet of }\mathcal{SC}({\rm Q},w)\text{ and }i\in
I\text{ not flippable }\right\\}$

The other inclusion follows immediately with Lemma 3.11. ∎

######  Example 3.13 (Type $B_{3}$).

Take ${\rm Q}=123123123$ to be a reduced word for the longest element
${w_{\circ}}$. For the simple generator $s_{1}$ we have

${\mathcal{E}^{+}(s_{1},{w_{\circ}})}=\\{{{010}_{\Delta}},\leavevmode\nobreak\
{{001}_{\Delta}},\leavevmode\nobreak\ {{110}_{\Delta}}\\}$

corresponding to covers
$s_{{{010}_{\Delta}}}s_{1}=s_{2}s_{1},\leavevmode\nobreak\
s_{{{001}_{\Delta}}}s_{1}=s_{3}s_{1}$ and
$s_{{{110}_{\Delta}}}s_{1}=s_{1}s_{2}$. The facets of $\mathcal{SC}({\rm
Q},s_{1})$ and their root configurations are

$\displaystyle{{\sf
R}}(\\{{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}},2,3,{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}},5,6,8,9\\})$
$\displaystyle=\left\\{\\!\\!\left\\{{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{100}_{\Delta}}}},\leavevmode\nobreak\
{{010}_{\Delta}},\leavevmode\nobreak\ {{001}_{\Delta}},\leavevmode\nobreak\
{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{100}_{\Delta}}}},\leavevmode\nobreak\
{{010}_{\Delta}},\leavevmode\nobreak\ {{001}_{\Delta}},\leavevmode\nobreak\
{{110}_{\Delta}},\leavevmode\nobreak\
{{001}_{\Delta}}\right\\}\\!\\!\right\\}$ $\displaystyle{{\sf
R}}(\\{{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}},2,3,5,6,{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}},8,9\\})$
$\displaystyle=\left\\{\\!\\!\left\\{{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{100}_{\Delta}}}},\leavevmode\nobreak\
{{010}_{\Delta}},\leavevmode\nobreak\ {{001}_{\Delta}},\leavevmode\nobreak\
{{110}_{\Delta}},\leavevmode\nobreak\ {{001}_{\Delta}},\leavevmode\nobreak\
{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{{\overline{1}}00}_{\Delta}}}},\leavevmode\nobreak\
{{110}_{\Delta}},\leavevmode\nobreak\
{{001}_{\Delta}}\right\\}\\!\\!\right\\}$ $\displaystyle{{\sf
R}}(\\{2,3,{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}},5,6,{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}},8,9\\})$
$\displaystyle=\left\\{\\!\\!\left\\{{{110}_{\Delta}},\leavevmode\nobreak\
{{001}_{\Delta}},\leavevmode\nobreak\
{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{{\overline{1}}00}_{\Delta}}}},\leavevmode\nobreak\
{{110}_{\Delta}},\leavevmode\nobreak\ {{001}_{\Delta}},\leavevmode\nobreak\
{\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{{{\overline{1}}00}_{\Delta}}}},\leavevmode\nobreak\
{{110}_{\Delta}},\leavevmode\nobreak\
{{001}_{\Delta}}\right\\}\\!\\!\right\\}$

with flippable positions in bold red.

For the values of the root function on non-flippable vertices this translates
to the following result on root configurations.

######  Proposition 3.14.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex. Then

${\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}\subseteq\operatorname{cone}({{\sf R}}(F))$

for every facet $F\in\mathcal{SC}({\rm Q},w)$.

###### Proof.

We prove this statement by induction on the length of ${\rm Q}={\rm
s}_{1}\dots\rm s_{m}$. The statement is trivially true for $m=1$, so we may
assume $m\geq 2$. Let ${\rm Q}^{\prime}={\rm s}_{2}\dots\rm s_{m}$ be obtained
from ${\rm Q}$ by deleting the initial letter ${\rm s}_{1}$. Set moreover
$\sigma={\operatorname{Dem}}({\rm Q})$ and $\tau={\operatorname{Dem}}({\rm
Q}^{\prime})$. One has the decomposition

$\mathcal{SC}({\rm Q},w)=\big{(}\\{1\\}\star\mathcal{SC}({\rm
Q}^{\prime},w)\big{)}\sqcup\mathcal{SC}({\rm Q}^{\prime},s_{1}w),$

where $\mathcal{SC}({\rm Q}^{\prime},{\rm s}_{1}w)$ is only taken into account
if $s_{1}w\prec w$, compare the proof of [KM04, Theorem 2.5]. For a facet
$\mathcal{SC}({\rm Q},w)$, one either has $1\in I$ and then
$I_{1}=I\setminus\\{1\\}\in\mathcal{SC}({\rm Q}^{\prime},w)$ is a facet with
${{\sf R}}(I)={{\sf R}}(I_{1})\cup\\{\alpha_{s_{1}}\\}$, or $1\notin I$ and
then $I_{2}=I\in\mathcal{SC}({\rm Q}^{\prime},s_{1}w)$ is a facet with ${{\sf
R}}(I)=s_{1}({{\sf R}}(I_{2}))$. We aim to show that
${\mathcal{E}^{+}(w,\sigma)}\subseteq\operatorname{cone}({{\sf R}}(I))$.

Case 1: $1\in I$: We may assume by induction that

${\mathcal{E}^{+}(w,\tau)}\subseteq\operatorname{cone}({{\sf R}}(I_{1})).$

If $\tau=\sigma$, we obtain

${\mathcal{E}^{+}(w,\sigma)}={\mathcal{E}^{+}(w,\tau)}\subseteq\operatorname{cone}({{\sf
R}}(I_{1}))\subseteq\operatorname{cone}({{\sf R}}(I)).$

If $\tau\prec\sigma=s_{1}\tau$, we apply Theorem 3.4 to the situation
$w\leq\tau\prec\sigma=s_{1}\tau$ and obtain

${\mathcal{E}^{+}(w,\sigma)}\subseteq{\mathcal{C}^{+}(w,\tau)}+\mathbb{R}_{+}(\alpha_{s_{1}})\subseteq\operatorname{cone}({{\sf
R}}(I_{1}))+\mathbb{R}_{+}(\alpha_{s_{1}})=\operatorname{cone}({{\sf
R}}(I_{1})\cup\\{\alpha_{s_{1}}\\})=\operatorname{cone}({{\sf R}}(I)).$

Case 2: $1\notin I$: We may assume by induction that

${\mathcal{E}^{+}(s_{1}w,\tau)}\subseteq\operatorname{cone}({{\sf
R}}(I_{2})),\text{ hence
}{\mathcal{C}^{+}(s_{1}w,\tau)}\subseteq\operatorname{cone}({{\sf
R}}(I_{2})).$

Since $1\notin I$, there is a reduced word for $w$ that starts with ${\rm
s}_{1}$ and hence $s_{1}w\prec w\leq\sigma$. By Corollary 3.5 we obtain

$s_{1}\big{(}{\mathcal{C}^{+}(w,\sigma)}\big{)}\subseteq{\mathcal{C}^{+}(s_{1}w,\tau)},$

and thus

${\mathcal{E}^{+}(w,\sigma)}\subseteq{\mathcal{C}^{+}(w,\sigma)}\subseteq
s_{1}\big{(}{\mathcal{C}^{+}(s_{1}w,\tau)}\big{)}\subseteq
s_{1}\operatorname{cone}({{\sf R}}(I_{2}))=\operatorname{cone}(s_{1}{{\sf
R}}(I_{2}))=\operatorname{cone}({{\sf R}}(I)).\qed$

The following describes a non-trivial example for the situation in Proposition
3.14. In particular, it shows that it is not enough to take the root
configuration itself in the conclusion of the proposition.

######  Example 3.15 (Type $A_{2}$).

Take ${\rm Q}=1212$ with ${\operatorname{Dem}}({\rm Q})=121=212$ and let
$w=12$. We then have ${\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}=\\{{{01}_{\Delta}}\\},$ the facets of $\mathcal{SC}({\rm Q},w)$ and
their root configurations are given by

${{\sf
R}}(\\{1,2\\})=\left\\{\\!\\!\left\\{{{10}_{\Delta}},\leavevmode\nobreak\
{{01}_{\Delta}}\right\\}\\!\\!\right\\},\quad{{\sf
R}}(\\{2,3\\})=\left\\{\\!\\!\left\\{{{11}_{\Delta}},\leavevmode\nobreak\
{{{\overline{1}}0}_{\Delta}}\right\\}\\!\\!\right\\},\quad{{\sf
R}}(\\{3,4\\})=\left\\{\\!\\!\left\\{{{01}_{\Delta}},\leavevmode\nobreak\
{{{\overline{11}}}_{\Delta}}\right\\}\\!\\!\right\\}.$

While ${{01}_{\Delta}}\notin{{\sf R}}(\\{2,3\\})$ is not in the root
configuration, we see
${{01}_{\Delta}}={{11}_{\Delta}}+{{{\overline{1}}0}_{\Delta}}\in\operatorname{cone}{{\sf
R}}(\\{2,3\\})$ is in its cone, as proposed.

###  3.3. Constructing antigreedy facets inside certain half-spaces

We call a linear functional $f:V\rightarrow\mathbb{R}$ _non-negative_ for the
Bruhat interval $[x,y]$ if $f(\beta)\geq 0$ for all
$\beta\in{\mathcal{E}^{+}(x,y)}$. In this section, we provide an algorithm to
construct an antigreedy facet $I_{f}$ of $\mathcal{SC}({\rm Q},w)$ relative to
a given linear functional $f:V\longrightarrow\mathbb{R}$ that is non-negative
for the Bruhat interval $[w,{\operatorname{Dem}}({\rm Q})]$. We show in
Theorem 3.17 that the facet $I_{f}$ is well-defined and that the linear
functional $f$ is non-negative on its root configuration, $f(\beta)\geq 0$ for
all $\beta\in{{\sf R}}(I_{f})$. For any vector
$v\notin{\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$, one may thus
choose a linear functional that is non-negative for
$[w,{\operatorname{Dem}}({\rm Q})]$ while $f(v)<0$. We then obtain
$v\notin\operatorname{cone}({{\sf R}}(I))$. This implies the remaining
inclusion

${\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}\ \supseteq\
\bigcap_{I}\operatorname{cone}{{\sf R}}(I),$

and thus concludes the proof of Theorem 3.1.

######  Algorithm 3.16.

Computing the $f$-antigreedy facet $I_{f}$ of the subword complex
$\mathcal{SC}({\rm Q},w)$

Input : ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$

$w\leq{\operatorname{Dem}}({\rm Q})$

$f:V\rightarrow\mathbb{R}$ with $f(\beta)\geq 0$ for
$\beta\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$

Conditions : Conditions (1)–(6) are given by the following decision tree:

$\operatorname{sgn}(f(\beta_{k}))$

$(4)$$\beta_{k}\in\Phi^{+}$$\beta_{k}\in\Phi^{+}$

$w_{k-1}s_{k}\leq_{\mathsf{R}}w$$(2)$$w_{k-1}s_{k}\leq_{\mathsf{R}}w$

$(5)$$w_{k-1}^{-1}w\leq{\operatorname{Dem}}({\rm s}_{k+1}\dots\rm s_{m})$

$(1)$$(3)$$(6)$

$-$$0$$+$

$T$$F$$F$$T$

$T$$F$$F$$T$

$T$$F$

The sign can be positive ($+$), negative ($-$), or zero ($0$).

The statements can be true ($T$) or false ($F$).

Output : $I_{f}\subset\\{1,\dots,m\\}$

$w_{0}\leftarrow{e}\in W$

$I_{0}\hskip 3.0pt\leftarrow\\{\\}$

for  _$k=1,\dots,m$_ do

$\beta_{k}\leftarrow w_{k-1}(\alpha_{s_{k}})$

if  _Condition (1) or (2) or (3)_ then

$I_{k}\hskip 3.0pt\leftarrow I_{k-1}\cup\\{k\\}$

$w_{k}\leftarrow w_{k-1}$

else if  _Condition (4) or (5) or (6)_ then

$I_{k}\hskip 3.0pt\leftarrow I_{k-1}$

$w_{k}\leftarrow w_{k-1}\cdot s_{k}$

$I_{f}\leftarrow I_{m}$

return $I_{f}$

We aim to prove the following properties of the output set
$I_{f}\subseteq\\{1,\dots,m\\}$ of 3.16.

######  Theorem 3.17.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex and let
$f:V\rightarrow\mathbb{R}$ with $f(\beta)\geq 0$ for
$\beta\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$. The output set
$I_{f}\subseteq\\{1,\dots,m\\}$ of 3.16 has the following properties:

  1. (a)

$I_{f}$ is a facet of the subword complex $\mathcal{SC}({\rm Q},w)$, i.e., the
word ${\rm Q}_{\\{1,\dots,m\\}\setminus I_{f}}$ is a reduced word for $w$.

  2. (b)

For $i\in I_{f}$, we have $f({{\sf r}}(I_{f},i))\geq 0$.

  3. (c)

For $i\in I_{f}$ with $f({{\sf r}}(I_{f},i))=0$ and ${{\sf
r}}(I_{f},i)\not\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$, we
have ${{\sf r}}(I_{f},i)\in\Phi^{-}$.

######  Remark 3.18.

Applying this algorithm for $w\leq{\operatorname{Dem}}({\rm Q})$ and a linear
functional $f:V\rightarrow\mathbb{R}$ which is positive on

  * •

the basis $\Delta$ of $V$, i.e., $f(\alpha_{s})>0$ for all $s\in\mathcal{S}$,
yields the greedy facet $I_{\operatorname{g}}$,

  * •

the basis $w(\Delta)$ of $V$, i.e., $f(w(\alpha_{s}))>0$ for all
$s\in\mathcal{S}$, yields the antigreedy facet $I_{\operatorname{ag}}$,

of $\mathcal{SC}({\rm Q},w)$ as seen in Lemma 2.8.

In the $k$-th step of 3.16 we have to choose whether to extend the output set
$I_{f}$ or to apply the simple reflection $s_{k}$ to the element $w_{k-1}$. In
the former, we aim to ensure that a reduced word for $w$ still can be obtained
after this step. The following lemma formalizes this condition using Bruhat
order.

######  Lemma 3.19.

Let ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$ and $w\leq{\operatorname{Dem}}({\rm
Q})$ be an element in $W$. Furthermore let

$v=\Pi{{\rm Q}}_{\\{1,\dots,i\\}\setminus X}\leq w$

for some subset $X\subseteq\\{1,\dots,i\\}$ such that ${\rm
Q}_{\\{1,\dots,i\\}\setminus X}$ is a reduced word for $v$. Then ${\rm
Q}_{\\{1,\dots,i\\}\setminus X}$ can be extended to a reduced word for $w$ by
a subword of ${\rm Q}_{\\{i+1,\dots,m\\}}$ if and only if

$v^{-1}w\leq{\operatorname{Dem}}({\rm Q}_{\\{i+1,\dots,m\\}}).$

###### Proof.

This is a direct consequence of the definition of the Demazure product in
terms of Bruhat order as given in (2.6). ∎

The crucial step in the proof of Theorem 3.17 is the following property of the
algorithm.

######  Proposition 3.20.

At the end of the $k$-th iteration of the _for loop_ , the word ${\rm
Q}_{\\{1,\dots,k\\}\setminus I_{k}}$ is a reduced word for $w_{k}$ and can be
extended to a reduced word for $w$ by a subword of ${\rm
Q}_{\\{k+1\,\dots,m\\}}$.

###### Proof.

Let ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$. Lemma 3.19 implies that if ${\rm
Q}_{\\{1,\dots,k\\}\setminus I_{k}}$ is a reduced word for $w_{k}$, then it
can be extended to a reduced word for $w$ by a subword of ${\rm
Q}_{\\{k+1,\dots,m\\}}$ if and only if

($\ast$) $w_{k}^{-1}w\leq{\operatorname{Dem}}({\rm Q}_{\\{k+1,\dots,m\\}}).$

We prove in parallel by induction on the loop index $k$ that the word ${\rm
Q}_{\\{1,\dots,k\\}\setminus I_{k}}$ is reduced and that property ($\ast$ ‣
3.3) holds. This is, we show that if these two properties are satisfied for
all indices $t<k$, than these are also satisfied for the index $k$. Since the
two properties are satisfied before the first loop starts (this is, for
$k=0$), the statement then follows.

For step $k\geq 1$ we assume by induction that ${\rm
Q}_{\\{1,\dots,k-1\\}\setminus I_{k-1}}$ is a reduced word for $w_{k-1}$ and
that $(w_{k-1})^{-1}w\leq{\operatorname{Dem}}({\rm Q}_{\\{k,\dots,m\\}})$.

We first show that the word ${\rm Q}_{\\{1,\dots,k-1\\}\setminus I_{k-1}}$ is
reduced. In the case of conditions $(1),(2)$ and $(3)$, we have ${\rm
Q}_{\\{1,\dots,k\\}\setminus I_{k}}={\rm Q}_{\\{1,\dots,k-1\\}\setminus
I_{k-1}}$ is reduced. In the case of conditions $(5)$ and $(6)$, we have
$w_{k-1}(\alpha_{s_{k}})=\beta_{k}\in\Phi^{+}$ hence $w_{k}=w_{k-1}\cdot
s_{k}$ is reduced. It remains to show the case of condition $(4)$, i.e.,
$f(\beta_{k})<0$, where we need to show $\beta_{k}\in\Phi^{+}$.

By contraposition, we may assume $\beta_{k}\in\Phi^{-}$ and have to show that
$f(\beta_{k})\geq 0$. As $w_{k-1}$ is reduced and
$\beta_{k}=w_{k-1}(\alpha_{s_{k}})$ we have
$-\beta_{k}\in\operatorname{Inv}(w_{k-1})$. Therefore there is an index $t<k$
such that

$w_{t-1}(\alpha_{s_{t}})=\beta_{t}=-\beta_{k}$

and at step $t$ we were in either of the cases of conditions $(4),(5)$ or
$(6)$. If we were in the cases of conditions $(4)$ or $(5)$, then
$f(\beta_{t})\leq 0$ and hence $f(\beta_{k})\geq 0$ as desired.

We conclude that proof of reducedness by showing that it was impossible to be
in the case of condition $(6)$ at step $t$. By induction, the reduced word
${\rm Q}_{\\{1,\dots,k-1\\}\setminus I_{k-1}}$ for $w_{k-1}$ can be extended
in ${\rm Q}_{\\{k,\dots,m\\}}$ to a reduced word for $w$. Since
$\beta_{k}\in\Phi^{-}$, this extended reduced word cannot use the letter ${\rm
s}_{k}$. Thus there exists a facet $I\in\mathcal{SC}({\rm Q},w)$ such that

$\\{1,\dots,k\\}\cap I=I_{k-1}\cup\\{k\\}.$

But as
$-\beta_{k}\in\operatorname{Inv}(w_{k-1})\subseteq\operatorname{Inv}(w)$,
Lemma 2.7 implies that the index $k\in I$ is flippable to $t$ in this facet.
In other words, the flip of $k$ in $I$ gives the facet
$(I\setminus\\{k\\})\cup\\{t\\}$. Now this in particular implies that ${\rm
Q}_{\\{t+1,\dots,m\\}}$ contains a reduced word for $w_{t-1}^{-1}w$, hence

$w_{t-1}^{-1}w\leq{\operatorname{Dem}}({\rm Q}_{\\{t+1,\dots,m\\}})$

and we were not in the case of condition $(6)$.

We conclude with showing that also ($\ast$ ‣ 3.3) holds for the index $k$. If
we are in one of the cases of conditions $(4),(5)$ or $(6)$, then ($\ast$ ‣
3.3) holds by (2.6). If we are in the case of condition $(3)$, we have
$w_{k}=w_{k-1}$ and ($\ast$ ‣ 3.3) is part of the condition.

If we are in the case of condition $(2)$, we have
$\beta_{k}=w_{k-1}(\alpha_{s_{k}})\in\Phi^{-}$. But as we have the
decomposition

($\ast\ast$) $\operatorname{Inv}(w)=\operatorname{Inv}(w_{k-1})\sqcup
w_{k-1}\cdot\operatorname{Inv}(w_{k-1}^{-1}w),$

we have $\alpha_{s_{k}}\not\in\operatorname{Inv}(w_{k-1}^{-1}w)$, hence no
reduced word for $w_{k-1}^{-1}w$ starts with ${\rm s}_{k}$. Therefore
$w_{k}^{-1}w=w_{k-1}^{-1}w\leq{\operatorname{Dem}}({\rm
Q}_{\\{k+1,\dots,m\\}})$.

If we are in the case of condition $(1)$, we have
$w_{k-1}s_{k}\not\leq_{\mathsf{R}}w$, hence
$\beta_{k}\not\in\operatorname{Inv}(w)$. Thus again by ($\ast\ast$ ‣ 3.3) we
get $\alpha_{s_{k}}\not\in\operatorname{Inv}(w_{k-1}^{-1}w)$, hence no reduced
word for $w_{k-1}^{-1}w$ starts with ${\rm s}_{k}$ and the same argument
applies. ∎

###### Proof of Theorem 3.17.

Applying Proposition 3.20 for $k=m$, this is at the end of the last iteration
of the _for loop_ , the word ${\rm Q}\setminus I_{m}$ is a reduced word for
$w=w_{m}$. This implies (a).

For (b) it is immediate from the definition that the root configuration of the
facet $I_{f}$ is

${{\sf R}}(I_{f})=\left\\{\\!\\!\left\\{\beta_{k}\;|\;k\in
I_{f}\right\\}\\!\\!\right\\}.$

The algorithm only adds an index $k$ to the facet if and only if one of the
conditions $(1),(2)$ or $(3)$ is fulfilled. Since these conditions all contain
the condition $f(\beta_{k})\geq 0$, we conclude (b).

For (c) we show that if $f(\beta_{k})=0$ and $\beta_{k}\in\Phi^{+}$ for some
$k\in I_{f}$, then $\beta_{k}\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}$. This means that adding $k$ to $I_{f}$ was done in the case of
condition $(1)$. We thus have $w_{k-1}s_{k}\not\leq_{\mathsf{R}}w$. As seen
before this implies $\beta_{k}\not\in\operatorname{Inv}(w)$, which means that
the index $k$ is not flippable in $I_{f}$. We conclude the proof by invoking
Proposition 3.9. ∎

######  Example 3.21 (Type $B_{2}$).

Let ${\rm Q}=21122112$ with ${\operatorname{Dem}}({\rm
Q})=1212=2121={w_{\circ}}$ and let $w=12$. Let furthermore
$f:V\rightarrow\mathbb{R}$ be the linear functional sending ${{10}_{\Delta}}$
to $-2$ and ${{01}_{\Delta}}$ to $1$. We check that this linear functional is
non-negative on

${\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}=\\{{{01}_{\Delta}},{{12}_{\Delta}}\\}.$

The steps in 3.16 are then shown in the following table:

$m=1:\ \beta_{1}={{01}_{\Delta}},\ f(\beta_{1})>0,\ \beta_{1}\in\Phi^{+},\ s_{2}\not\leq_{\mathsf{R}}w$ | $\leadsto(1):\ I_{1}=\\{1\\},$ | $w_{1}=e,$
---|---|---
$m=2:\ \beta_{2}={{10}_{\Delta}},\ f(\beta_{2})<0$ | $\leadsto(4):\ I_{2}=\\{1\\},$ | $w_{2}=s_{1},$
$m=3:\ \beta_{3}={{{\overline{1}}0}_{\Delta}},\ f(\beta_{3})>0,\ \beta_{3}\in\Phi^{-}$ | $\leadsto(2):\ I_{3}=\\{1,3\\},$ | $w_{3}=s_{1},$
$m=4:\ \beta_{4}={{11}_{\Delta}},\ f(\beta_{4})<0$ | $\leadsto(4):\ I_{4}=\\{1,3\\},$ | $w_{4}=s_{1}s_{2},$
$m=5:\ \beta_{5}={{{\overline{11}}}_{\Delta}},\ f(\beta_{5})>0,\ \beta_{5}\in\Phi^{-}$ | $\leadsto(2):\ I_{5}=\\{1,3,5\\},$ | $w_{5}=s_{1}s_{2},$
$m=6:\ \beta_{6}={{12}_{\Delta}},\ f(\beta_{6})=0,\ \beta_{6}\in\Phi^{+},\ s_{1}s_{2}s_{1}\not\leq_{\mathsf{R}}w$ | $\leadsto(1):\ I_{6}=\\{1,3,5,6\\},$ | $w_{6}=s_{1}s_{2},$
$m=7:\ \beta_{7}={{{\overline{11}}}_{\Delta}},\ f(\beta_{7})>0,\ \beta_{7}\in\Phi^{-}$ | $\leadsto(2):\ I_{7}=\\{1,3,5,6,7\\},$ | $w_{7}=s_{1}s_{2},$
$m=8:\ \beta_{8}={{12}_{\Delta}},\ f(\beta_{8})=0,\ \beta_{8}\in\Phi^{+},\ s_{1}s_{2}s_{1}\not\leq_{\mathsf{R}}w$ | $\leadsto(1):\ I_{8}=\\{1,3,5,6,7,8\\},$ |  $w_{8}=s_{1}s_{2}$.

The algorithm finally returns $I_{f}=I_{8}=\\{1,3,5,6,7,8\\}$ with root
configuration

${{\sf R}}(I_{f})=\left\\{\\!\\!\left\\{{{01}_{\Delta}},\leavevmode\nobreak\
{{{\overline{1}}0}_{\Delta}},\leavevmode\nobreak\
{{{\overline{11}}}_{\Delta}},\leavevmode\nobreak\
{{12}_{\Delta}},\leavevmode\nobreak\
{{{\overline{11}}}_{\Delta}},\leavevmode\nobreak\
{{12}_{\Delta}}\right\\}\\!\\!\right\\},$

and Theorem 3.17(b) and (c) are both satisfied, as expected.

We prove in the following section, see Theorem 3.22, that the facet $I_{f}$ is
uniquely determined by the two conditions given in Theorem 3.17(b) and (c).

###  3.4. Uniqueness of $f$-antigreedy facets

We show in this section that the $f$-antigreedy facet $I_{f}$ in 3.16 is
unique in the following sense.

######  Theorem 3.22.

Let $I$ be a facet of the non-empty subword complex $\mathcal{SC}({\rm Q},w)$
and let $f:V\rightarrow\mathbb{R}$ be a linear functional that is non-negative
for the Bruhat interval $[w,{\operatorname{Dem}}({\rm Q})]$. If the facet $I$
satisfies the conclusions in Theorem 3.17(b) and (c), then $I=I_{f}$ is the
facet produced by 3.16.

Before proving this theorem, we also provide one important corollary and
recast the two properties Theorem 3.17(b) and (c) into subword complex terms
as follows. For a facet $I\in\mathcal{SC}({\rm Q},w)$ and $i\in I$ flippable
we call the flip of $i\in I$ _$f$ -preserving_ if $f({{\sf r}}(I,i))=0$, and
denote by

$\mathcal{SC}_{f}({\rm Q},w)=\left\\{I\text{ facet of }\mathcal{SC}({\rm
Q},w)\;\big{|}\;\forall i\in I:f({{\sf r}}(I,i))\geq 0\right\\}$

the set of facets whose root configuration is contained in the closed positive
halfspace defined by $f$. For such a facet $I$ of $\mathcal{SC}_{f}({\rm
Q},w)$ denote moreover by

${\operatorname{Pos}_{f}(I)}=\left\\{i\in I\;|\;f({{\sf r}}(I,i))>0\right\\}$

those positions in $I$ for which the root function is $f$-positive. A facet
$I\in\mathcal{SC}({\rm Q},w)$ then satisfies Theorem 3.17(b) if and only if
$I\in\mathcal{SC}_{f}({\rm Q},w)$ and it satisfies Theorem 3.17(c) if and only
if

$\left\\{{{\sf r}}(I,i)\;|\;i\in
I\setminus{\operatorname{Pos}_{f}(I)}\right\\}\subseteq\Phi^{-}\cup{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}.$

######  Proposition 3.23.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex and let
$f:V\rightarrow\mathbb{R}$ be a linear functional. Then

$\mathcal{SC}_{f}({\rm Q},w)\text{ is non-empty }\Leftrightarrow f\text{ is
non-negative on }[w,{\operatorname{Dem}}({\rm Q})].$

###### Proof.

If $f$ is non-negative on $[w,{\operatorname{Dem}}({\rm Q})]$ then the facet
$I_{f}$ generated by 3.16 is in $\mathcal{SC}_{f}({\rm Q},w)$ by Theorem 3.17.
Otherwise if $f$ is not non-negative, Proposition 3.14 ensures that every
facet $I\in\mathcal{SC}({\rm Q},w)$ contains at least one position $i\in I$
for that $f({{\sf r}}(I,i))<0$ and thus $\mathcal{SC}_{f}({\rm Q},w)$ is
empty. ∎

The following crucial corollary of Theorem 3.22 generalizes [PS15, Conjecture
7.1].

######  Corollary 3.24.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex and let
$f:V\rightarrow\mathbb{R}$ be a linear functional which is non-negative on
$[w,{\operatorname{Dem}}({\rm Q})]$. Then $\mathcal{SC}_{f}({\rm Q},w)$ forms
a connected component of the graph of $f$-preserving flips in
$\mathcal{SC}({\rm Q},w)$ and moreover,

$\mathcal{SC}_{f}({\rm Q},w)\cong\mathcal{SC}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I)}},w)$

for any facet $I\in\mathcal{SC}_{f}({\rm Q},w)$.

In the remainder of this section, we prove Theorem 3.22 and Corollary 3.24,
and start with collecting several technical lemmas.

######  Lemma 3.25.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex with ${\rm
Q}={\rm s}\ {\rm s}_{2}\dots\rm s_{m}$. The following are equivalent:

  * •

There exist facets $I,J\in\mathcal{SC}({\rm Q},w)$ with $1\in I$ and $1\not\in
J$.

  * •

There exists a facet $K\in\mathcal{SC}({\rm Q}_{\\{2,\dots,m\\}},sw)$ with
$\alpha_{s}\in{{\sf R}}(K)$, and $sw\prec w$.

###### Proof.

Let ${\rm Q}^{\prime}={\rm s}_{2}\dots\rm s_{m}$, and observe that there
exists a facet $I$ with $1\in I$ if and only if $\mathcal{SC}({\rm
Q}^{\prime},w)$ is not empty, and there exists a facet $J$ with $1\notin J$ if
and only if $sw\prec w$.

Assuming first that these two properties hold, the existence of a facet $K$ of
$\mathcal{SC}({\rm Q}^{\prime},sw)$ with $\alpha_{s}\in{{\sf R}}(K)$ is
ensured by Proposition 3.9 as $\alpha_{s}\in\operatorname{Inv}(w)$.

Let now be $K\in\mathcal{SC}({\rm Q}^{\prime},sw)$ with $\alpha_{s}\in{{\sf
R}}(K)$, and let $sw\prec w$. Again by Proposition 3.9, we obtain that the
word ${\rm Q}^{\prime}$ contains a reduced word for $w=ssw$. Since this is
equivalent to $\mathcal{SC}({\rm Q}^{\prime},w)$ being not empty, it concludes
the proof. ∎

######  Lemma 3.26.

Let ${\rm Q}={\rm s}\ {\rm s}_{2}\dots\rm s_{m}$ and
$w\leq{\operatorname{Dem}}({\rm Q})$. The following are equivalent:

  * •

For every linear functional $f$ with $f(\alpha_{s})>0$, the complex
$\mathcal{SC}_{f\circ s}({\rm Q}_{\\{2,\dots,m\\}},sw)$ is empty.

  * •

For every facet $K\in\mathcal{SC}({\rm Q}_{\\{2,\dots,m\\}},sw)$ we have
$\alpha_{s}\in\operatorname{cone}{{\sf R}}(K)$.

###### Proof.

The first item says that for any functional $f:V\rightarrow\mathbb{R}$ with
$f(\alpha_{s})>0$ and every facet $K\in\mathcal{SC}({\rm
Q}_{\\{2,\dots,m\\}},sw)$, there is a $\beta\in{{\sf R}}(K)$ such that
$(f\circ s)(\beta)<0$. By replacing $f$ with $(f\circ s)$ this says for any
functional $f:V\rightarrow\mathbb{R}$ with $f(\alpha_{s})<0$ and every facet
$K\in\mathcal{SC}({\rm Q}{\\{2,\dots,m\\}},sw)$, there is a $\beta\in{{\sf
R}}(K)$ such that $f(\beta)<0$. Now by duality of cones and functionals, this
says that $\alpha_{s}\in\operatorname{cone}({{\sf R}}(K))$ for every facet
$K\in\mathcal{SC}({\rm Q}_{\\{2,\dots,m\\}},sw)$. ∎

######  Corollary 3.27.

Let ${\rm Q}={\rm s}\ {\rm s}_{2}\dots\rm s_{m}$,
$w\leq{\operatorname{Dem}}({\rm Q})$ and $f:V\rightarrow\mathbb{R}$ be a
linear functional with $f(\alpha_{s})>0$. Let furthermore
$I,J\in\mathcal{SC}({\rm Q},w)$ be two facets with $1\in I$ and $1\not\in J$.
Then

  * •

For every facet $K\in\mathcal{SC}({\rm Q}_{\\{2,\dots,m\\}},sw)$ we have
$\alpha_{s}\in\operatorname{cone}({{\sf R}}(K))$, and

  * •

the complex $\mathcal{SC}_{f\circ s}({\rm Q}_{\\{2,\dots,m\\}},sw)$ is empty.

###### Proof.

First by Lemma 3.25 we have $sw\prec w$. Applying Proposition 3.14 we get
$\alpha_{s}\in\operatorname{cone}({{\sf R}}(K))$ for every facet
$K\in\mathcal{SC}({\rm Q}_{\\{2,\dots,m\\}},sw)$ and by Lemma 3.26 we then get
$\mathcal{SC}_{f\circ s}({\rm Q}_{\\{2,\dots,m\\}},sw)$ is empty. ∎

We remark that in the situations of Lemma 3.26 and Corollary 3.27 we have
$sw\prec w$. Thus the functional $f\circ s$ is not non-negative for the Bruhat
interval $[sw,{\operatorname{Dem}}({\rm Q})]$. Thus, the conclusion

$\mathcal{SC}_{f\circ s}({\rm Q}_{\\{2,\dots,m\\}},sw)=\emptyset$

is in agreement with Corollary 3.24.

###### Proof of Theorem 3.22.

Let $I_{f}$ be the facet of $\mathcal{SC}({\rm Q},w)$ produced by 3.16 and let
$I\neq I_{f}$ be another facet. Let $k$ be the smallest index for which $I$
differs from $I_{f}$, i.e., the smallest index such that either $k\in
I\setminus I_{f}$ or $k\in I_{f}\setminus I$.

If the algorithm was violated at step $k$ in condition $(4)$, the facet $I$
violates Theorem 3.17(b), and if the algorithm was violated in condition
$(5)$, the facet $I$ violates Theorem 3.17(c).

If the algorithm was violated in step $k$ in either of the conditions
$(1),(2)$ and $(6)$, the partially constructed set could not be extended to a
facet of $\mathcal{SC}({\rm Q},w)$ which cannot happen since $I$ is chosen to
be such a facet.

For the remaining case, i.e., that the algorithm was violated at step $k$ in
condition $(3)$, we assume without loss of generality that $k=1$. Hence, we
have $f(\beta_{1})=f(\alpha_{s})>0$, $sw\prec w$ and
$w\leq{\operatorname{Dem}}({\rm Q}_{\\{2,\dots,m\\}})$. By the latter there is
a facet $J\in\mathcal{SC}({\rm Q},w)$ with $1\in J$, but as $sw\prec w$ we
have $\alpha_{s}\in\operatorname{Inv}(w)$, hence $1\in J$ is flippable. Let
$I^{\prime}$ be the adjacent facet, such that
$I^{\prime}\setminus\\{i\\}=J\setminus\\{1\\}$. Then by Corollary 3.27 we have
$\mathcal{SC}_{f\circ s}({\rm Q}_{\\{2,\dots,m\\}},sw)=\emptyset$. Now facets
$K^{\prime}\in\mathcal{SC}({\rm Q}_{\\{2,\dots,m\\}},sw)$ are in one-to-one
correspondence with facets $K^{\prime}=K\in\mathcal{SC}({\rm Q},w)$ with
$1\not\in K$. Furthermore we have ${{\sf R}}(K)=s{{\sf R}}(K^{\prime})$ for
every such facet, hence if we violated 3.16 at step $k$ in condition $(3)$ by
not adding $1$ to $I_{k+1}$, we obtain $I\not\in\mathcal{SC}_{f}({\rm Q},w)$
and conclude the statement. ∎

###### Proof of Corollary 3.24.

Let $I,J\in\mathcal{SC}({\rm Q},w)$ be two adjacent facets with
$I\setminus\\{i\\}=J\setminus\\{j\\}$ and $f({{\sf r}}(I,i))=0=f({{\sf
r}}(J,j))$, i.e., the flip from $I$ to $J$ is $f$-preserving. By Lemma 2.7 we
have for all $k\in[m]$ that ${{\sf r}}(J,k)-{{\sf
r}}(I,k)\in\mathbb{R}\cdot{{\sf r}}(I,i)$ and thus $f({{\sf r}}(I,k))=f({{\sf
r}}(J,k))$. Therefore $\mathcal{SC}_{f}({\rm Q},w)$ is closed under
$f$-preserving flips, and also the set of $f$-positive indices is preserved,
${\operatorname{Pos}_{f}(I)}={\operatorname{Pos}_{f}(J)}$. By performing
$f$-preserving flips we can reach a facet $K\in\mathcal{SC}_{f}({\rm Q},w)$
with ${\operatorname{Pos}_{f}(K)}={\operatorname{Pos}_{f}(I)}$ and
$(K\setminus{\operatorname{Pos}_{f}(K)})\setminus{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}\subseteq\Phi^{-}$. By Theorem 3.22 this facet is unique, hence
$\mathcal{SC}_{f}({\rm Q},w)$ is connected via $f$-preserving flips.

For the second part, recall that we proved in the first part that
${\operatorname{Pos}_{f}(I)}$ is independent of the facet
$I\in\mathcal{SC}_{f}({\rm Q},w)$. By inserting the positions
${\operatorname{Pos}_{f}(I)}$ into ${\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I)}}$, we obtain a natural
isomorphism

$\mathcal{SC}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I)}},w)\cong\left\\{I\in\mathcal{SC}({\rm
Q},w)\;\big{|}\;{\operatorname{Pos}_{f}(I)}\subseteq I\right\\}.$

In particular, $\mathcal{SC}_{f}({\rm Q},w)$ is a subset of the right hand
side. Now let $J\in\mathcal{SC}({\rm Q},w)$ be any facet with
${\operatorname{Pos}_{f}(I)}\subseteq J$. By the above isomorphism, the facets
$J$ and $I$ are connected by a sequence of flips not containing positions in
${\operatorname{Pos}_{f}(I)}$. Thus, the sequence of flips from $I$ to $J$ not
containing positions in ${\operatorname{Pos}_{f}(I)}$ is $f$-preserving and we
obtain $J\in\mathcal{SC}_{f}({\rm Q},w)$. ∎

##  4\. Brick polyhedra for subword complexes

Based on Corollary 3.24, we extend in this section brick polytopes that were
developed in [PS15] for root-independent spherical subword complexes towards
brick polyhedra for general subword complexes.

We first recall some elementary notions for polyhedra in the vector space $V$.
A subset $P\subseteq V$ is called _polyhedron_ if there are finitely many
linear functionals $f_{1},\dots,f_{k}:V\rightarrow\mathbb{R}$ and scalars
$b_{1},\dots,b_{k}\in\mathbb{R}$ such that

$P=\left\\{v\in V\;\big{|}\;f_{i}(v)+b_{i}\geq 0\text{ for all }1\leq i\leq
k\right\\}.$

A bounded polyhedron is furthermore called _polytopal_. A _face_ of a
polyhedron $P$ is a subset $F\subseteq P$ such that there exists a linear
functional $f:V\rightarrow\mathbb{R}$ and a scalar $b\in\mathbb{R}$ with $f+b$
is non-negative on $P$ and such that $F=\left\\{v\in P\;|\;f(v)+b=0\right\\}$.
The linear functional $f$ is called _defining functional_ for the face $F$ and
the pair $(f,b)$ is called _defining hyperplane_. The _local cone_ of a
polyhedron $P$ at a point $q\in P$ is the cone over $P$ seen from the point
$q$,

$\operatorname{cone}^{(q)}(P)=\operatorname{cone}\left\\{p-q\;|\;p\in
P\right\\}.$

Moreover, the _(inner) normal cone_ ${\operatorname{C}^{\diamond}(F)}$ of a
face $F\subseteq P$ is the cone of defining functionals of $F$ and the
_(inner) normal fan_ ${\mathcal{N}(P)}$ is the collection of normal cones of
faces of $P$,

${\mathcal{N}(P)}=\left\\{{\operatorname{C}^{\diamond}(F)}\;\big{|}\;F\text{ a
face of }P\right\\}.$

Finally, the _Minskowski sum_ $P+Q$ of two polyhedra $P$ and $Q$ is given by
pointwise vector addition. Observe that every $d$-dimensional face of $P+Q$ is
given by the Minskowski sum of an $i$-dimensional face of $P$ and a
$j$-dimensional face of $Q$ with $i+j=d$.

We now define the brick polyhedron of a non-empty subword complex
$\mathcal{SC}({\rm Q},w)$ with ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$. Following
[PS15, Definition 4.1], the _weight function_ ${{\sf
w}}(I,\cdot):[m]\rightarrow W(\nabla)\subseteq V$ of a facet $I$ of
$\mathcal{SC}({\rm Q},w)$ is defined by ${{\sf w}}(I,k)=\Pi{{\rm
Q}}_{\\{1,\dots,k-1\\}\setminus I}(\omega_{s_{k}}).$ and the _brick vector_
222In comparision with the original definition of brick polytopes in [PS15],
we introduce a minus sign here. This is done in order to simplify notations in
later statements. of $I$ is then

${{\sf b}({I})}=-\sum\limits_{k=1}^{m}{{\sf w}}(I,k).$

The following definition generalizes the definition of brick polytopes for
spherical subword complexes.

######  Definition 4.1.

The _brick polyhedron_ of a non-empty subword complex $\mathcal{SC}({\rm
Q},w)$ is the Minskowski sum of the convex hull of all brick vectors and the
Bruhat cone ${\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$,

$\mathcal{B}({\rm Q},w)=\operatorname{conv}\left\\{{{\sf
b}({I})}\;\big{|}\;I\text{ facet of }\mathcal{SC}({\rm
Q},w)\right\\}+{\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}.$

This definition immediately implies that every brick vector is contained in
the brick polyhedron and that every vertex of the brick polyhedron is a brick
vector. We moreover record that brick polyhedra indeed generalize the
previously known notion of brick polytopes up to a switch in the sign of brick
vectors.

######  Proposition 4.2.

The brick polyhedron $\mathcal{B}({\rm Q},w)$ of a non-empty subword complex
$\mathcal{SC}({\rm Q},w)$ is polytopal if and only if $\mathcal{SC}({\rm
Q},w)$ is spherical. In this case, the brick polyhedron is the convex hull of
all brick vectors.

###### Proof.

This follows from the observation made in Section 2.4 that the subword complex
$\mathcal{SC}({\rm Q},w)$ is spherical if and only if
${\operatorname{Dem}}({\rm Q})=w$ if and only if
${\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}=\\{0\\}$. ∎

######  Example 4.3 (Type $A_{2}$).

Let ${\rm Q}=11212$ and $w=12$. We then have the facets of $\mathcal{SC}({\rm
Q},w)$ and the brick polyhedron $\mathcal{B}({\rm Q},w)$ given by

${{\sf b}({\\{1,2,3\\}})}=\tfrac{1}{3}({{{\overline{87}}}_{\Delta}})$${{\sf
b}({\\{1,3,4\\}})}=\tfrac{1}{3}({{{\overline{77}}}_{\Delta}})$${{\sf
b}({\\{1,4,5\\}})}=\tfrac{1}{3}({{{\overline{66}}}_{\Delta}})$${{\sf
b}({\\{2,3,4\\}})}=\tfrac{1}{3}({{{\overline{67}}}_{\Delta}})$${{\sf
b}({\\{2,4,5\\}})}=\tfrac{1}{3}({{{\overline{56}}}_{\Delta}})$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

with arrows pointing towards the respective root configurations

$\displaystyle{{\sf R}}(\\{1,2,3\\})=\\{{{10}_{\Delta}},\leavevmode\nobreak\
{{10}_{\Delta}},\leavevmode\nobreak\ {{01}_{\Delta}}\\},\quad{{\sf
R}}(\\{1,3,4\\})=\\{{{10}_{\Delta}},\leavevmode\nobreak\
{{11}_{\Delta}},\leavevmode\nobreak\ {{{\overline{10}}}_{\Delta}}\\},$
$\displaystyle{{\sf R}}(\\{1,4,5\\})=\\{{{10}_{\Delta}},\leavevmode\nobreak\
{{01}_{\Delta}},\leavevmode\nobreak\
{{{\overline{11}}}_{\Delta}}\\},\quad{{\sf
R}}(\\{2,3,4\\})=\\{{{{\overline{10}}}_{\Delta}},\leavevmode\nobreak\
{{11}_{\Delta}},\leavevmode\nobreak\ {{{\overline{10}}}_{\Delta}}\\},$
$\displaystyle{{\sf
R}}(\\{2,4,5\\})=\\{{{{\overline{10}}}_{\Delta}},\leavevmode\nobreak\
{{01}_{\Delta}},\leavevmode\nobreak\ {{{\overline{11}}}_{\Delta}}\\}.$

###  4.1. Local cones of brick polyhedra at brick vectors

The definition of brick polyhedra is justified by the following generalization
of [PS15, Proposition 4.7].

######  Theorem 4.4.

The local cone of the brick polyhedron $\mathcal{B}({\rm Q},w)$ at the brick
vector ${{\sf b}({I})}$ coincides with the cone generated by the root
configuration of the facet $I$ of $\mathcal{SC}({\rm Q},w)$. In symbols,

$\operatorname{cone}^{({{\sf b}({I})})}(\mathcal{B}({\rm
Q},w))=\operatorname{cone}{{\sf R}}(I).$

In particular, the brick vector ${{\sf b}({I})}$ is a vertex of
$\mathcal{B}({\rm Q},w)$ if and only if ${{\sf R}}(I)$ is pointed.

Based on Theorem 3.1, we obtain the following equivalent description of brick
polyhedra.

######  Corollary 4.5.

We have

$\mathcal{B}({\rm Q},w)=\bigcap_{I\text{ facet of }\mathcal{SC}({\rm
Q},w)}\big{(}{{\sf b}({I})}+\operatorname{cone}{{\sf R}}(I)\big{)}.$

A linear functional $f:V\rightarrow\mathbb{R}$ is a defining functional for
the non-empty brick polyhedron $\mathcal{B}({\rm Q},w)$ if and only if it is
non-negative on $[w,{\operatorname{Dem}}({\rm Q})]$. For such a defining
functional $f$ with corresponding defining hyperplane $(f,b)$, denote by
$B_{f}=\left\\{v\in P\;|\;f(v)+b=0\right\\}$ the corresponding face of
$\mathcal{B}({\rm Q},w)$. Recall also the facet $I_{f}$ produced by 3.16 in
Section 3.3 and from Section 3.4 that $\mathcal{SC}_{f}({\rm Q},w)$ is the set
of facets $I$ of $\mathcal{SC}({\rm Q},w)$ with $f({{\sf r}}(I,i))\geq 0$ for
all $i\in I$.

The following statement then generalizes [PS15, Lemma 4.6].

######  Proposition 4.6.

Let $f:V\rightarrow\mathbb{R}$ be a linear functional which is non-negative on
$[w,{\operatorname{Dem}}({\rm Q})]$. For a facet $I\in\mathcal{SC}({\rm
Q},w)$, we have

${{\sf b}({I})}\in B_{f}\Longleftrightarrow I\in\mathcal{SC}_{f}({\rm Q},w).$

For the proof we first recall the following two lemmas from [PS15, Section 4]
that were stated for root-independent spherical subword complexes. These
remain valid in the present context with the same proofs as given.

######  Lemma 4.7.

[PS15, Lemma 4.4] Let ${\rm Q}={\rm s}_{1}\dots\rm s_{m}$ and let $I$ be a
facet of the non-empty subword complex $\mathcal{SC}({\rm Q},w)$.

  1. (a)

If ${\rm s}_{k}={\rm s}_{k+1}$ we have ${{\sf w}}(I,k+1)=\begin{cases}{{\sf
w}}(I,k)&\text{ if }k\in I,\\\ {{\sf w}}(I,k)-{{\sf r}}(I,k)&\text{ if
}k\notin I.\end{cases}$

  2. (b)

If $J$ is an adjacent facet with $I\setminus\\{i\\}=J\setminus\\{j\\}$, then
${{\sf w}}(J,\cdot)$ is obtained from ${{\sf w}}(I,\cdot)$ by:

${{\sf w}}(J,k)=\begin{cases}s_{{{\sf r}}(I,i)}({{\sf w}}(I,k))&\text{ if
}\min(i,j)<k\leq\max(i,j),\\\ {{\sf w}}(I,k)&\text{ otherwise}.\end{cases}$

  3. (c)

For $j\notin I$, we have $\langle{{\sf r}}(I,j),{{\sf w}}(I,k)\rangle$ is non-
negative if $j\geq k$, and non-positive if $j<k$.

The following lemma is a consequence of Lemma 4.7. Due to our sign-switch in
the definition of the brick vector and in comparison to the original statement
we also have a switch of the direction here.

######  Lemma 4.8.

[PS15, Lemma 4.5] If $I$ and $J$ are two facets in $\mathcal{SC}({\rm Q},w)$
with $I\setminus\\{i\\}=J\setminus\\{j\\}$, then the difference of the brick
vectors ${{\sf b}({J})}-{{\sf b}({I})}$ is a positive multiple of ${{\sf
r}}(I,i)$.

###### Proof of Proposition 4.6.

Assume first that ${{\sf b}({I})}\in B_{f}$. For every index $i\in I$ we then
either have ${{\sf r}}(I,i)\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}$ or the index $i$ is flippable. In the former case we have $f({{\sf
r}}(I,i))\geq 0$ as $f$ is non-negative on $[w,{\operatorname{Dem}}({\rm
Q})]$. In the latter case, let $J$ be the adjacent facet with
$I\setminus\\{i\\}=J\setminus\\{j\\}$. Then ${{\sf b}({J})}-{{\sf b}({I})}$ is
a positive multiple of ${{\sf r}}(I,i)$ by Lemma 4.8 and thus $f({{\sf
r}}(I,i))\geq 0$. We thus obtain $I\in\mathcal{SC}_{f}({\rm Q},w)$.

Assume now that $I\in\mathcal{SC}_{f}({\rm Q},w)$. Let $K$ be any facet such
that ${{\sf b}({K})}\in B_{f}$. It follows from the first part of the proof
that $K\in\mathcal{SC}_{f}({\rm Q},w)$, and then from Corollary 3.24 that $K$
and $I$ are connected via $f$-preserving flips. Again by Lemma 4.8, we obtain
$f({{\sf b}({I})})=f({{\sf b}({K})})$ and thus ${{\sf b}({I})}\in B_{f}$. ∎

Before proving Theorem 4.4, we collect the following consequence of
Proposition 4.6.

######  Corollary 4.9.

Any two facets $I$ and $J$ of $\mathcal{SC}({\rm Q},w)$ whose brick vectors
${{\sf b}({I})},{{\sf b}({J})}$ are contained in an edge
$E\subseteq\mathcal{B}({\rm Q},w)$ are connected by a flip.

###### Proof.

Let $f$ be a defining functional for the edge $E=B_{f}$. Proposition 4.6 then
implies that the facets $I,J$ are contained in $\mathcal{SC}_{f}({\rm Q},w)$.
By the isomorphism in Corollary 3.24, this complex corresponds to a Coxeter
system $W^{\prime}$ of rank $1$ where any two facets are connected by a flip.
∎

The following example shows that there are also flips between facets with
pointed root configurations that are not edges of the brick polyhedron.

######  Example 4.10 (Type $A_{2}$).

The spherical subword complex $\mathcal{SC}(211221,121)$ has the eight facets

$\begin{array}[]{cccc}I_{1}=\\{1,2,4\\},&I_{2}=\\{1,2,5\\},&I_{3}=\\{1,3,4\\},&I_{4}=\\{1,3,5\\},\\\
I_{5}=\\{2,4,6\\},&I_{6}=\\{2,5,6\\},&I_{7}=\\{3,4,6\\},&I_{8}=\\{3,5,6\\}.\end{array}$

After a shift by $3(\omega_{1}+\omega_{2})$, we have the polytopal brick
polyhedron $\mathcal{B}({\rm Q},w)$ with flip graph

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$${{\sf
b}({I_{1}})}={{10}_{\Delta}}$${{\sf b}({I_{2}})}={{21}_{\Delta}}$${{\sf
b}({I_{3}})}={{20}_{\Delta}}$${{\sf b}({I_{4}})}={{31}_{\Delta}}$${{\sf
b}({I_{5}})}={{13}_{\Delta}}$${{\sf b}({I_{6}})}={{23}_{\Delta}}$${{\sf
b}({I_{7}})}={{24}_{\Delta}}$${{\sf b}({I_{8}})}={{34}_{\Delta}}$

The facets $I_{3}$ and $I_{7}$ have pointed root configurations and are
connected by a flip which does not correspond to an edge of the brick
polyhedron.

###### Proof of Theorem 4.4.

Fix a facet $I$ of $\mathcal{SC}({\rm Q},w)$. Denote by $C_{B}(I)$ the local
cone of the brick polyhedron at the brick vector ${{\sf b}({I})}$. We first
show ${{\sf R}}(I)\subseteq C_{B}(I)$. Let $i\in I$ and $\beta={{\sf
r}}(I,i)$. If $\beta\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$ we
have

$\beta\in{\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}\subseteq
C_{B}(I).$

Otherwise $i$ is flippable to some facet $J$, i.e., there is a facet $J$ and
an index $j\in J$ such that $I\setminus\\{i\\}=J\setminus\\{j\\}$. We then
have ${{\sf b}({J})}-{{\sf b}({I})}$ is a positive multiple of $\beta$ by
Lemma 4.8. As ${{\sf b}({J})}\in\mathcal{B}({\rm Q},w)$ we conclude
$\beta\subseteq C_{B}(I)$.

The other inclusion $C_{B}(I)\subseteq\operatorname{cone}{{\sf R}}(I)$ is
obvious if $\operatorname{cone}{{\sf R}}(I)=V$. So assume otherwise, let $v\in
V\setminus\operatorname{cone}{{\sf R}}(I)$ and let $f$ be a linear functional
which is negative on $v$ and non-negative on ${{\sf R}}(I)$. It follows from
Theorem 3.1 that $f$ is then also non-negative on
$[w,{\operatorname{Dem}}({\rm Q})]$. By definition, $I\in\mathcal{SC}_{f}({\rm
Q},w)$ and Proposition 4.6 ensures that ${{\sf b}({I})}\in B_{f}$. This yields
that $C_{B}(I)$ is non-negative on $f$ and we conclude that $v\notin
C_{B}(I)$. ∎

######  Remark 4.11.

We have seen in Proposition 4.6 that brick vectors contained in a face $B_{f}$
of the brick polyhedron $\mathcal{B}({\rm Q},w)$ are in one-to-one
correspondence with facets in $\mathcal{SC}_{f}({\rm Q},w)$. We furthermore
have by Corollary 3.24 the identification

$\mathcal{SC}_{f}({\rm Q},w)\cong\mathcal{SC}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I_{f})}},w),$

and Theorem 4.4 ensures that $B_{f}$ and $\mathcal{B}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I_{f})}},w)$ have the same
_local structure_ :

  * •

The direction of flips between brick vectors is preserved,

  * •

Local cones in $\mathcal{B}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I_{f})}},w)$ agree with
those inside the face $B_{f}$ of $\mathcal{B}({\rm Q},w)$,

  * •

The normal fans of $B_{f}$ and of $\mathcal{B}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I_{f})}},w)$ coincide, and

  * •

$B_{f}$ is polytopal if and only if $\mathcal{SC}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I_{f})}},w)$ is spherical.

Nevertheless, one may check that $B_{f}$ and $\mathcal{B}({\rm
Q}_{\\{1,\dots,m\\}\setminus{\operatorname{Pos}_{f}(I_{f})}},w)$ do not
necessarily coincide. Take the edge connecting ${{\sf b}({I_{1}})}$ and ${{\sf
b}({I_{5}})}$ in Example 4.10. The defining functional $f$ is zero on
${{01}_{\Delta}}$ and positive on ${{10}_{\Delta}}$ and ${{11}_{\Delta}}$ and
we obtain

$\mathcal{SC}_{f}({\rm Q},w)=\\{I_{1}=\\{1,2,4\\},\leavevmode\nobreak\
I_{5}=\\{2,4,6\\}\\}\ \text{ and }\
{\operatorname{Pos}_{f}(I_{1})}={\operatorname{Pos}_{f}(I_{5})}=\\{2,4\\}.$

The reduced subword complex then is $\mathcal{SC}_{f}({\rm
Q},w)\cong\mathcal{SC}(2121,121)$ with facets

$J_{1}=\\{1\\}\ \text{ and }\ J_{2}=\\{4\\},$

and brick vectors ${{\sf b}({J_{1}})}={{{\overline{12}}}_{\Delta}}$ and ${{\sf
b}({J_{2}})}={{{\overline{10}}}_{\Delta}}$. We thus see

${{\sf b}({I_{5}})}-{{\sf b}({I_{I}})}={{03}_{\Delta}}\ \text{ and }\ {{\sf
b}({J_{2}})}-{{\sf b}({J_{1}})}={{02}_{\Delta}},$

hence this edge has different lengths in the two brick polytopes.

###  4.2. Normal fans of brick polyhedra from Coxeter fans

Theorem 4.4 makes it possible to generalize further properties developed for
brick polytopes in [PS15] to brick polyhedra for general subword complexes.
Several proofs in this section are similar to those given in [PS15]. Define
the _Coxeter fan_ of $W$ as

${\mathcal{CF}_{W}}=\left\\{w(\operatorname{cone}\nabla^{\prime})\;\big{|}\;w\in
W,\ \nabla^{\prime}\subseteq\nabla\right\\}$

with _fundamental chamber_ $\mathcal{C}=\operatorname{cone}(\nabla)$ being the
cone generated by the fundamental weights. The aim of this section is to
describe how to glue together and delete chambers in the Coxeter fan to obtain
the normal fan of the brick polyhedron . To this end, associate to a Bruhat
interval $[x,y]$ a (lower) order ideal in the weak order by

$\displaystyle{\operatorname{Id}_{\mathsf{R}}(x,y)}$
$\displaystyle=\left\\{w\in W\;\big{|}\;{\mathcal{E}^{+}(x,y)}\subseteq
w(\Phi^{+})\right\\}$ $\displaystyle=\left\\{w\in
W\;\big{|}\;\operatorname{Inv}(w)\cap{\mathcal{E}^{+}(x,y)}=\emptyset\right\\}.$

This is indeed a lower order ideal as for
$w\in{\operatorname{Id}_{\mathsf{R}}(x,y)}$ and $z\leq_{\mathsf{R}}w$ we have
$\operatorname{Inv}(z)\subseteq\operatorname{Inv}(w)$ and thus
$z\in{\operatorname{Id}_{\mathsf{R}}(x,y)}$.

######  Proposition 4.12.

Let $\mathcal{SC}({\rm Q},w)$ be a non-empty subword complex and let $z\in W$.
Then there exists a facet $I$ such that ${{\sf R}}(I)\subseteq z(\Phi^{+})$ if
and only if $z\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm
Q}))}$. In this case, the facet $I$ is uniquely given by the facet $I_{f}$
produced by 3.16 for the linear functional $f$ which is positive on
$z(\Phi^{+})$ and negative on $z(\Phi^{-})$.

###### Proof.

It follows from Theorem 3.1 that for
$z\notin{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$
there does not exist a facet $I$ such that ${{\sf R}}(I)\subseteq
z(\Phi^{+})$. Now let
$z\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$ and
let $f$ be a linear functional as in the statement. Then
${\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}\subseteq z(\Phi^{+})$
ensures that $f$ is positive for the Bruhat interval
$[w,{\operatorname{Dem}}({\rm Q})]$. Theorem 3.22 then gives that the facet
$I_{f}$ is the unique facet with $f$-positive root configuration. In other
words, $I_{f}$ is the unique facet for which ${{\sf R}}(I)\subseteq
z(\Phi^{+})$. ∎

For a non-empty subword complex $\mathcal{SC}({\rm Q},w)$, this proposition
allows to define a map

$\kappa:{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm
Q}))}\rightarrow\mathcal{SC}({\rm Q},w)$

by sending $z\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm
Q}))}$ to the unique facet $I_{f}$ with ${{\sf R}}(I)\subseteq z(\Phi^{+})$
where $f$ and $I_{f}$ are given as in the proposition.

######  Lemma 4.13.

Let $\mathcal{SC}({\rm Q},w)$ be non-empty and
$x,y\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$. If
$\kappa(x)=\kappa(y)$ then

$\kappa(x)=\kappa(w)=\kappa(y)\text{ for all }w\in[x,y]_{\mathsf{R}}.$

###### Proof.

Let $\kappa(x)=I=\kappa(y)$ and consider $w\in[x,y]_{\mathsf{R}}$. Recall that
for any $z\in W$, we have

$z(\Phi^{+})\cap\Phi^{+}=\Phi^{+}\setminus\operatorname{Inv}(z),\quad
z(\Phi^{+})\cap\Phi^{-}=-\operatorname{Inv}(z)\ .$

With $\kappa(x)=I=\kappa(y)$ and
$\operatorname{Inv}(x)\subseteq\operatorname{Inv}(w)\subseteq\operatorname{Inv}(y)$,
we obtain

${{\sf
R}}(I)\cap\Phi^{+}\subseteq\Phi^{+}\setminus\operatorname{Inv}(y)\subseteq\Phi^{+}\setminus\operatorname{Inv}(w),\quad{{\sf
R}}(I)\cap\Phi^{-}\subseteq-\operatorname{Inv}(x)\subseteq-\operatorname{Inv}(w).$

The statement follows. ∎

######  Example 4.14 (Type $A_{2}$).

We continue Example 4.3 with ${\rm Q}=11212$ and $w=12$. We then have
${\mathcal{E}^{+}(12,121)}=\\{{{01}_{\Delta}}\\}$ and
${\operatorname{Id}_{\mathsf{R}}(12,121)}=\\{e,1,12\\}$. The brick polyhedron
with normal fan is

$\kappa(e)={{\sf b}({\\{1,2,3\\}})}$$\kappa(1)={{\sf
b}({\\{2,3,4\\}})}$$\kappa(12)={{\sf
b}({\\{2,4,5\\}})}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$1(\mathcal{C})$$12(\mathcal{C})$$e(\mathcal{C})=\mathcal{C}$$121(\mathcal{C})=212(\mathcal{C})$$21(\mathcal{C})$$2(\mathcal{C})$

In particular we see that

$\displaystyle e(\mathcal{C})\text{ is the inner normal cone of
}\kappa(e)=\\{1,2,3\\},$ $\displaystyle 1(\mathcal{C})\text{ is the inner
normal cone of }\kappa(1)=\\{2,3,4\\},$ $\displaystyle 12(\mathcal{C})\text{
is the inner normal cone of }\kappa(12)=\\{2,4,5\\},$

and the union $2(\mathcal{C})\cup 21(\mathcal{C})\cup 212(\mathcal{C})$ is the
set of linear functionals not non-negative on ${\mathcal{C}^{+}(12,121)}$.

######  Example 4.15 (Type $B_{2}$).

Let $Q=2221$ and $w=2$. Then ${\operatorname{Dem}}({\rm Q})=12$ and
${\mathcal{E}^{+}(2,21)}=\\{{{12}_{\Delta}}\\}$. Furthermore we have that
${\operatorname{Id}_{\mathsf{R}}(2,21)}=\\{e,1,12,2\\}$ is an order ideal that
is not an interval. In $\mathcal{SC}({\rm Q},w)$ we have the three facets with
brick vectors

${{\sf
b}({\\{1,2,4\\}})}=\tfrac{1}{2}({{{\overline{58}}}_{\Delta}}),\quad{{\sf
b}({\\{1,3,4\\}})}=\tfrac{1}{2}({{{\overline{57}}}_{\Delta}}),\quad{{\sf
b}({\\{2,3,4\\}})}=\tfrac{1}{2}({{{\overline{56}}}_{\Delta}}),$

that form an edge. The brick polyhedron is thus

$\mathcal{B}({\rm
Q},w)=\operatorname{conv}\big{\\{}\tfrac{1}{2}({{{\overline{58}}}_{\Delta}}),\
\tfrac{1}{2}({{{\overline{56}}}_{\Delta}})\big{\\}}+\operatorname{cone}\big{\\{}{{12}_{\Delta}}\big{\\}}.$

We furthermore have

$\kappa(e)=\kappa(1)=\kappa(12)=\\{1,2,4\\}\ \text{ and }\
\kappa(2)=\\{2,3,4\\}$

as shown in the weak order of type $B_{2}$:

$e$$1$$2$$12$$21$$121$$212$$1212=2121$$\\{1,2,4\\}$$\\{2,3,4\\}$

######  Proposition 4.16.

The map $\kappa$ maps surjectively onto the facets of $\mathcal{SC}({\rm
Q},w)$ with pointed root configurations.

###### Proof.

Since ${{\sf R}}(\kappa(z))\subseteq z(\Phi^{+})$, the facet $\kappa(z)$ has a
pointed root configuration by construction. For a facet $I$ with pointed root
configuration, let $f$ be any linear functional that is positive on ${{\sf
R}}(I)$ and non-zero on all roots. Then there is a unique element $z\in W$
with $z(\Phi^{+})=\left\\{\beta\in\Phi\;|\;f(\beta)>0\right\\}$ and conclude
that $\kappa(z)=I$. ∎

The main theorem of this section is the following generalization of [PS15,
Proposition 5.4].

######  Theorem 4.17.

Let ${{\sf b}({I})}$ be a vertex of $\mathcal{B}({\rm Q},w)$, i.e.,
$I\in\mathcal{SC}({\rm Q},w)$ is a facet with pointed root configuration. The
(closure of the) normal cone ${\operatorname{C}^{\diamond}({{\sf b}({I})})}$
is the union of the chambers $z(\mathcal{C})$ of ${\mathcal{CF}_{W}}$ given by
the elements $z\in W$ with $\kappa(z)=I$.

We also get the following generalization of [PS15, Corollary 5.5].

######  Corollary 4.18.

The normal fan ${\mathcal{N}(\mathcal{B}({\rm Q},w))}$ is obtained from the
Coxeter fan by glueing together the chambers corresponding to fibers of the
map $\kappa$, and deleting the chambers corresponding to elements in $W$ not
in ${\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$.

The crucial parts of the proof of Theorem 4.17 is extracted into the following
two lemmas. The first generalizes [PS15, Lemma 5.3].

######  Lemma 4.19.

Let $z\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$
and $s\in\mathcal{S}$ such that
$zs\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$. Then
$\kappa(zs)$ is obtained from $\kappa(z)$ as follows:

  * •

If $z(\alpha_{s})\in{{\sf R}}(\kappa(z))$, then $\kappa(zs)$ is obtained from
$\kappa(z)$ by flipping the unique index $i\in I$ such that ${{\sf
r}}(I,i)=z(\alpha_{s})$ and the obtained facet has again a pointed root
configuration.

  * •

If $z(\alpha_{s})\notin{{\sf R}}(\kappa(z))$, then $\kappa(zs)=\kappa(z)$.

###### Proof.

Set $\alpha=\alpha_{s}$ and $I=\kappa(z)$, and observe that the root
$z(\alpha)$ generates a ray of $z(\operatorname{cone}(\Phi^{+}))$. Either
$z(\alpha)\in\Phi^{-}$ or $z(\alpha)\in\operatorname{Inv}(zs)$. Since
$zs\in{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm Q}))}$ we
obtain $z(\alpha)\notin{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$.

Let $z(\alpha)\notin{{\sf R}}(I)$. Then ${{\sf R}}(I)\subseteq z(\Phi^{+})\cap
zs(\Phi^{+})$ and we obtain $\kappa(sz)=I$.

Let $z(\alpha)\in{{\sf R}}(I)$. Since ${{\sf R}}(I)\subseteq z(\Phi^{+})$,
$z(\alpha)$ generates a ray of the (pointed) cone over ${{\sf R}}(I)$.
Therefore, there exists a linear functional $f$ with $f(z(\alpha))=0$ and $f$
positive on $z(\Phi^{+})\setminus\\{z(\alpha)\\}$ (and in particular on ${{\sf
R}}(I)$). Since $z(\alpha)\notin{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}$, the face $B_{f}\subseteq\mathcal{B}({\rm Q},w)$ is a polytopal edge.
Theorem 4.4 and Proposition 4.6 ensure that ${{\sf b}({I})}$ is a vertex of
$B_{f}$. Let $J$ be the facet for which ${{\sf b}({J})}$ is the other vertex
of the edge $B_{f}$. Corollary 4.9 then shows that $I$ and $J$ are connected
by a flip. If $z(\alpha)\in\Phi^{+}$, then $J$ is obtained from $I$ by
flipping the smallest index $i\in I$ for which ${{\sf r}}(I,i)=z(\alpha)$, and
if $z(\alpha)\in\Phi^{-}$, then $J$ is obtained from $I$ by flipping the
largest index $i\in I$ for which ${{\sf r}}(I,i)=z(\alpha)$. ∎

######  Lemma 4.20.

Let ${{\sf b}({I})}$ be a vertex of $\mathcal{B}({\rm Q},w)$. Then

$\operatorname{cone}({{\sf
R}}(I))=\bigcap\limits_{z\in\kappa^{-1}(I)}z(\operatorname{cone}(\Phi^{+})).$

###### Proof.

The definition of the map $\kappa$ immediately implies

$\operatorname{cone}({{\sf
R}}(I))\subseteq\bigcap\limits_{z\in\kappa^{-1}(I)}z(\operatorname{cone}(\Phi^{+})).$

For the other inclusion let $\beta\in\Phi$ be a root that generates a ray of
$\cap_{z\in\kappa^{-1}(I)}z(\operatorname{cone}(\Phi^{+}))$. Then $\beta$ is
also ray of $u(\operatorname{cone}(\Phi^{+}))$ for some particular
$u\in\kappa^{-1}(I)$. Thus $\beta=u(\alpha)$ for some $\alpha\in\Delta$.

If
$us_{\alpha}\notin{\operatorname{Id}_{\mathsf{R}}(w,{\operatorname{Dem}}({\rm
Q}))}$ then

$u(\alpha)\in{\mathcal{E}^{+}(w,{\operatorname{Dem}}({\rm
Q}))}\subseteq\operatorname{cone}({{\sf R}}(I)).$

Otherwise $\kappa(u)\neq\kappa(us_{\alpha})$ and therefore by Lemma 4.19 we
have $u(\alpha)$ is the direction of the flip from $\kappa(u)$ to
$\kappa(us_{\alpha})$, hence $u(\alpha)\in{{\sf R}}(I)$. This concludes the
statement. ∎

We can now proof Theorem 4.17 and Corollary 4.18.

###### Proof of Theorem 4.17.

Let $I\in\mathcal{SC}({\rm Q},w)$ be a facet with pointed root configuration.
We write in the following ${\operatorname{C}^{\diamond}(\mathcal{X})}$ for a
pointed cone $\mathcal{X}$ to denote the normal cone at its apex. Theorem 4.4
yields

${\operatorname{C}^{\diamond}({{\sf
b}({I})})}={\operatorname{C}^{\diamond}(\operatorname{cone}{{\sf R}}(I))}.$

It is well-known that the (closure of the) normal cone of the fundamental
chamber $\mathcal{C}$ is generated by the simple roots
${\operatorname{C}^{\diamond}(\mathcal{C})}=\operatorname{cone}(\Delta)=\operatorname{cone}(\Phi^{+})$.
Lemma 4.20 then gives

${\operatorname{C}^{\diamond}(\operatorname{cone}{{\sf
R}}(I))}={\operatorname{C}^{\diamond}\big{(}\bigcap\limits_{v\in\kappa^{-1}(I)}v({\operatorname{C}^{\diamond}(\mathcal{C})})\big{)}}=\bigcup\limits_{v\in\kappa^{-1}(I)}{\operatorname{C}^{\diamond}\big{(}v({\operatorname{C}^{\diamond}(\mathcal{C})})\big{)}}=\bigcup\limits_{v\in\kappa^{-1}(I)}v(\mathcal{C}),$

where the latter two equalities are elementary transformations. ∎

###### Proof of Corollary 4.18.

It follows from Theorem 4.17 that the maximal cones of
${\mathcal{N}(\mathcal{B}({\rm Q},w))}$ are given as in the corollary. ∎

###  4.3. Containment properties of brick polyhedra for a fixed word

The considerations of brick polyhedra also for non-spherical subword complexes
makes it possible to discuss how the various brick polyhedra for a fixed word
${\rm Q}$ are related. In this section, we use the map
$\iota:\mathcal{SC}({\rm Q},s_{\beta}w)\rightarrow\mathcal{SC}({\rm Q},w)$
from (3.1), to show how brick vectors change between the subword complexes
$\mathcal{SC}({\rm Q},w)$ and $\mathcal{SC}({\rm Q},s_{\beta}w)$ for a cover
$w\prec s_{\beta}w\leq{\operatorname{Dem}}({\rm Q})$ in Bruhat order. Using
Corollary 3.6, we then obtain the following containment statement of brick
polyhedra.

######  Theorem 4.21.

Let $w\in W$ and $s\in\mathcal{S}$ such that $w\prec
ws\leq{\operatorname{Dem}}({\rm Q})$. Then $\mathcal{B}({\rm
Q},ws)\subseteq\mathcal{B}({\rm Q},w)$.

We first show the following result for brick vectors and extract the key
ingredient into a lemma.

######  Proposition 4.22.

Let $w\prec s_{\beta}w\leq{\operatorname{Dem}}({\rm Q})$ and
$I\in\mathcal{SC}({\rm Q},s_{\beta}w)$ be a facet. Then ${{\sf
b}({I})}\in\mathcal{B}({\rm Q},w)$.

######  Lemma 4.23.

In the situation of the proposition, we have ${{\sf b}({I})}\in{{\sf
b}({\iota(I)})}+\mathbb{R}_{+}(\beta)$.

###### Proof.

The facet $\iota(I)$ is the set $I\cup\\{j\\}$ where $j$ is the unique
position in the complement of $I$, such that ${{\sf r}}(I,j)=\beta$ in
$\mathcal{SC}({\rm Q},s_{\beta}w)$. Similar to Lemma 4.7(b), the weight
function ${{\sf w}}(\iota(I),\cdot)$ is obtained from the weight function
${{\sf w}}(I,\cdot)$ by

${{\sf w}}(\iota(I),k)=\begin{cases}{{\sf w}}(I,k)&\text{ if }k\leq j,\\\
s_{\beta}({{\sf w}}(I,k))&\text{ if }k>j.\end{cases}$

Let $k>j$. Since $\beta={{\sf r}}(I,j)$ and $j\notin I$, Lemma 4.7(c) yields
that $\langle\beta,{{\sf w}}(I,k)\rangle$ is non-positive. Therefore,
$s_{\beta}({{\sf w}}(I,k))\in{{\sf w}}(I,k)+\mathbb{R}_{+}(\beta)$, and we
obtain ${{\sf b}({I})}={{\sf b}({\iota(I)})}+\mathbb{R}_{+}(\beta)$. ∎

###### Proof of Proposition 4.22.

The previous lemma shows that ${{\sf b}({I})}\in{{\sf
b}({\iota(I)})}+\mathbb{R}_{+}(\beta)$. Since
$\beta\in{\mathcal{C}^{+}(w,{\operatorname{Dem}}({\rm Q}))}$, the statement
follows. ∎

###### Proof of Theorem 4.21.

This follows from Proposition 4.22 together with the containment of Bruhat
cones described in Corollary 3.6. ∎

The following example shows the nested situation of brick polyhedra for the
permutahedron in type $A_{2}$.

######  Example 4.24 (Type $A_{2}$).

Let ${\rm Q}=112211$. We show all brick polyhedra where brick vectors of
different polyhedra that have the same coordinates are drawn close to each
other. The brick polyhedra $\mathcal{SC}({\rm Q},w)$ are in black for $w=121$,
in red for $w=12$, in blue for $w=21$, in orange for $w=1$, in lightblue for
$w=2$ and in grey for $w=e$.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

## References

  * [BB05] Anders Björner and Francesco Brenti.  Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics.  Springer, New York, 2005.
  * [CFZ02] Frédéric Chapoton, Sergey Fomin, and Andrei Zelevinsky.  Polytopal realizations of generalized associahedra.  Canad. Math. Bull., 45(4):537–566, 2002.
  * [CLS14] Cesar Ceballos, Jean-Philippe Labbé, and Christian Stump.  Subword complexes, cluster complexes, and generalized multi-associahedra.  J. Algebraic Combin., 39(1):17–51, 2014.
  * [Dye94] Matthew J. Dyer.  Bruhat intervals, polyhedral cones and Kazhdan-Lusztig-Stanley polynomials.  Math. Z., 215(2):223–236, 1994.
  * [HLT11] Christoph Hohlweg, Carsten Lange, and Hugh Thomas.  Permutahedra and generalized associahedra.  Adv. in Math., 226:206–240, 2011.
  * [KM04] Allen Knutson and Ezra Miller.  Subword complexes in Coxeter groups.  Adv. Math., 184(1):161–176, 2004.
  * [KM05] Allen Knutson and Ezra Miller.  Gröbner geometry of Schubert polynomials.  Ann. of Math., 161(3):1245–1318, 2005.
  * [PS12] Vincent Pilaud and Francisco Santos.  The brick polytope of a sorting network.  European J. Combin., 33(4):632–662, 2012.
  * [PS13] Vincent Pilaud and Christian Stump.  EL-labelings and canonical spanning trees for subword complexes.  In Discrete geometry and optimization, volume 69 of Fields Inst. Commun., pages 213–248. Springer, New York, 2013.
  * [PS15] Vincent Pilaud and Christian Stump.  Brick polytopes of spherical subword complexes and generalized associahedra.  Adv. Math., 276:1–61, 2015.