%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

%
%
%
%
%

\usepackage[table]{xcolor}
\usepackage{graphicx}
%\usepackage{footmisc}

\usepackage{tikz}
\usetikzlibrary{calc,through,backgrounds,shapes,matrix,decorations.markings,decorations.pathmorphing,arrows.meta}

\usepackage{array}
\newcolumntype{C}[1]{>{\centering\arraybackslash$}p{#1}<{$}}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{hhline}
\newcommand{\onevar}{\mathbf{1}}
\newcommand{\zerovar}{\mathbf{0}}

%\usepackage{hyperref}
%\usepackage{enumitem}
\setenumerate{label=\normalfont{(\alph*)}}%, itemsep=5pt, topsep=5pt}

%\usepackage{url, hypcap}
%\hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue}

\numberwithin{equation}{section}

\usepackage{cleveref}
\Crefname{algocf}{Algorithm}{Algorithms}





\usepackage[boxed,vlined,algosection]{algorithm2e}
\makeatletter
\renewcommand{\@algocf@capt@boxed}{above}% formerly {bottom}
\makeatother

\newtheorem*{Theorem}{Theorem}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}
\newtheorem{algo}[theorem]{Algorithm}
\newtheorem{definition}[theorem]{Definition}

%
%
%
%

%MathOperator
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\pos}{pos}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\relint}{relint}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\verts}{vert}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\Red}{Red}


%MathShortcuts
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}

\newcommand{\RRpos}{\RR_+}

\newcommand{\pcone}[2]{\operatorname{cone}^{(#2)}(#1)}
\newcommand{\ssm}{\smallsetminus}
\newcommand{\nor}[1]{{#1}^\circ}

\newcommand{\set}[2]{\left\{ #1 \;|\; #2 \right\}}
\newcommand{\bigset}[2]{\left\{ #1 \;\big|\; #2 \right\}}
\newcommand{\bigbracket}[1]{\left\{ #1 \right\}}
\newcommand{\multiset}[2]{\left\{\!\!\left\{ #1 \;|\; #2 \right\}\!\!\right\}}
\newcommand{\multibracket}[1]{\left\{\!\!\left\{ #1 \right\}\!\!\right\}}
\newcommand{\bigmultiset}[2]{\big\{\!\!\big\{ #1 \;\big|\; #2 \big\}\!\!\big\}}
\newcommand{\bigmultibrackets}[1]{\big\{\!\!\big\{ #1 \big\}\!\!\big\}}

\newcommand{\Mink}{{\sum}}


%ReflectionGroup
\newcommand{\Sym}{{\mathfrak{S}}}
\newcommand{\sref}{\mathcal{S}}
\newcommand{\tref}{\mathcal{R}}
\newcommand{\wo}{{w_\circ}}
\newcommand{\one}{{e}}
\newcommand{\emptyword}{{\varepsilon}}
\newcommand{\csys}{{(W,\sref)}}
\newcommand{\At}[2]{{At_{[#1,#2]}}}
\newcommand{\Cplus}[2]{{\mathcal{C}^+(#1,#2)}}
\newcommand{\Cminus}[2]{{\mathcal{C}^-(#1,#2)}}
\newcommand{\Eplus}[2]{{\mathcal{E}^+(#1,#2)}}
\newcommand{\Eminus}[2]{{\mathcal{E}^-(#1,#2)}}
\newcommand{\Phiplus}{\Phi^+}
\newcommand{\Phiminus}{\Phi^-}
\newcommand{\Phipm}{\Phi_{\geq -1}}
\newcommand{\refl}{\mathcal{R}}
\newcommand{\innerform}[2]{{\langle #1 ~|~ #2 \rangle}}

%Weak order
\newcommand{\precweak}{\prec_\mathsf{R}}
\newcommand{\leqweak}{\leq_\mathsf{R}}
\newcommand{\inv}{\operatorname{Inv}}
\newcommand{\weakint}[2]{[#1,#2]_{\mathsf{R}}}
\newcommand{\idweak}[1]{{\operatorname{Id}_{\mathsf{R}}(#1)}}

%Bruhat order
\newcommand{\precbru}{\prec}
\newcommand{\leqbru}{\leq}

%SubwordComplex
\newcommand{\subwordComplex}{\mathcal{SC}}
\newcommand{\greedy}{I_{\operatorname{g}}}
\newcommand{\antigreedy}{I_{\operatorname{ag}}}
\newcommand{\demazure}[1]{{\operatorname{Dem}}(#1)}

\newcommand{\brickVector}[1]{{{\sf b}({#1})}}
\newcommand{\brickCone}{{\sf C}}
\newcommand{\brickPolytope}{\mathcal{B}}

\newcommand{\Root}[2]{{\sfr}(#1,#2)}
\newcommand{\Roots}[1]{{\sfR}(#1)}
\newcommand{\RootsLoc}[2]{{\sfR_{#1}}(#2)}
\newcommand{\RootsPos}[2]{{\operatorname{Pos}_{#2}(#1)}}
\newcommand{\RootsPlus}[1]{{\sfR}^+(#1)}
\newcommand{\RootsMinus}[1]{{\sfR}^-(#1)}
\newcommand{\Weight}[2]{{\sfw}(#1,#2)}
\newcommand{\Weights}[1]{{\sfW}(#1)}

\newcommand{\coRoot}[2]{{\sfr^\vee}(#1,#2)}
\newcommand{\coRoots}[1]{{\sfR^\vee}(#1)}
\newcommand{\coWeight}[2]{{\sfw^\vee}(#1,#2)}
\newcommand{\coWeights}[1]{{\sfW^\vee}(#1)}

\newcommand{\IntervalWeight}[1]{{\operatorname{Int}\big(\Weight{\greedy}{#1},\ \Weight{\antigreedy}{#1}\big)}}
\newcommand{\IntervalRoot}[1]{{\operatorname{Int}\big(0,\ \Root{\greedy}{#1}\big)}}


%TextShortcuts
\newcommand{\ie}{\textit{i.e.}}
\newcommand{\eg}{\textit{e.g.}}

\newcommand{\Dfn}[1]{\emph{\bfseries #1}}

\newcommand{\sq}[1]{{\rm #1}}
\newcommand{\Q}{\sq{Q}}
\newcommand{\q}{\sq{q}}
\newcommand{\s}{\sq{s}}
\newcommand{\y}{\sq{y}}
\newcommand{\w}{\sq{w}}
\renewcommand{\c}{\sq{c}}

\newcommand{\sfr}{{\sf r}}
\newcommand{\sfR}{{\sf R}}
\newcommand{\sfw}{{\sf w}}
\newcommand{\sfW}{{\sf W}}
\newcommand{\sfB}{{\sf B}}

\newcommand{\mi}[1]{{\overline{#1}}}
\newcommand{\del}[1]{{{#1}_\Delta}}
\newcommand{\delmin}[1]{{\overline{#1}_\Delta}}


%Colours
\definecolor{darkblue}{rgb}{0,0,0.7}
\newcommand{\darkblue}{\color{darkblue}}

\definecolor{lightblue}{rgb}{0.68,0.85,1}

\definecolor{lightgrey}{rgb}{0.9,0.9,0.9}
\newcommand{\lightgrey}{\cellcolor{lightgrey}}

\definecolor{grey}{rgb}{0.5,0.5,0.5}
\newcommand{\grey}{\cellcolor{grey}}

\newcommand{\black}{\color{black}}
\newcommand{\gray}{\color{gray}}
\newcommand{\red}{\color{red}}
\newcommand{\green}{\color{green}}
\newcommand{\yellow}{\color{yellow}}
\newcommand{\orange}{\color{orange}}
\newcommand{\purple}{\color{purple}}
\newcommand{\violet}{\color{violet}}
\newcommand{\olive}{\color{olive}}

\newcommand{\markedbox}[1]{{\bf{\color{red} #1}}}

%Other
\newcommand{\normalfan}[1]{{\mathcal{N}(#1)}}
\newcommand{\normalcone}[1]{{\operatorname{C}^{\diamond}(#1)}}
\newcommand{\bignormalcone}[1]{{\operatorname{C}^{\diamond}\big(#1\big)}}
\newcommand{\permutahedron}[1]{{\operatorname{Perm}(#1)}}
\newcommand{\coxeterfan}[1]{{\mathcal{CF}_{#1}}}

\renewcommand{\th}{\textsuperscript{th}}
\newcommand{\st}{\textsuperscript{st}}

\newcommand\T{\rule{0pt}{2ex}}       %
\newcommand\B{\rule[-2ex]{0pt}{0pt}} %

\newcommand{\dotprod}[2]{\left\langle \, #1 \,\middle|\, #2 \, \right\rangle} %
\newcommand{\bigdotprod}[2]{\big\langle \, #1 \,\big|\, #2 \, \big\rangle} %
\newcommand{\smalldotprod}[2]{\langle \, #1 \,|\, #2 \, \rangle} %

\newcommand{\wordprod}[2]{\Pi{#1}_{#2}} %

%
%
%
%


%% define your title in the usual way
\title[Bruhat Intervals, Subword Complexes and Brick Polyhedra]{Bruhat Intervals, Subword Complexes and Brick Polyhedra for Finite Coxeter Groups}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[D.~Jahn and C.~Stump]{Dennis Jahn\thanks{\href{mailto:dennis.jahn@rub.de}{dennis.jahn@rub.de}}\addressmark{1} \and Christian Stump\thanks{\href{mailto:christian.stump@rub.de}{christian.stump@rub.de}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Fakult\"at f\"ur Mathematik, Ruhr-Universit\"at Bochum, Germany}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
  We study the 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.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Coxeter groups, Bruhat order, Bruhat cones, subword complexes, brick polyhedra}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{JS2021.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
\label{sec:intro}

We introduce brick polyhedra associated to subword complexes for finite Coxeter systems.
These generalize brick polytopes for root-independent spherical subword complexes as defined and studied by Pilaud and the second author~\cite{Pilaud-Stump-2015}.
We study brick polyhedra by closely tying them to the theory of Bruhat interval cones of Dyer~\cite{Dyer-1994}.
We start with naturally extending this theory and then showing how brick polyhedra naturally arise from the recursive structure of subword complexes.
%Our construction extends the properties of brick polytopes towards general subword complexes and, in the spherical case, coincides with the previously known brick polytope.

\medskip

Let $\csys$ be a finite type Coxeter system of rank~$n = |\sref|$ acting on a Euclidean vector space~$V \cong \RR^n$ with inner form $\langle \cdot, \cdot \rangle$.
Let $\Delta \subseteq \Phiplus \subseteq \Phi \subseteq V$ be a root system for $\csys$ with simple roots $\Delta = \set{ \alpha_s }{ s \in \sref }$, positive roots~$\Phiplus$, and negative roots $\Phiminus = -\Phiplus$.
The reflections in~$W$ are $\tref = \set{s_\beta}{\beta \in \Phiplus}$ where $s_\beta$ denotes the reflection sending~$\beta$ to its negative while fixing pointwise its orthogonal complement~$\beta^\perp = \set{v \in V}{\langle \beta, v \rangle = 0}$.
The corresponding Cartan matrix $(a_{st})_{s,t \in \sref}$ is given by $s(\alpha_t) = \alpha_t - a_{st} \alpha_s$.
The fundamental weights $\nabla = \set{ \omega_s }{ s \in \sref } \subseteq V$ are then given by the relations $\alpha_s = \sum_{t \in \sref} 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 \sref$.

\medskip

Furthermore denote by~$\leq$ the \Dfn{(strong) Bruhat order} on $W$ and write~$\prec$ for cover relations.
For a Bruhat interval $[x,y]$, the \Dfn{(upper) Bruhat cone} $\Cplus{x}{y}$ is defined by $\Cplus{x}{y} = \cone\Eplus{x}{y}$ for $\Eplus{x}{y}  = \bigset{\beta \in \Phiplus}{x \prec s_\beta x \leq y}$.
These cones were introduced and studied by Dyer in the study of positivity properties of Kazhdan--Lusztig and Stanley polynomials~\cite{Dyer-1994}.

\medskip

For a (not necessarily reduced) word $\Q = \s_1 \cdots \s_m$ in $\sref$ the \Dfn{Demazure product} $\demazure{\Q} \in W$ can be defined as the unique maximal element in Bruhat order among all expressions obtained from $\Q$ by removing letters.
For $w \in W$ and~$\Q$ as above, the \Dfn{subword complex} $\subwordComplex(\Q,w)$ is the simplicial complex of sets of (positions of) letters in~$\Q$ whose complements contain reduced words for~$w$.
Subword complexes have been introduced by Knutson and Miller in the context of Gr\"obner geometry of Schubert varieties~\cite{KM2004, KM2005} and it is known that $\subwordComplex(\Q,w)$ is non-empty if and only if $w \leq \demazure{\Q}$.
Furthermore as shown in \cite[Theorem 3.7, Corollary 3.8]{KM2004} the non-empty complex $\subwordComplex(\Q,w)$ is a topological sphere if and only if $w = \demazure{\Q}$ and a topological ball otherwise.

\medskip

Strongly connected to the internal structure of subword complexes is the construction of root configurations introduced in~\cite{CLS-14}.
For~$\Q = \s_1 \cdots \s_m$, a facet~$I$ of $\subwordComplex(\Q,w)$, and a position $k \in [m] = \{1,\ldots,m\}$ the \Dfn{root function} $\Root{I}{\cdot} \colon [m] \rightarrow \Phi = W(\Delta) \subseteq V$ is defined by
\[
  \Root{I}{k} = \wordprod{\Q}{\{1,\dotsc,k-1\} \setminus I}(\alpha_{s_k}),
\]
where $\wordprod{\Q}{X}$ denotes the product of the simple reflections $s_i$, for $i \in X$ in the given order.
The ordered multiset $\Roots{I} = \multiset{\Root{I}{i}}{i \in I}$ is then called \Dfn{root configuration} of the facet~$I$.
The first main theorem of this work now describes how closely tightened Dyer's Bruhat cones are to root configurations of facets of subword complexes.

\begin{theorem}
  \label{thm:cone_equality}
  Let~$\Q$ be a word in~$\sref$ and let $w \in W$ with $w \leq \demazure{\Q}$.
  Then
  \[
  \Cplus{w}{\demazure{\Q}} = \bigcap_I \cone\Roots{I}
  \]
  where the intersection is taken over all facets~$I$ of the subword complex $\subwordComplex(\Q,w)$.
\end{theorem}

The purpose of \Cref{sec:bruhatcoversandsubwordcomplexes} below and its subsections is to gather the statements that are involved in the proof of this theorem as well as their corollaries.
These include various new statements about Bruhat cones in \Cref{sec:conesinbruhatintervals} and moreover \Cref{prop:connectedcomp}.
The latter is based on a conjecture in~\cite[Conjeture~7.1]{Pilaud-Stump-2015} and it is the key ingredient for the statements in \Cref{sec:brickpolytopes}

Therein we introduce brick polyhedra for subword complexes and study their properties.
Brick polyhedra can be seen as a generalization of the previously known brick polytopes in the sense that they provide generalizations of the properties that brick polytopes could only provide for certain types of spherical subword complexes.

This includes \Cref{cor:vertexpointedcone} where the root configuration of a facet is connected to its associated point in the brick polyhedron, \Cref{thm:brickpolynormalcone} and \Cref{thm:coarseningcoxeter} where we describe how to obtain the normal fan of the brick polyhedron from the Coxeter fan, and \Cref{thm:brickpolycontainment} where we explain how brick polyhedra associated to a common word~$\Q$ but different elements interfere with each other.

\medskip

Most details and all proofs are omitted in this extended abstract because of the limited space, but they and also more examples can be found in the full version of this work~\cite{JS21}.

\medskip

To illustrate our results we will present examples in the Coxeter system of type $A_2$.
We generally write~$\sref = \{s_1,s_2\}$ for concrete generators~$s_i$ and also $\Delta = \{\alpha_1,\alpha_2\}$ for simple roots with $\alpha_i = \alpha_{s_i}$.
To keep examples compact, we write shorthand $\Q = 12212 = \s_1\s_2\s_2\s_1\s_2$ for words in~$\sref$ and also for elements $w = 121 = s_1s_2s_1 \in W$ as reduced words, and we abbreviate $\del{21} = 2\alpha_1+\alpha_2$ and $\delmin{21} = -\del{21}$ for vectors written in the basis of simple roots.

\begin{example}[Type $A_2$]
  We have $\sref = \{ s_1,s_2 \}$, the simple and positive roots $\Delta \subset \Phiplus$ given by
  $
  \{ \del{10}, \del{01} \}\subset \{ \del{10},\del{01},\del{11} \}
  $
  and
  \[
  s_1(\del{10}) = \delmin{10}, \quad s_1(\del{01}) = \del{11},\quad
  s_2(\del{10}) = \del{11}, \quad s_2(\del{01}) = \delmin{01}.
  \]
  The fundamental weights are
  $
  \nabla = \{ \omega_1 = \tfrac{1}{3}(\del{21}), \omega_2 = \tfrac{1}{3}(\del{12}) \}.
  $
\end{example}

\section{The interplay between Bruhat intervals and subword complexes}
\label{sec:bruhatcoversandsubwordcomplexes}

\subsection{Properties of Bruhat cones}
\label{sec:conesinbruhatintervals}

In this section we develop properties of Bruhat cones.
Those properties are independent from the theory of subword complexes and generalize the previously known statements of Dyer.
Denote by~$\wo$ the unique longest element in~$W$.
The set $\Eminus{x}{y}$ and with it $\Cminus{x}{y}$ are defined similarly to $\Eplus{x}{y}$ and $\Cplus{x}{y}$.
For details we again refer to \cite{JS21}.  

\begin{lemma}[{\cite[Proposition 1.4, Proposition 3.6]{Dyer-1994}}]
  \label{lem:dyer}
  Let $[x,y]$ be a Bruhat interval and let $w \in W$.
  Then
  \begin{enumerate}
    \item\label{it:dyer-a} $\Cminus{e}{w} \cap \Cplus{w}{\wo} = \{0\}$ and $\Phiplus \subseteq \Cminus{\one}{w} \cup \Cplus{w}{\wo}$.
    
    \item\label{it:dyer-c} $\Eplus{x}{y}$ are the rays of $\Cplus{x}{y}$ and $\Eminus{x}{y}$ are the rays of $\Cminus{x}{y}$.
    
    \item\label{it:dyer-d} For $\beta \in \Eplus{x}{y}$ we have $\Cplus{x}{y} \subseteq \Cplus{s_\beta x}{y} + \RR (\beta)$, and similar for $\Cminus{x}{y}$.
    
    \item\label{it:dyer-e} For $\beta \in \Phiplus$ with $x \leq s_\beta x \leq y$ we have $\beta \in \Cplus{x}{y}$, and similar for $\Cminus{x}{y}$.
  \end{enumerate}
\end{lemma}

\begin{corollary}
  Let $w \in W$ be an element.
  Then $\Eminus{\one}{w}$ are the extremal rays of $\cone\inv(w)$ and $\Eplus{w}{\wo} = \Eminus{\one}{w\cdot\wo}$ are the extremal rays of $\cone\inv(w\cdot\wo)$.
  In particular,
  \[
  \Cminus{\one}{w} \cap \Phi = \inv(w), \quad \Cplus{w}{\wo} \cap \Phi = \inv(w\cdot\wo).
  \]
\end{corollary}

In particular, the following statements look similar to \Cref{lem:dyer}\ref{it:dyer-d}.
However, they are far from being corollaries of it and every one of it has its own crucial proof.

\begin{proposition}
  \label{prop:bruhatcone}
  Let $x,y \in W$, $s\in \sref$ and $r = s_\beta \in \tref$ such that $s \neq r$ and $x \prec sx, rx \leq y$.
  Then
  \[
  s(\beta) \in \Cplus{sx}{y} + \RRpos(\alpha_s).
  \]
\end{proposition}

\begin{theorem}
  \label{cor:bruhatcone}
  Let $x,y \in W$ and $s \in \sref$  such that $x \leq y \prec sy$.
  Then
  \[
  \Cplus{x}{sy} \subseteq \Cplus{x}{y} + \RRpos(\alpha_s).
  \]
\end{theorem}

\begin{corollary}
  \label{lem:extendingcovercones}
  Let $x,y \in W$ and $s \in \sref$ such that $sx \prec x \leq y$.
  Let furthermore $\tau \in \{ sy, y \}$ be the Bruhat smaller element.
  Then
  \[
  s\big( \Cplus{x}{y} \big) \subseteq \Cplus{sx}{\tau}.
  \]
\end{corollary}

\begin{corollary}
  \label{cor:weakordercplus}
  Let $x,y \in W$ and $s \in \sref$ such that $xs \prec x \leq y$.
  Let furthermore $\tau \in \{ ys, y \}$ be the Bruhat smaller element.
  Then
  \[
  \Cplus{x}{y} \subseteq \Cplus{xs}{\tau}.
  \]
\end{corollary}

\subsection{Bruhat cones and non-flippable vertices in subword complexes}
\label{sec:nonflipableverticesandbruhatcovers}

For two facets $I \neq J$ of $\subwordComplex(\Q,w)$ we call those facets \Dfn{adjacent} if there are positions $i \in I$ and $j \in J$ such that $I \setminus \{i\} = J \setminus \{j\}$.
The transition from~$I$ to~$J$ is called the \Dfn{flip} of~$i$ in~$I$ and if for any $k \in I$ there is no adjacent facet that flips~$k$, we call the position~$k$ non-flippable in~$I$. 
Furthermore for a given $\beta \in \Eplus{w}{\demazure{\Q}}$,~\ie, $w \prec s_\beta w \leq \demazure{\Q}$, consider the map
\begin{equation}
\label{eq:iota}
  \iota \colon \subwordComplex(\Q,s_\beta w) \rightarrow \subwordComplex(\Q, w)
\end{equation}
from facets of $\subwordComplex(\Q,s_\beta w)$ to facets of $\subwordComplex(\Q,w)$ given by $J \mapsto J \cup \{k\}$ where~$k$ is the unique index in the complement of~$J$ such that $\Q_{\{1,\dotsc,m\} \setminus (J \cup \{k\})}$ is a reduced word for~$w$.
This unique index is well-defined by the deletion property of Bruhat order, saying that for any reduced word $\s_1\cdots \s_\ell$ for~$s_\beta w$ there is a unique index~$k$ such that $\s_1\cdots \widehat \s_k \cdots \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 $\subwordComplex(\Q,s_\beta w)$ is also a face of $\subwordComplex(\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 \cite[Example 3.10]{JS21}.
The following two lemmas now describe how facets of the subword complex for~$w$ can lead to facets of the complex for $s_\beta w$.

\begin{lemma}
  \label{lem:nonflippablesarepositive}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex, let $I \in \subwordComplex(\Q,w)$ be a facet and let $i \in I$ non-flippable.
  Then $I \setminus \{i\}$ is a facet of $\subwordComplex(\Q,s_\beta w)$ for $\beta = \Root{I}{i}$.
  In particular, the complement of $I \setminus \{i\}$ is a reduced word and $\beta \in \Eplus{w}{\demazure{\Q}}$.
\end{lemma}

\begin{lemma}
  \label{lem:coversandnonflipables}
  Let $w \prec s_\beta w \leq \demazure{\Q}$.
  Then:
  \begin{enumerate}
    \item\label{it:coversandnonflipables-b} There is a facet $I \in \subwordComplex(\Q,w)$ and an index $i \in I$ with $\Root{I}{i} = \beta$.
    \item\label{it:coversandnonflipables-c} A facet $I \in \subwordComplex(\Q,w)$ is in the image of $\iota$ if and only if $\beta \in \Roots{I}$.
  \end{enumerate}
\end{lemma}

\begin{proposition}
  \label{prop:bruhatcoversandrootfunction}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex.
  Then
  \[
  \Eplus{w}{\demazure{\Q}} = \bigset{\Root{I}{i}}{I \text{ facet of }\subwordComplex(\Q,w) \text{ and } i \in I \text{ not flippable}}.
  \]
  Moreover, if~$i \in I$ is a flippable index in a facet~$I$ of $\subwordComplex(\Q,w)$ then $\Root{I}{i} \notin \Eplus{w}{\demazure{\Q}}$.
\end{proposition}

\begin{proposition}
  \label{prop:nonflipablerootincone}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex.
  Then
  \[
  \Eplus{w}{\demazure{\Q}} \subseteq \cone( \Roots{F} )
  \]
  for every facet $F \in \subwordComplex(\Q,w)$.
  This leads to the first containment needed for \Cref{thm:cone_equality}:
  \[
    \Cplus{w}{\demazure{\Q}} \ \subseteq \ \bigcap_F \cone\Roots{F}.
  \]
\end{proposition}

\subsection{Constructing antigreedy facets inside certain half-spaces}
\label{sec:algorithm}

The Demazure product of a given word $\Q = \s_1 \ldots \s_m$ can be computed by scanning through~$\Q$ from left to right, starting with the identity element and multiplying by the current~$s_i$ from the right whenever we go upwards in (right) weak order.
For spherical subword complexes this \emph{greedy algorithm} also computes the antigreedy facet,~\ie, the lexicographically last facet of the complex, given by the complement of the positions used for the Demazure product.

\begin{example}[Type $A_2$]
  For $\Q = 22121$ the Demazure product is given by $\demazure{\Q} = 121$.
  By scanning from left to right we obtain the reduced word and facet:
  \[
    w = 212 \quad \text{ and } \quad I = \{2,5\}.
  \]
\end{example}

The following \Cref{algo:uniquefacet} describes a generalization of this method in two ways.
First it computes a facet of $\subwordComplex(\Q,w)$ for any $w \leq \demazure{\Q}$.
Second the computation respects a given linear functional $f \colon V \rightarrow \RR$ such that the root configuration of the computed facet is contained in the positive halfspace defined by~$f$.
By \Cref{prop:nonflipablerootincone} the latter is only possible if $f(\beta) \geq 0$ for all $\beta \in \Eplus{w}{\demazure{\Q}}$, leading to the restriction in the algorithm.
We call those functionals non-negative for the Bruhat interval $[w,\demazure{\Q}]$.

\begin{algo}
  \label{algo:uniquefacet}
  Computing the $f$-antigreedy facet $I_f$ of the subword complex $\subwordComplex(\Q,w)$
  
  \begin{algorithm}[H]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Conditions}{Conditions}
    \SetKwInOut{Output}{Output}
    
    \Input{$\Q = \s_1\cdots\s_m$\\ $w \leq \demazure{\Q}$\\ $f \colon V \rightarrow \RR$ with $f(\beta) \geq 0$ for $\beta \in \Eplus{w}{\demazure{\Q}}$}
    \bigskip
    \Conditions{Conditions (1)--(6) are given by the following decision tree:\\
      \medskip
      \begin{tikzpicture}[scale=0.5]
      
      \node (f) at (6,15) {$\operatorname{sgn}( f(\beta_k) )$};
      
      \node[violet] (beta1) at (0,9)  {$(4)$};
      \node         (beta2) at (6,9)  {$\beta_k \in \Phiplus$};
      \node         (beta3) at (12,9) {$\beta_k \in \Phiplus$};
      
      \node       (gc1) at (3,6)  {$w_{k-1} s_k \leqweak w$};
      \node[blue] (gc2) at (9,6)  {$(2)$};
      \node       (gc3) at (15,6) {$w_{k-1} s_k \leqweak w$};
      
      \node[violet] (dem1) at (0,3)  {$(5)$};
      \node         (dem2) at (18,3) {$w_{k-1}^{-1} w \leq \demazure{\s_{k+1}\cdots\s_m}$};
      
      \node[blue]   (a1) at (9,0)  {$(1)$};
      \node[blue]   (a2) at (15,0) {$(3)$};
      \node[violet] (a3) at (21,0) {$(6)$};
      
      \draw (beta1) -- (f) -- (beta2);
      \draw (beta3) -- (f);
      
      \node[fill=white] (fv1) at (3,12) {$-$};
      \node[fill=white] (fv2) at (6,12) {$0$};
      \node[fill=white] (fv3) at (9,12) {$+$};
      
      \draw[green] (beta2) -- (gc1) -- (dem1);
      \draw[green] (beta3) -- (gc3) -- (dem2) -- (a2);
      
      \draw[red] (beta2) -- (gc2) -- (beta3);
      \draw[red] (gc1) -- (a1) -- (gc3);
      \draw[red] (dem2) -- (a3);
      
      \node[fill=white] (betav1) at (4.5,7.5)  {$T$};
      \node[fill=white] (betav2) at (7.5,7.5)  {$F$};
      \node[fill=white] (betav3) at (10.5,7.5) {$F$};
      \node[fill=white] (betav4) at (13.5,7.5) {$T$};
      
      \node[fill=white] (lwv1) at (1.5,4.5)  {$T$};
      \node[fill=white] (lwv2) at (6,3)      {$F$};
      \node[fill=white] (lwv3) at (12,3)     {$F$};
      \node[fill=white] (lwv4) at (16.5,4.5) {$T$};
      
      \node[fill=white] (bwv1) at (16.5,1.5) {$T$};
      \node[fill=white] (bwv2) at (19.5,1.5) {$F$};
      
      \end{tikzpicture} \\
      The sign can be positive ($+$), negative ($-$), or zero ($0$). \\
      The statements can be true ($T$) or false ($F$).}
    \bigskip
    \Output{$I_f \subset \{1,\dotsc,m\}$}
    \bigskip
    
    $w_0              \leftarrow \one \in W$\\
    $I_0 \hspace*{3pt}\leftarrow \{\}$\\
    \bigskip
    
    \For{$k = 1,\dotsc, m$}{
      $\beta_k        \leftarrow w_{k-1}(\alpha_{s_k})$
      
      \If{Condition (1) or (2) or (3)}{
        $I_k \hspace*{3pt}\leftarrow I_{k-1} \cup \{k\}$ \\
        $w_k              \leftarrow w_{k-1}$
      }
      \ElseIf{Condition (4) or (5) or (6)}{
        $I_k \hspace*{3pt}\leftarrow I_{k-1}$ \\
        $w_k              \leftarrow w_{k-1} \cdot s_k$
      }
    }
    $I_f \leftarrow I_m$ \\
    \Return $I_f$
  \end{algorithm}
\end{algo}

\begin{proposition}
  \label{prop:algoprops}
  At the end of the $k$-th iteration of the \emph{for loop}, the word $\Q_{\{1,\dotsc,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 $\Q_{\{k+1\,\dotsc,m\}}$.
\end{proposition}

\begin{theorem}
  \label{prop:algowelldefined}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex and let $f \colon V \rightarrow \RR$ be non-negative on $[w,\demazure{\Q}]$.
  The output set~$I_f \subseteq \{1,\dotsc,m\}$ of \Cref{algo:uniquefacet} has the following properties:
  \begin{enumerate}
    \item\label{it:algowelldefined-a} $I_f$ is a facet of the subword complex $\subwordComplex(\Q,w)$, \ie, the word $\Q_{\{1,\dotsc,m\} \setminus I_f}$ is a reduced word for~$w$.
    \item\label{it:algowelldefined-b} For~$i \in I_f$, we have $f(\Root{I_f}{i}) \geq 0$.
    \item\label{it:algowelldefined-c} For~$i \in I_f$ with $f(\Root{I_f}{i}) = 0$ and $\Root{I_f}{i} \not\in \Eplus{w}{\demazure{\Q}}$, we have $\Root{I_f}{i} \in \Phiminus$.
  \end{enumerate}
\end{theorem}

\begin{remark}
  Applying this algorithm for $w \leq \demazure{\Q}$ and a linear functional $f \colon V \rightarrow \RR$ which is positive on
  \begin{itemize}
    \item the basis $\Delta$ of~$V$, \ie, $f(\alpha_s) > 0$ for all $s \in \sref$, yields the greedy facet~$\greedy$,
    \item the basis $w(\Delta)$ of~$V$, \ie, $f(w(\alpha_s)) > 0$ for all $s \in \sref$, yields the antigreedy facet~$\antigreedy$,
  \end{itemize}
  of $\subwordComplex(\Q,w)$.
\end{remark}

We can now take any vector~$v \notin \Cplus{w}{\demazure{\Q}}$, and choose a linear functional that is non-negative for $[w,\demazure{\Q}]$ while $f(v) < 0$.
We then obtain $v \notin \cone(\Roots{I})$.
This implies the remaining inclusion
\[
  \Cplus{w}{\demazure{\Q}} \ \supseteq \ \bigcap_I \cone\Roots{I},
\]
and thus concludes the proof of \Cref{thm:cone_equality}.

\subsection{Uniqueness of $f$-antigreedy facets}
\label{sec:uniqueantigreedyfacets}

In \Cref{prop:algowelldefined} we describe the properties the facet $I_f$ computed by \Cref{algo:uniquefacet} has.
In this section we show that these properties uniquely determine this facet among all facets of $\subwordComplex(\Q,w)$.
Furthermore~$I_f$ is in the set of all facets with root configuration contained in the positive halfspace defined by~$f$:
\[
  I_f \in \subwordComplex_f(\Q,w) = \bigset{I \text{ facet of } \subwordComplex(\Q,w)}{\text{for all } i \in I : f( \Root{I}{i} ) \geq 0},
\]
and by \Cref{prop:connectedcomp} this set forms a connected component of the graph of $f$-preserving flips, where a flip of $i \in I$ is called $f$-preserving, if $f( \Root{I}{i} = 0$.

\begin{proposition}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex and let $f \colon V \rightarrow \RR$ be a linear functional.
  Then
  \[
  \subwordComplex_f(\Q,w) \text{ is non-empty if and only if } f \text{ is non-negative on } [w,\demazure{\Q}].
  \]
\end{proposition}

\begin{corollary}
  \label{prop:connectedcomp}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex and let $f \colon V \rightarrow \RR$ be a linear functional which is non-negative on $[w,\demazure{\Q}]$.
  Then $\subwordComplex_f(\Q,w)$ forms a connected component of the graph of $f$-preserving flips in $\subwordComplex(\Q,w)$ and moreover,
  \[
  \subwordComplex_f(\Q,w) \cong \subwordComplex(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I}{f}}, w)
  \]
  for any facet $I \in \subwordComplex_f(\Q,w)$.
\end{corollary}

\begin{theorem}
  \label{thm:uniquefantigreedyfacet}
  Let~$I$ be a facet of the non-empty subword complex $\subwordComplex(\Q,w)$ and let $f \colon V \rightarrow \RR$ be a linear functional that is non-negative for the Bruhat interval $[w,\demazure{\Q}]$.
  If the facet~$I$ satisfies the conclusions in \Cref{prop:algowelldefined}\ref{it:algowelldefined-b} and \ref{it:algowelldefined-c}, then $I = I_f$ is the facet produced by \Cref{algo:uniquefacet}.
\end{theorem}

\section{Brick polyhedra for subword complexes}
\label{sec:brickpolytopes}

In this section we associate to a subword complex a convex polyhedron, the brick polyhedron.
Similar to the root function, for each facet $I \in \subwordComplex(\Q,w)$ we define the \Dfn{weight function} by:
\[
  \Weight{I}{k} = \wordprod{\Q}{\{1,\dotsc,k-1\} \setminus I}(\omega_{s_k}).
\]
This function is then used to define the \Dfn{brick vector}~$\brickVector{I}$ of the facet~$I$:
\[
  \brickVector{I} = - \sum\limits_{k=1}^{m} \Weight{I}{k}.
\]

\begin{definition}
  \label{def:brickpolytope}
  The \Dfn{brick polyhedron} of a non-empty subword complex $\subwordComplex(\Q,w)$ is the Minskowski sum of the convex hull of all brick vectors and the Bruhat cone, which is denoted by $\Cplus{w}{\demazure{\Q}}$:
  \[
  \brickPolytope(\Q,w) = \conv\bigset{\brickVector{I}}{I \text{ facet of } \subwordComplex(\Q,w)} + \Cplus{w}{\demazure{\Q}}. 
  \]
\end{definition}

For spherical subword complexes this construction coincides (up to a sign) with the previously known brick polytope.

\begin{proposition}
  The brick polyhedron $\brickPolytope(\Q,w)$ of a non-empty subword complex $\subwordComplex(\Q,w)$ is polytopal if and only if $\subwordComplex(\Q,w)$ is spherical.
  In this case, the brick polyhedron is the convex hull of all brick vectors.
\end{proposition}

\begin{example}[Type $A_2$]
  \label{ex:brickpoly}
  Let $\Q = 11212$ and $w = 12$.
  We then have the facets of $\subwordComplex(\Q,w)$ and the brick polyhedron $\brickPolytope(\Q,w)$ given by
  \[
  \begin{tikzpicture}[scale=1.5]
  \draw[fill=grey!20, grey!20] (2.598,3) -- (-1.299,0.75) -- (-1.299,-0.75) -- (1.299,-2.25) -- (5.196,0) -- (2.598,3);
  
  \draw[green!10] (-2.165,-1.25) -- (4.33,2.5);
  \draw[green!10] (-2.165,1.25) -- (3.2475,-1.875);
  \draw[green!10] (0,-2.5) -- (0,2.5);
  
  \node (a1) at (0,-2.5)     {$\brickVector{\{1,2,3\}} = \tfrac{1}{3}(\del{\mi{87}})$};
  \node (a2) at (-1.3,-1.75) {$\brickVector{\{1,3,4\}} = \tfrac{1}{3}(\del{\mi{77}})$};
  \node (a3) at (1.5,0)      {$\brickVector{\{1,4,5\}} = \tfrac{1}{3}(\del{\mi{66}})$};
  \node (a4) at (-2.6,-0.75) {$\brickVector{\{2,3,4\}} = \tfrac{1}{3}(\del{\mi{67}})$};
  \node (a5) at (-2.6,0.75)  {$\brickVector{\{2,4,5\}} = \tfrac{1}{3}(\del{\mi{56}})$};
  
  \draw (2.598,3) -- (-1.299,0.75) -- (-1.299,-0.75) -- (1.299,-2.25) -- (5.196,0);
  \draw[-{>[scale=1.2]}] (-1.299,0.75) -- (2.598,3);
  \draw[-{>[scale=1.2]}] (1.299,-2.25) -- (5.196,0);
  
  \draw[darkblue, line width = 2pt, ->] (1.299,-2.25) -- (1.732,-2);
  \draw[darkblue, line width = 2pt, ->] (1.299,-2.25) -- (0.866,-2);
  
  \draw[darkblue, line width = 2pt, ->] (0,-1.5) -- (-0.433,-1.25);
  \draw[darkblue, line width = 2pt, ->] (0,-1.5) -- (0.433,-1.75);
  \draw[darkblue, line width = 2pt, ->] (0,-1.5) -- (0,-1);
  
  \draw[darkblue, line width = 2pt, ->] (0,0) -- (0,-0.5);
  \draw[darkblue, line width = 2pt, ->] (0,0) -- (0.433,0.25);
  \draw[darkblue, line width = 2pt, ->] (0,0) -- (-0.433,0.25);
  
  \draw[darkblue, line width = 2pt, ->] (-1.299,-0.75) -- (-1.299,-0.25);
  \draw[darkblue, line width = 2pt, ->] (-1.299,-0.75) -- (-0.866,-1);
  
  \draw[darkblue, line width = 2pt, ->] (-1.299,0.75) -- (-1.299,0.25);
  \draw[darkblue, line width = 2pt, ->] (-1.299,0.75) -- (-0.866,1);
  \draw[darkblue, line width = 2pt, ->] (-1.299,0.75) -- (-0.866,0.5);
  
  \node (b1) at (1.299,-2.25) {$\bullet$};
  \node (b2) at (0,-1.5) {$\bullet$};
  \node (b3) at (0,0) {$\bullet$};
  \node (b4) at (-1.299,-0.75) {$\bullet$};
  \node (b5) at (-1.299,0.75) {$\bullet$};
  
  \end{tikzpicture}
  \]
  with arrows pointing towards the respective root configurations
  \begin{gather*}
  \Roots{\{1,2,3\}} = \{\del{10},~ \del{10},~ \del{01}\}, \quad 
  \Roots{\{1,3,4\}} = \{\del{10},~ \del{11},~ \del{\mi{10}}\}, \\
  \Roots{\{1,4,5\}} = \{\del{10},~ \del{01},~ \del{\mi{11}}\}, \quad 
  \Roots{\{2,3,4\}} = \{\del{\mi{10}},~ \del{11},~ \del{\mi{10}}\}, \\
  \Roots{\{2,4,5\}} = \{\del{\mi{10}},~ \del{01},~ \del{\mi{11}}\}.
  \end{gather*}
\end{example}

\subsection{Local cones of brick polyhedra at brick vectors}

To precisely state the connections between subword complexes and brick polyhedra we need the following definition.
The \Dfn{local cone} of a polyhedron~$P$ at a point~$q \in P$ is the cone over~$P$ seen from the point~$q$,
\[
  \pcone{P}{q} = \cone\set{p-q}{p \in P}.
\]

\begin{theorem}
  \label{cor:vertexpointedcone}
  The local cone of the brick polyhedron $\brickPolytope(\Q,w)$ at the brick vector $\brickVector{I}$ coincides with the cone generated by the root configuration of the facet~$I$ of $\subwordComplex(\Q,w)$.
  In symbols,
  \[
  \pcone{\brickPolytope(\Q,w)}{\brickVector{I}} = \cone \Roots{I}.
  \]
  In particular, the brick vector $\brickVector{I}$ is a vertex of $\brickPolytope(\Q,w)$ if and only if $\Roots{I}$ is pointed.
\end{theorem}

\begin{corollary}
  \label{cor:brickpolyhdescription}
  We have
  \[
  \brickPolytope(\Q,w) =  \bigcap_{I \text{ facet of } \subwordComplex(\Q,w)} \big( \brickVector{I} +  \cone \Roots{I} \big).
  \]
\end{corollary}

A linear functional $f \colon V \rightarrow \RR$ is a defining functional for the non-empty brick polyhedron $\brickPolytope(\Q,w)$ if and only if it is non-negative on the interval $[w,\demazure{\Q}]$.
For such a defining functional~$f$ with corresponding defining hyperplane $(f,b)$, denote by $B_f = \set{ v \in P}{f(v) + b = 0}$ the corresponding face of $\brickPolytope(\Q,w)$.

\begin{proposition}
  \label{prop:facesofbrickpolyarebrickpoly}
  Let $f \colon V \rightarrow \RR$ be a linear functional which is non-negative on $[w,\demazure{\Q}]$.
  For a facet $I \in \subwordComplex(\Q,w)$, we have
  \[
  \brickVector{I} \in B_f \Longleftrightarrow I \in \subwordComplex_{f}(\Q,w).
  \]
\end{proposition}

\begin{corollary}
  \label{cor:edgesareflips}
  Any two facets~$I$ and~$J$ of $\subwordComplex(\Q,w)$ whose brick vectors $\brickVector{I}, \brickVector{J}$ are contained in an edge $E \subseteq \brickPolytope(\Q,w)$ are connected by a flip.
\end{corollary}

\begin{remark}
  We have seen in \Cref{prop:facesofbrickpolyarebrickpoly} that brick vectors contained in a face~$B_f$ of the brick polyhedron $\brickPolytope(\Q,w)$ are in one-to-one correspondence with facets in $\subwordComplex_f(\Q,w)$.
  We furthermore have by \Cref{prop:connectedcomp} the identification
  \[
  \subwordComplex_f(\Q,w) \cong \subwordComplex(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I_f}{f}}, w),
  \]
  and \Cref{cor:vertexpointedcone} ensures that~$B_f$ and $\brickPolytope(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I_f}{f}}, w)$ have the same \emph{local structure}:
  \begin{itemize}
    \item The direction of flips between brick vectors is preserved,
    \item Local cones in $\brickPolytope(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I_f}{f}}, w)$ agree with those inside the face~$B_f$ of $\brickPolytope(\Q, w)$,
    \item The normal fans of~$B_f$ and of $\brickPolytope(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I_f}{f}}, w)$ coincide, and
    \item $B_f$ is polytopal if and only if $\subwordComplex(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I_f}{f}}, w)$ is spherical.
  \end{itemize}
  Nevertheless, we refer to~\cite[Example 4.10, Remark 4.11]{JS21} to see an example where~$B_f$ and $\brickPolytope(\Q_{\{1,\dotsc,m\} \setminus \RootsPos{I_f}{f}}, w)$ do not coincide.
\end{remark}

\subsection{Normal fans of brick polyhedra from Coxeter fans}
\label{sec:furtherproperties}

Define the \Dfn{Coxeter fan} of~$W$ as 
\[
  \coxeterfan{W} = \bigset{w(\cone\nabla')}{w \in W,\ \nabla' \subseteq \nabla}
\] 
with \Dfn{fundamental chamber} $\mathcal{C} = \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.
For detailed definitions of (inner) normal cones and the (inner) normal fan of a polyhedron we refer to~\cite[Section 4]{JS21}.
To this end, associate to a Bruhat interval $[x,y]$ a (lower) order ideal in the weak order by
\begin{align*}
\idweak{x,y} & = \bigset{w \in W}{\Eplus{x}{y} \subseteq w(\Phiplus)}.
\end{align*}

\begin{proposition}
  Let $\subwordComplex(\Q,w)$ be a non-empty subword complex and let $z \in W$.
  Then there exists a facet~$I$ such that $\Roots{I} \subseteq z(\Phiplus)$ if and only if $z \in \idweak{w,\demazure{\Q}}$.
  In this case, the facet~$I$ is uniquely given by the facet $I_f$ produced by \Cref{algo:uniquefacet} for the linear functional~$f$ which is positive on $z(\Phiplus)$ and negative on $z(\Phiminus)$.
\end{proposition}

For a non-empty subword complex $\subwordComplex(\Q,w)$, this proposition allows to define a map
\[
  \kappa \colon \idweak{w,\demazure{\Q}} \rightarrow \subwordComplex(\Q,w),
\] 
by sending $z \in \idweak{w,\demazure{\Q}}$ to the unique facet~$I_f$ with $\Roots{I} \subseteq z(\Phiplus)$ where~$f$ and~$I_f$ are given as in the proposition.

\begin{proposition}
  \label{lem:kappasurjective}
  The map~$\kappa$ maps surjectively onto the facets of $\subwordComplex(\Q,w)$ with pointed root configurations.
\end{proposition}

\begin{theorem}
  \label{thm:brickpolynormalcone}
  Let $\brickVector{I}$ be a vertex of $\brickPolytope(\Q,w)$, \ie, $I \in \subwordComplex(\Q,w)$ is a facet with pointed root configuration.
  The (closure of the) normal cone $\normalcone{\brickVector{I}}$ is the union of the chambers $z( \mathcal{C} )$ of $\coxeterfan{W}$ given by the elements $z \in W$ with $\kappa(z) = I$.
\end{theorem}

\begin{corollary}
  \label{thm:coarseningcoxeter}
  The normal fan $\normalfan{\brickPolytope(\Q,w)}$ is obtained from the Coxeter fan by gluing together the chambers corresponding to fibers of the map~$\kappa$, and deleting the chambers corresponding to elements in~$W$ not in $\idweak{w,\demazure{\Q}}$.
\end{corollary}

\subsection{Containment properties of brick polyhedra for a fixed word}
\label{sec:brickpolycontainment}

In this section we show how brick polyhedra associated to the same word~$\Q$ but different elements interact with each other.

\begin{proposition}
  \label{prop:brickrelation}
  Let $w \prec s_\beta w \leq \demazure{\Q}$ and $I \in \subwordComplex(\Q, s_\beta w)$ be a facet.
  Then $\brickVector{I} \in \brickPolytope(\Q,w)$.
\end{proposition}

\begin{theorem}
  \label{thm:brickpolycontainment}
  Let $w \in W$ and $s \in \sref$ such that $w \prec ws \leq \demazure{\Q}$.
  Then $\brickPolytope(\Q,ws) \subseteq \brickPolytope(\Q,w)$.
\end{theorem}

The following example shows the nested situation of brick polyhedra for the permutahedron in type~$A_2$.

\begin{example}[Type $A_2$]
  Let $\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 of $\subwordComplex(\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$.
  \[
  \begin{tikzpicture}[scale=0.85]
  \node (121a) at (-2.598,1.5) {$\bullet$};
  \node (121b) at (-1.299,2.25) {$\bullet$};
  \node (121c) at (-1.299,3.75) {$\bullet$};
  \node (121d) at (-2.598,4.5) {$\bullet$};
  \node (121e) at (-3.897,3.75) {$\bullet$};
  \node (121f) at (-3.897,2.25) {$\bullet$};
  \node (121g) at (-2.598,3) {$\bullet$};
  
  \draw (-2.598,1.5) -- (-1.299,2.25) -- (-1.299,3.75) -- (-2.598,4.5) -- (-3.897,3.75) -- (-3.897,2.25) -- (-2.598,1.5);
  \draw[fill=black, opacity=0.05] (-2.598,1.5) -- (-1.299,2.25) -- (-1.299,3.75) -- (-2.598,4.5) -- (-3.897,3.75) -- (-3.897,2.25) -- (-2.598,1.5);
  
  \node[red] (12a) at (-2.598,1.35) {$\bullet$};
  \node[red] (12b) at (-3.997,3.85) {$\bullet$};
  \node[red] (12c) at (-3.997,2.15) {$\bullet$};
  \node[red] (12d) at (-2.598,2.85) {$\bullet$};
  
  \draw[red] (-3.997,3.85) -- (-3.997,2.15) -- (-2.598,1.35);
  \draw[red, -{>[scale=1.2]}] (-3.997,3.85) -- (0, 6.1);
  \draw[red, -{>[scale=1.2]}] (-2.598,1.35) -- (3.897, 5.1);
  \draw[fill=red, opacity=0.05] (3.897, 5.1) -- (-2.598,1.35) -- (-3.997,2.15) -- (-3.997,3.85) -- (0.15, 6.2) -- (3.897,6.2);
  
  \node[blue] (21a) at (0,-0.25) {$\bullet$};
  \node[blue] (21b) at (1.299,0.6) {$\bullet$};
  \node[blue] (21c) at (0,1.5) {$\bullet$};
  \node[blue] (21d) at (1.299,2.35) {$\bullet$};
  
  \draw[blue] (0,-0.25) -- (1.299,0.6) -- (1.299,2.35);
  \draw[blue, -{>[scale=1.2]}] (1.299,2.35) -- (-5.196, 6.1);
  \draw[blue, -{>[scale=1.2]}] (0,-0.25) -- (-5.196, 2.75);
  \draw[fill=blue, opacity=0.05] (-5.196, 2.75) -- (0,-0.25) -- (1.299,0.6) -- (1.299,2.35) -- (-5.196, 6.1);
  
  \node[orange] (1a) at (0,-0.4) {$\bullet$};
  \node[orange] (1b) at (-1.299,0.35) {$\bullet$};
  \node[orange] (1c) at (-2.598,1.1) {$\bullet$};
  \node[orange] (1d) at (-4.1,1.98) {$\bullet$};
  
  \draw[orange] (0,-0.4) -- (-1.299,0.35) -- (-2.598,1.1) -- (-4.1,1.98);
  \draw[orange, -{>[scale=1.2]}] (0,-0.4) -- (3.897,2.15);
  \draw[orange, -{>[scale=1.2]}] (-4.1,1.98) -- (-4.1,6.1);
  \draw[fill=orange, opacity=0.05] (3.897,2.15) -- (0,-0.4) -- (-1.299,0.35) -- (-2.598,1.1) -- (-4.1,1.98) -- (-4.1,6.2) -- (3.897,6.2);
  
  \node[lightblue] (2a) at (0,-0.55) {$\bullet$};
  \node[lightblue] (2b) at (1.399,0.35) {$\bullet$};
  
  \draw[lightblue] (0,-0.55) -- (1.399,0.35);
  \draw[lightblue, -{>[scale=1.2]}] (1.399,0.35) -- (1.399,6.1);
  \draw[lightblue, -{>[scale=1.2]}] (0,-0.55) -- (-5.196,2.45);
  \draw[fill=lightblue, opacity=0.05] (-5.196,2.45) -- (0,-0.55) -- (1.399,0.35) -- (1.399,6.2) -- (-5.196, 6.2);
  
  \node[lightgrey] (ea) at (0,-0.7) {$\bullet$};
  
  \draw[lightgrey, -{>[scale=1.2]}] (0,-0.7) -- (-5.196,2.3);
  \draw[lightgrey, -{>[scale=1.2]}] (0,-0.7) -- (3.897,1.85);
  \draw[fill=lightgrey, opacity=0.1] (-5.196,2.3) -- (0,-0.7) -- (3.897,1.85) -- (3.897,6.2) -- (-5.196, 6.2);
  
  \draw (-5.196, 6.2) -- (3.897,6.2) -- (3.897,-0.8) -- (-5.196,-0.8) -- (-5.196, 6.2);
  \end{tikzpicture}
  \]
\end{example}

\acknowledgements{The authors are supported by the DFG Heisenberg grant STU 563/4-1.}










%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
