A Geometric Realization via Brick Polyhedra

The goal of this paper is to show that the _ν _ν-associahedron can be geometrically realized as the complex of bounded faces of the _ν _ν-brick polyhedron.

The following is our main result, which can be observed from Examples 1 and 2, illustrated in Fig. 8.

Theorem 5

The ν ν-associahedron is geometrically realized as the polytopal complex of bounded faces of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν). In other words, the poset of bounded faces of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν) is anti-isomorphic to the poset of interior faces of the _ν _ν-subword complex (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\cong \nu $$\end{document}≅ν-Tamari complex).

Fig. 8: Comparison of the νν-brick polyhedron and νν-associahedron for ν =ENEENν=ENEEN

Our approach to establish this result involves the following steps: Enhance the understanding of the faces of general brick polyhedra (Proposition 6).Characterize the bounded faces of the _ν _ν-brick polyhedron (Theorem 11).Analyze the poset of bounded faces of the _ν _ν-brick polyhedron (Proof of Theorem 5 in Sect. 5.4).

Faces of Brick Polyhedra

In order to prove Theorem 5, it is useful to have a better understanding of the faces of brick polyhedra in general. For this purpose, we use a notion of modified brick polyhedra.

Definition 13

(Modified Bruhat Cone \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {C}^{I,+}$$\end{document}CI,+) We denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}^I(Q,w)$$\end{document}SCI(Q,w) the set of all facets in the subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w)$$\end{document}SC(Q,w) that contain a given face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I \in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}I∈SC(Q,w):For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J\in \mathcal{S}\mathcal{C}^I(Q,w)$$\end{document}J∈SCI(Q,w), the modified root configuration \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R^I(J)$$\end{document}RI(J) is given byWe define the modified Bruhat cone \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {C}^{I,+}$$\end{document}CI,+ as

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathcal{S}\mathcal{C}^I(Q,w):=\{J \in \mathcal{S}\mathcal{C}(Q,w) : I \subseteq J\}. \end{aligned}$$\end{document}SCI(Q,w):={J∈SC(Q,w):I⊆J}.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} { R}^I(J):= \{ r(J,j) \mid j \in J \setminus I \}. \end{aligned}$$\end{document}RI(J):={r(J,j)∣j∈J\I}.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathcal {C}^{I,+} := \bigcap _{J \in \mathcal{S}\mathcal{C}^I(Q,w)} \operatorname {cone} { R}^I(J). \end{aligned}$$\end{document}CI,+:=⋂J∈SCI(Q,w)coneRI(J).

Definition 14

(Modified Brick Polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q, w)$$\end{document}BI(Q,w)) For a face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I\in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}I∈SC(Q,w) of a non-empty subword complex, the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q,w)$$\end{document}BI(Q,w) is the polyhedron

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q,w):= \text {conv}{b(J)\mid $$\end{document}BI(Q,w):=conv{b(J)∣ J facet of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w) \text { and } I \subseteq J}+\mathcal {C}^{I,+}$$\end{document}SC(Q,w)andI⊆J}+CI,+.

Example 3

For ν = ENEEN_ν=ENEEN and using the labeling shown in Fig. 9, the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_2}(Q, w)$$\end{document}BI2(Q,w) for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2={3,4,7,9}$$\end{document}I2={3,4,7,9} is the bounded pentagon in Fig. 10, while \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_3}(Q\nu , w_\nu )$$\end{document}BI3(Qν,wν), where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_3 = {1, 2, 3, 9}$$\end{document}I3={1,2,3,9}, is not a face of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν) since it consists of a brick vector and two rays extending to infinity, as illustrated by the red region in Fig. 10. For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_4 = {3, 7, 8, 9}$$\end{document}I4={3,7,8,9}, the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_4}(Q_\nu , w_\nu )$$\end{document}BI4(Qν,wν) is a slice of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν), as illustrated by the green region in Fig. 10.

Fig. 9: Grid for labeling of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q\nu , w_\nu )$$\end{document}SC(Qν,wν) for ν =ENEENν=ENEEN_

Fig. 10: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w_\nu )$$\end{document}B(Qν,wν) for ν = ENEENν=ENEEN_

Moving forward, our objective is to establish the following result.

Proposition 6

Every face F of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q, w)$$\end{document}B(Q,w) is of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q, w)$$\end{document}BI(Q,w) for some face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I \in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}I∈SC(Q,w).

This proposition states that every face of a brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q, w)$$\end{document}B(Q,w) is a modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q, w)$$\end{document}BI(Q,w); however, we remark that not every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q, w)$$\end{document}BI(Q,w) is a face of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q, w)$$\end{document}B(Q,w), as shown in Example 3. The Proposition was essentially proved in [11] using the description of faces via linear functionals, see [11, Remark 4.11] and [11, Corollary 3.24 and Proposition 4.6]. Our approach is a bit different and is based on Proposition 7, cf. [11, Proposition 4.6 and Remark 4.11].

For a face F of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w), we denote bythe vector space spanned by F, and bythe smallest affine space containing F.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ V_F:=\operatorname {span} \{ p-q \mid p,q\in F\} $$\end{document}VF:=span{p-q∣p,q∈F}

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \widetilde{V}_F:= F+V_F= \{ p+v \mid p\in F, v\in V_F\} $$\end{document}V~F:=F+VF={p+v∣p∈F,v∈VF}

It is essential to develop certain ideas before we can prove Proposition 6.

The Minimal Element and Characterization of Vertices in a Face F

First, we demonstrate that each face F of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q, w)$$\end{document}B(Q,w) has a “minimal element”. To accomplish this, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta \in V$$\end{document}η∈V be a vector such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \eta , \alpha \rangle > 0$$\end{document}⟨η,α⟩>0 for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \in \Phi ^+$$\end{document}α∈Φ+ and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \eta , \alpha \rangle < 0$$\end{document}⟨η,α⟩<0 for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \in \Phi ^-$$\end{document}α∈Φ-. This vector _η _η can be regarded as a linear functional \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta : V \rightarrow \mathbb {R}$$\end{document}η:V→R defined by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x \mapsto \langle \eta , x \rangle $$\end{document}x↦⟨η,x⟩, satisfying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta (\alpha ) \ne 0$$\end{document}η(α)≠0 for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \in \Phi $$\end{document}α∈Φ.

Lemma 2

(Minimal element of a face) For every face F of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w), there exists a unique vertex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J_{F,\min }) \in F$$\end{document}b(JF,min)∈F, corresponding to some facet \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_{F,\min }$$\end{document}JF,min, that minimizes the linear functional _η _η.

Proof

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_\eta $$\end{document}Fη be the sub-face of F that minimizes the linear functional η η. We aim to demonstrate that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F\eta $$\end{document}Fη consists of only one point. Otherwise, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F\eta $$\end{document}Fη would contain a (possibly unbounded) edge in the direction of _α _α for some \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \in \Phi $$\end{document}α∈Φ.

Let p and q be two points on this edge such that _q = p + α _q=p+α for some \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \in \Phi $$\end{document}α∈Φ. Then, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \eta , q \rangle = \langle \eta , p \rangle + \langle \eta , \alpha \rangle $$\end{document}⟨η,q⟩=⟨η,p⟩+⟨η,α⟩. Since p and q are minimizing _η _η, it follows that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \eta , \alpha \rangle = 0$$\end{document}⟨η,α⟩=0, contradicting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \eta , \alpha \rangle \ne 0$$\end{document}⟨η,α⟩≠0 for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \in \Phi $$\end{document}α∈Φ. _□ _□

Our second step is to characterize the vertices within a face F of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q, w)$$\end{document}B(Q,w). The following Observation 1 is a direct consequence of the definition of the reflection \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_\beta (\alpha ) = \alpha - 2 \frac{\langle \alpha , \beta \rangle }{\langle \beta , \beta \rangle } \beta $$\end{document}rβ(α)=α-2⟨α,β⟩⟨β,β⟩β along the hyperplane orthogonal to the root _β _β.

Observation 1

Let U be a finite-dimensional subspace of a vector space.If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha , \beta \in U$$\end{document}α,β∈U then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_\alpha (\beta )\in U $$\end{document}rα(β)∈U.If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \notin U$$\end{document}α∉U and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta \in U$$\end{document}β∈U, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_\alpha (\beta ) \not \in U $$\end{document}rα(β)∉U.

Lemma 3

(Characterization of the vertices in a face F) Let F be a face of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w), and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J\in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}J∈SC(Q,w) be a facet such that the brick vector _b(J)∈ F_b(J)∈F. Define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J^F:={j \in J:$$\end{document}JF:={j∈J: r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J,j) \in V_F}$$\end{document}(J,j)∈VF} and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I = J \setminus J^F$$\end{document}I=J\JF. For any facet \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J' \in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}J′∈SC(Q,w), we have the following equivalence:

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} I \subseteq J' \quad \text {if and only if} \quad b(J') \in \widetilde{V}_F. \end{aligned}$$\end{document}I⊆J′if and only ifb(J′)∈V~F.

Proof

_⇒ ⇒: Assume I ⊆ J'I⊆J′. Note that there exists a sequence of flips \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J = J_0 \overset{j_0}{\rightarrow }\ J_1 \overset{j_1}{\rightarrow }\ \ldots \overset{j{\ell -1}}{\rightarrow } J\ell = J'$$\end{document}J=J0→j0J1→j1…→jℓ-1Jℓ=J′ that never flips an element in I. This is due to the connectedness of the flip graph of a subword complex, especially for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{[m]\setminus I},w)$$\end{document}SC(Q[m]\I,w), where Q is of length m.

Now the following holds: r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J_k,j) \notin V_F \text { if } j\in I$$\end{document}(Jk,j)∉VFifj∈Ir\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J_k,j) \in V_F \text { if } j\in J_k \setminus I$$\end{document}(Jk,j)∈VFifj∈Jk\ITo prove this, it is enough to examine only one flip. Without loss of generality, take the first flip. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_1=J_0\setminus {j_0} \cup {j_0'}$$\end{document}J1=J0{j0}∪{j0′}. By [9, Lemma 3.3 (2)], we havefor β := β:=r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J_0,j_0)$$\end{document}(J0,j0). Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta \in V_F$$\end{document}β∈VF, Observation 1 implies properties (1) and (2) hold for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J_1,j)$$\end{document}r(J1,j). Now, note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J_1) = b(J_0) + c{0,1}$$\end{document}b(J1)=b(J0)+c0,1r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J_0,j_0)$$\end{document}(J0,j0), for some constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c{0,1}$$\end{document}c0,1. Since r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J_0,j_0) \in V_F$$\end{document}(J0,j0)∈VF, we have \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J_1) \in \widetilde{V}_F$$\end{document}b(J1)∈V~F.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} {r(J_1,j)}= \left\{ \begin{array}{lll} s_\beta (r(J_0,j)) \qquad \qquad \qquad & & \text { if}\ \text {min}(j_0,j_0')<j \le max(j_0,j_0') \\ r(J_0,j) \qquad \qquad \qquad & & \text { otherwise} \end{array}\right. \end{aligned}$$\end{document}r(J1,j)=sβ(r(J0,j))ifmin(j0,j0′)<j≤max(j0,j0′)r(J0,j)otherwise

Applying the same argument several times for the rotations in the sequence yields \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J_\ell )= b(J') \in \widetilde{V}_F$$\end{document}b(Jℓ)=b(J′)∈V~F (Fig. 11).

_⇐ _⇐: Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q = b(J') \in \widetilde{V}F$$\end{document}q=b(J′)∈V~F and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J{F, \text {min}})$$\end{document}b(JF,min) be the minimal element by Lemma 2. We will show that _J'J′ can be connected to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J{F, \text {min}}$$\end{document}JF,min by a sequence of decreasing flips \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J' = J'0 \overset{j'0}{\rightarrow }\ J'1 \overset{j'1}{\rightarrow }\ \ldots \overset{j'{\ell -1}}{\rightarrow } J'{\ell '} = J{F, \text {min}}$$\end{document}J′=J0′→j0′J1′→j1′…→jℓ-1′J′′=JF,min, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J'k, j'k) \in V_F$$\end{document}r(Jk′,jk′)∈VF for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le k < \ell '$$\end{document}1≤k<ℓ′. To demonstrate this, we provide a construction of a flip-sequence. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p{\text {min}}:= b(J{F, \text {min}})$$\end{document}pmin:=b(JF,min). By the local cone property [11, Theorem 4.4],where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a{j'} \ge 0$$\end{document}aj′≥0 for all _j' ∈ J'_j′∈J′. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta _F$$\end{document}ηF be a linear functional that is minimal at the face F. Taking the inner product with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta _F$$\end{document}ηF, we obtain:but \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle r(J', j'), \eta _F \rangle =0$$\end{document}⟨r(J′,j′),ηF⟩=0 if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J', j')\in V_F$$\end{document}r(J′,j′)∈VF and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle r(J', j'), \eta F \rangle >0$$\end{document}⟨r(J′,j′),ηF⟩>0 otherwise. So, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a{j'} = 0$$\end{document}aj′=0 if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J', j') \not \in V_F$$\end{document}r(J′,j′)∉VF. Therefore,

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} p_{\text {min}} - q= b(J_{F, \text {min}}) - b(J')= \sum _{j'\in J'} a_{j'} r(J', j') \in V_F, \end{aligned}$$\end{document}pmin-q=b(JF,min)-b(J′)=∑j′∈J′aj′r(J′,j′)∈VF,

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} 0 = \sum _{j' \in J'} a_{j'} \langle r(J', j'), \eta _F \rangle \end{aligned}$$\end{document}0=∑j′∈J′aj′⟨r(J′,j′),ηF⟩

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} b(J_{F, \text {min}}) - b(J) = \sum _{\begin{array}{c} j' \in J' \\ r(J', j') \in V_F \end{array}} a_{j'} r(J', j'). \end{aligned}$$\end{document}b(JF,min)-b(J)=∑j′∈J′r(J′,j′)∈VFaj′r(J′,j′).

_Fig. 11: Normal vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta F$$\end{document}ηF

Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_{F, \text {min}}$$\end{document}JF,min minimizes the linear functional _η _η, the inner product with _η η satisfiesIf all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J', j') \in R(J) \cap V_F$$\end{document}r(J′,j′)∈R(J)∩VF were positive roots, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \eta , b(J{F,\text {min}}) - b(J) \rangle > 0$$\end{document}⟨η,b(JF,min)-b(J)⟩>0 would hold. Thus, at least one _r(J', j')_r(J′,j′) must be a negative root, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J', j_0') \in \Phi ^-\cap V_F$$\end{document}r(J′,j0′)∈Φ-∩VF. By [11, Lema 3.3 (2)] \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j_0' \in J'$$\end{document}j0′∈J′ is decreasingly flippable. Flipping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j_0'$$\end{document}j0′ in J, we obtain a new facet \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_1'$$\end{document}J1′ such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J_1')\in \widetilde{V}F$$\end{document}b(J1′)∈V~F, because \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(J_1')=b(J_0')+c_0r(J_0',j_0')$$\end{document}b(J1′)=b(J0′)+c0r(J0′,j0′) for some positive constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c_0$$\end{document}c0. If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_1'=J{F,\text {min}}$$\end{document}J1′=JF,min then we are done. If not, we can repeat the process and find a sequence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J' \overset{j'_0}{\rightarrow }\ J'1 \overset{j'1}{\rightarrow }\ \ldots \overset{j'{\ell '-1}}{\rightarrow } J{F, \text {min}}$$\end{document}J′→j0′J1′→j1′…→jℓ′-1′JF,min such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J'_k, j'_k) \in V_F$$\end{document}r(Jk′,jk′)∈VF for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le k < \ell '$$\end{document}1≤k<ℓ′.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \langle \eta , b(J_{F, \text {min}}) - b(J) \rangle < 0. \end{aligned}$$\end{document}⟨η,b(JF,min)-b(J)⟩<0.

The similar statement holds for the facet J. Thus, going through \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_{F, \text {min}}$$\end{document}JF,min, we can find a sequence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J = J_1 \overset{j_0}{\rightarrow }\ J_1 \overset{j_1}{\rightarrow }\ \ldots \overset{j_{\ell -1}}{\rightarrow } J_\ell = J'$$\end{document}J=J1→j0J1→j1…→jℓ-1Jℓ=J′ such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(J_k, j_k) \in V_F$$\end{document}r(Jk,jk)∈VF for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le k < \ell $$\end{document}1≤k<ℓ. By properties (1) and (2), we are never flipping an element in I such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j_k \notin I$$\end{document}jk∉I. Therefore, _I ⊆ J'_I⊆J′ holds. _□ _□

Proof of Proposition 6

Now are ready to prove Proposition 6. It is a direct consequence of the following more explicit result, cf. [11, Proposition 4.6 and Remark 4.11].

Proposition 7

Consider a face F of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w), let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J \in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}J∈SC(Q,w) be a facet such that the brick vector _b(J)∈ F_b(J)∈F and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J^F:={j \in J:$$\end{document}JF:={j∈J: r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(J,j) \in V_F}$$\end{document}(J,j)∈VF}. Then, the following hold: for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I= J \setminus J^F$$\end{document}I=J\JF, we have \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}^I(Q,w)$$\end{document}F=BI(Q,w) andfor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J' \in \mathcal{S}\mathcal{C}(Q,w)$$\end{document}J′∈SC(Q,w) a facet, we have _I ⊆ J'_I⊆J′ if and only if _b(J') ∈ F_b(J′)∈F.

Proof

By Lemma 3, _I ⊆ J'_I⊆J′ if and only if _b(J')∈ F_b(J′)∈F, so (2) follows. The vertices of F are the brick vectors _b(J')_b(J′) for _I ⊆ J'_I⊆J′, and the local cone at _b(J')_b(J′) inside F is the intersection of the local cone of _b(J')_b(J′) in the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w) with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{V}_F$$\end{document}V~F. This is precisely the local cone at _b(J')_b(J′) in the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q,w)$$\end{document}BI(Q,w). Thus, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}^I(Q,w)$$\end{document}F=BI(Q,w). _□ _□

Some Faces of νν-brick Polyhedra

In this subsection, we will outline some conditions under which the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}BI(Qν,wν) is a face of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν). The following notation will be used throughout our discussion.

Definition 15

For a _ν _ν-tree T we denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta _t:=r(T,t) = e_i - e_j$$\end{document}βt:=r(T,t)=ei-ej the root associated to a node _t∈ T_t∈T. We label t by ij for convenience and define the coneGiven a subset of nodes _M ⊆ T_M⊆T we denote the _ν _ν-tree with M marked by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_M$$\end{document}TM, and defineAn example is shown in Fig. 12.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T):= \{ x \in V \mid \langle x, \beta _t \rangle > 0 \text { for all } t \in T \}.$$\end{document}C(T):={x∈V∣⟨x,βt⟩>0for allt∈T}.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_M):= \{x \in V \mid \langle x, \beta _t \rangle > 0 \text { for all } t \in T \setminus M \text { and } \langle x, \beta _t \rangle = 0 \text { for all } t \in M \}.$$\end{document}C(TM):={x∈V∣⟨x,βt⟩>0for allt∈T\Mand⟨x,βt⟩=0for allt∈M}.

Fig. 12: Left: νν-tree T, Right: νν-tree with marked points \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_M$$\end{document}TM

Remark 2

The result [18, Theorem 4.17] asserts that all the facets (pipe dreams) of the subword complex associated with the _ν _ν-Tamari lattice are acyclic. This condition is equivalent to the system of inequalities having a solution. Indeed, the cone C(T) is non-empty if and only if the contact graph of the pipe dream P(T) is acyclic. This acyclic property holds for all _ν _ν-trees.

Lemma 4

Let _I=T ∖ A_I=T\A, where T is a _ν _ν-tree and _A⊆ T_A⊆T a subset of ascents, and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta _t:=r(T,t)$$\end{document}βt:=r(T,t) for _t ∈ T_t∈T. There exists a linear functional f such that

1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} f(\beta _a)=0\text { for }a \in A\text { and }f(\beta _t)>0\text { for }t \in T \setminus A. \end{aligned}$$\end{document}f(βa)=0fora∈Aandf(βt)>0fort∈T\A.

The proof idea of Lemma 4 relies on Definition 15, by showing that the cone \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_A)\ne \emptyset $$\end{document}C(TA)≠∅, and is exemplified in Example 4.

Example 4

Consider _ν = EEN_ν=EEN. All three _ν _ν-trees T, _T'_T′, _T''_T′′ and the defining inequalities of their corresponding cones \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_1),C(T_2),C(T_3)$$\end{document}C(T1),C(T2),C(T3) are shown in Fig. 13. Note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_1),C(T_2)$$\end{document}C(T1),C(T2) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_3)$$\end{document}C(T3) are non-empty.

Figure 14 (Left) shows a marked _ν _ν-tree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_A$$\end{document}TA together with the defining equalities and inequalities of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_A)$$\end{document}C(TA). Here \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A={a}$$\end{document}A={a} consists of the unique ascent _a∈ T_a∈T. The figure also shows the marked _ν ν-tree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T'{A'}$$\end{document}T′′ where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T\smallsetminus {a}=T'\smallsetminus {a'}$$\end{document}T{a}=T′{a′}. Our strategy to prove that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_A)\ne \emptyset $$\end{document}C(TA)≠∅ is to pick two points _p∈ C(T)_p∈C(T) and _p'∈ C(T')_p′∈C(T′), and show that there is a point q in the line segment connecting them such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q\in C(T_A)$$\end{document}q∈C(TA).

Fig. 13: All three νν-trees T, T'T′, T''T′′ for ν = EENν=EEN, and defining inequalities for C(T), C(T')C(T′), C(T'')C(T′′)

Fig. 14: Marked νν-trees \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_A$$\end{document}TA and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T'{A'}$$\end{document}T′′ for ν =EENν=EEN_

Proof of Lemma 4

We proceed by induction on the number of marked ascents _k:=|A|_k:=|A|. The statement holds for _k = 0_k=0 by [18, Theorem 4.17], see Remark 2. Suppose _k \ge 1_k≥1 and that the statement holds for _k - 1_k-1. Let _I=T∖ A_I=T\A, where T is a _ν _ν-tree and _A⊆ T_A⊆T is a subset of ascents with |A|=k|A|=k, and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta _t=$$\end{document}βt= _r_r (T,t)(T,t), _t∈ T_t∈T as above.

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{a}\in A$$\end{document}a¯∈A be the northeast-most node in A (i.e. no other node in A is located northeast of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{a}$$\end{document}a¯), and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T'{=}T\setminus {\bar{a}}\cup {\bar{a}'}$$\end{document}T′=T{a¯}∪{a¯′} be the _ν _ν-tree obtained from T by rotating \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{a}$$\end{document}a¯.

Fig. 15: Structure of the νν-trees T and T'T′

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_1,i_2,i_3,i_4$$\end{document}i1,i2,i3,i4 be the pipes passing through the nodes of T involved in the rotation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{a}\in T$$\end{document}a¯∈T, as illustrated in Fig. 15. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{A}=A\setminus {\bar{a}}$$\end{document}A¯=A{a¯}, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{A} \subseteq T$$\end{document}A¯⊆T is a subset of ascents of T with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\bar{A}|=k-1$$\end{document}|A¯|=k-1 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{A}\subseteq T'$$\end{document}A¯⊆T′ is also a subset of ascents of T'T′. By induction hypothesis, the inequalities and equalities defining \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T{\bar{A}})$$\end{document}C(TA¯) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T'{\bar{A}})$$\end{document}C(TA¯′) have solutions. LetNote that all defining inequalities and equalities defining \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_{\bar{A}})$$\end{document}C(TA¯) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T'{\bar{A}})$$\end{document}C(TA¯′) coincide, except for three:On the other hand, the defining inequalities and equalities for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T{A})$$\end{document}C(TA) are all other defining inequalities for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_{\bar{A}})$$\end{document}C(TA¯) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T'{\bar{A}})$$\end{document}C(TA¯′) together withLet \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{D}$$\end{document}D¯ be defined by the other inequalities and equalities together withNote that we do not put any condition between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x{i_2}$$\end{document}xi2 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_{i_3}$$\end{document}xi3 in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{D}$$\end{document}D¯, whileWe want to show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ C(T_{A})\ne \emptyset $$\end{document}C(TA)≠∅. For this, note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T_{\bar{A}}) \subseteq \bar{D}$$\end{document}C(TA¯)⊆D¯ and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T'_{\bar{A}}) \subseteq \bar{D}$$\end{document}C(TA¯′)⊆D¯. ThereforeSinceThen, there must be some r∈ [0,1]r∈[0,1] such thatSince all other defining inequalities of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T{A})$$\end{document}C(TA) are satisfied for q(r), thenThus, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(T{A})$$\end{document}C(TA) has a solution as wanted. _□ _□

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} p=(p_1,...,p_\ell ) \in C(T_{\bar{A}}), \\ p'=(p'_1,...,p'_{\ell '}) \in C(T'_{\bar{A}}). \end{aligned}$$\end{document}p=(p1,...,pℓ)∈C(TA¯),p′=(p1′,...,p′′)∈C(TA¯′).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} x_{i_1}>x_{i_2}>x_{i_3}>x_{i_4} \text { in } C(T_{\bar{A}}), \\ x_{i_1}>x_{i_3}>x_{i_2}>x_{i_4} \text { in } C(T'_{\bar{A}}). \end{aligned}$$\end{document}xi1>xi2>xi3>xi4inC(TA¯),xi1>xi3>xi2>xi4inC(TA¯′).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} x_{i_1}>x_{i_2}=x_{i_3}>x_{i_4} \text { in } C(T_{\bar{A}}). \end{aligned}$$\end{document}xi1>xi2=xi3>xi4inC(TA¯).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} x_{i_1}>x_{i_2}\text {, }x_{i_3}>x_{i_4}. \end{aligned}$$\end{document}xi1>xi2,xi3>xi4.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} x_{i_2}>x_{i_3} \text { in } C(T_{\bar{A}}), \\ x_{i_3}>x_{i_2} \text { in } C(T'_{\bar{A}}), \\ x_{i_2}=x_{i_3} \text { in } C(T_{A}). \end{aligned}$$\end{document}xi2>xi3inC(TA¯),xi3>xi2inC(TA¯′),xi2=xi3inC(TA).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q(t)=(1-t)p+tp' \in \bar{D} \text { for all } t \in [0,1]. \end{aligned}$$\end{document}q(t)=(1-t)p+tp′∈D¯for allt∈[0,1].

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q_{i_2}(0)=p_{i_2}>p_{i_3}=q_{i_3}(0) \text { and } q_{i_2}(1)=p'_{i_2}<p'_{i_3}=q_{i_3}(1) . \end{aligned}$$\end{document}qi2(0)=pi2>pi3=qi3(0)andqi2(1)=p2′<p3′=qi3(1).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q_{i_2}(r)=q_{i_3}(r). \end{aligned}$$\end{document}qi2(r)=qi3(r).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q(r)\in C(T_{A}). \end{aligned}$$\end{document}q(r)∈C(TA).

Remark 3

Note that Lemma 4 is not necessarily true if _ A ⊆ T _A⊆T is not a subset of ascents, as demonstrated in Example 5.

Example 5

Let us continue Example 3 and consider the marked ν ν-trees \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T{M_2}$$\end{document}TM2, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T{M_3}$$\end{document}TM3, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T'_{M_4}$$\end{document}T4′ as illustrated in Fig. 16 and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2=T \setminus M_2$$\end{document}I2=T\M2, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_3=T \setminus M_3$$\end{document}I3=T\M3, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_4=T' \setminus M_4$$\end{document}I4=T′\M4.

For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_{M_2}$$\end{document}TM2, we obtain the conditions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_1> x_2 = x_3 = x_4> x_5 > x_6$$\end{document}x1>x2=x3=x4>x5>x6, which has a solution, and the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_2}(Q_\nu , w_\nu )$$\end{document}BI2(Qν,wν) is a face. For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_{M_3}$$\end{document}TM3, we obtain the conditions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_1> x_2> x_3> x_4 = x_5 > x_6$$\end{document}x1>x2>x3>x4=x5>x6 with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_3 = x_5$$\end{document}x3=x5, which has no solution, and the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_3}(Q_\nu , w_\nu )$$\end{document}BI3(Qν,wν) is not a face. For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T'{M_4}$$\end{document}T4′, we obtain the conditions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_1 > x_3 = x_4 = x_5$$\end{document}x1>x3=x4=x5 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_3> x_2> x_5 > x_6$$\end{document}x3>x2>x5>x6, which has no solution, and the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_4}(Q\nu , w_\nu )$$\end{document}BI4(Qν,wν) is not a face.

Fig. 16: Marked νν-trees for ν =ENEENν=ENEEN

Proposition 8

Let _I=T ∖ A_I=T\A, where T is a _ν ν-tree and A⊆ T_A⊆T a subset of ascents. Then the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q\nu , w\nu )$$\end{document}BI(Qν,wν) is a face of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν).

Proof

Take f as in Lemma 4 and let F be the face of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_\nu , w_\nu )$$\end{document}B(Qν,wν) minimizing f. Since for every ν ν-tree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{T}$$\end{document}T~ we haveThen \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(b(\tilde{T})) \ge f(b(T))$$\end{document}f(b(T~))≥f(b(T)), with equality satisfied when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(\tilde{T})-b(T) \in V_F$$\end{document}b(T~)-b(T)∈VF, the vector space spanned by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r(T,a)\mid a \in A}$$\end{document}{r(T,a)∣a∈A}. In particular b(T)∈ F_b(T)∈F and by Lemma 7 (2)Now \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}(Q\nu , w\nu )\cap \widetilde{V_F}$$\end{document}F=B(Qν,wν)∩VF~, and the local cone at point \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(\tilde{T})$$\end{document}b(T~) inside F is the intersection of the local cone of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(\tilde{T})$$\end{document}b(T~) in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w_\nu )$$\end{document}B(Qν,wν) with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{V_F}$$\end{document}VF~. This is equal to the local cone of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(\tilde{T})$$\end{document}b(T~) in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}BI(Qν,wν). Therefore, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}F=BI(Qν,wν). _□ _□

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} b(\tilde{T})-b(T)=\sum _{t\in T}c_t r(T,t) \text { for some } c_t\ge 0. \end{aligned}$$\end{document}b(T~)-b(T)=∑t∈Tctr(T,t)for somect≥0.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} b(\tilde{T}) \in F \Longleftrightarrow T\setminus A=I \subseteq \tilde{T}. \end{aligned}$$\end{document}b(T~)∈F⟺T\A=I⊆T~.

Bounded Faces of νν-brick Polyhedra

The goal of this section is to show that the faces in Proposition 8 are exactly the bounded faces of the _ν _ν-brick polyhedron (Theorem 11).

The Spherical and Root Independent Property

We denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_{\nu ,I}$$\end{document}Qν,I the word obtained from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_\nu $$\end{document}Qν by deleting the letters with positions in I, and consider the corresponding subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu ,I},w_\nu )$$\end{document}SC(Qν,I,wν). The purpose of this section is to show that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu ,I},w_\nu )$$\end{document}SC(Qν,I,wν) is spherical and root independent when I=T∖ A_I=T\A for a ν ν-tree T and A⊆ T_A⊆T a subset of ascents. As a consequence, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{\nu ,I},w\nu )$$\end{document}SC(Qν,I,wν) is realized as the polar of the brick polytope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q{\nu ,I},w\nu )$$\end{document}B(Qν,I,wν), which is combinatorially isomorphic to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_{\nu },w_\nu )$$\end{document}BI(Qν,wν). Before doing this, we need some preliminaries.

Theorem 9

([9]) If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w_\circ )$$\end{document}SC(Q,w∘) is root independent, then it is realized by the polar of the brick polytope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q, w_\circ )$$\end{document}B(Q,w∘).

Lemma 5

([5, 20]) Every spherical subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w)$$\end{document}SC(Q,w) is isomorphic to a (spherical) subword complex of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(\tilde{Q},w_\circ )$$\end{document}SC(Q~,w∘).

Remark 4

(Completing) For any spherical subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w)$$\end{document}SC(Q,w), there exists a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${w'}$$\end{document}w′, such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w{w'}! =! w_\circ $$\end{document}ww′=w∘ with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell (w)+\ell (w')!=!\ell (w_\circ )$$\end{document}ℓ(w)+ℓ(w′)=ℓ(w∘), by completing w to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_\circ $$\end{document}w∘. Defining \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${Q'}=Q {w'}$$\end{document}Q′=Qw′, the subword complexes \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}({Q},w)$$\end{document}SC(Q,w) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}({Q'},w_\circ )$$\end{document}SC(Q′,w∘) are isomorphic and the brick polytope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w) is just a translation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q',w_\circ )$$\end{document}B(Q′,w∘).

The following result is assumed/mentioned in [9] but not explicitly written down. We include it here with proof for completeness.

Corollary 3

([9]) Every spherical, root independent subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w)$$\end{document}SC(Q,w), where w is not necessary equal to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_\circ $$\end{document}w∘, is realized by the polar of the brick polytope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q,w)$$\end{document}B(Q,w).

Proof

By Lemma 5, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w) \cong \mathcal{S}\mathcal{C}(Q',w_\circ )$$\end{document}SC(Q,w)≅SC(Q′,w∘) by completing, as in Remark 4 the facets and root configurations do not change, so \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}({Q'},w_\circ )$$\end{document}SC(Q′,w∘) is root independent and we can apply Theorem 9. Moreover the brick polytope of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q',w_\circ )$$\end{document}SC(Q′,w∘) is a translation of the brick polytope of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q,w)$$\end{document}SC(Q,w), so the Corollary holds. _□ _□

Our next goal is to prove the following proposition.

Proposition 10

Let _I=T ∖ A_I=T\A, where T is a _ν ν-tree and A⊆ T_A⊆T a subset of ascents, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{\nu ,I},w\nu )$$\end{document}SC(Qν,I,wν) is a spherical and root independent subword complex.

The proof follows in two steps. Lemma 6 shows the spherical property and Lemma 7 shows root independence.

Lemma 6

(Spherical) For an interior face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I\in \mathcal{S}\mathcal{C}(Q_\nu ,w_\nu )$$\end{document}I∈SC(Qν,wν), the subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu , I},w_\nu )$$\end{document}SC(Qν,I,wν) is realizable as the boundary of a polytope, hence it is spherical.

Proof

If I is an interior face then the set of faces \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${J \in \mathcal{S}\mathcal{C}(Q_\nu ,w_\nu ): I \subseteq J}$$\end{document}{J∈SC(Qν,wν):I⊆J}, ordered by reverse containment is the face poset of the face of the ν ν-associahedron corresponding to I. But the reverse containment poset on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${J \in \mathcal{S}\mathcal{C}(Q\nu ,w\nu ): I \subseteq J}$$\end{document}{J∈SC(Qν,wν):I⊆J} is isomorphic to the reverse containment poset of faces of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu , I},w_\nu )$$\end{document}SC(Qν,I,wν). And by [12, Proposition 5.16] the cells of the ν ν-associahedron are known to be products of classical associahedra, in particular they are polytopes. And \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{\nu , I},w\nu )$$\end{document}SC(Qν,I,wν) can be realized as the boundary complex of the polar of the polytope of the corresponding cell. Hence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu ,I},w_\nu )$$\end{document}SC(Qν,I,wν) is polytopal, hence spherical. _□ _□

Remark 5

Observe, a single pipe cannot have more than two turns inside the Ferrers diagram \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_\nu $$\end{document}Fν. Otherwise, there would exist at least three vertices, as shown in Fig. 17 (Left) in the _ν _ν-tree, but then the two red points would be _ν _ν-incompatible, which contradicts the definition of a _ν _ν-tree as a maximal set of _ν _ν-compatible elements.

Fig. 17: Left: A pseudoline with 3 turns exhibiting red vertices in νν-incompatible position, Right: A pseudoline with 2 turns showing all vertices in νν-compatible position

Lemma 7

(Root Independent) Let I be an interior face of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_\nu , w_\nu )$$\end{document}SC(Qν,wν), T a _ν _ν-tree and _A⊆ T_A⊆T a subset of ascents of T such that I=T ∖ A_I=T\A. Then, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${$$\end{document}{ r_r \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(T,a): a \in A}$$\end{document}(T,a):a∈A} is linearly independent.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{\nu ,I}, w\nu )$$\end{document}SC(Qν,I,wν) is root independent.

Proof

To show (1), we proceed by induction on _n=|A|_n=|A|. The statement is clear for _n=1_n=1. Suppose that _n \ge 2_n≥2 and that the statement holds for _n-1_n-1.

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_2 \in A$$\end{document}a2∈A such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(T,a_2) = e_i - e_j$$\end{document}r(T,a2)=ei-ej with the smallest possible i. Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_2 \in A$$\end{document}a2∈A is an ascent, there is a node to the North and one to the East. By Remark 5, there cannot be a node to the left of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_2$$\end{document}a2, as illustrated in Fig. 18. Furthermore, since i is chosen to be minimal, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_2$$\end{document}a2 is unique. Additionally, there can be no vertex on the line segment between the vertices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_2$$\end{document}a2 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_3$$\end{document}a3, following the same argument.

Fig. 18: No node in gray area

Now, suppose there exists a linear combination such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum {a\in A} c_a r(T,a)=0$$\end{document}∑a∈Acar(T,a)=0. Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r(T,a_2)=e_i-e_j$$\end{document}r(T,a2)=ei-ej with i being minimal, there is no summand of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_k-e_i$$\end{document}ek-ei, hence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c{a_2}=0$$\end{document}ca2=0. Therefore \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum c_a r(T,a)$$\end{document}∑car(T,a) is a sum of n-1_n-1 summands and by induction hypothesis, we obtain \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c{a}=0$$\end{document}ca=0 for all _a ∈ A_a∈A. So (1) follows.

To prove (2) it is enough to find a facet of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu , I}, w_\nu )$$\end{document}SC(Qν,I,wν) whose root configuration is linearly independent. Taking the facet \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \subseteq \mathcal{S}\mathcal{C}(Q_{\nu ,I}, w_\nu )$$\end{document}A⊆SC(Qν,I,wν) and applying (1) concludes (2). _□ _□

Corollary 4

Let I=T ∖ A_I=T\A, where T is a ν ν-tree and A⊆ T_A⊆T a subset of ascents. The subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{\nu , I}, w\nu )$$\end{document}SC(Qν,I,wν) is realized by the polar of the brick polytope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q{\nu , I}, w\nu )$$\end{document}B(Qν,I,wν). In particular \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_{\nu , I}, w_\nu )$$\end{document}B(Qν,I,wν) is a bounded polytope.

Proof

By Proposition 10, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu , I}, w_\nu )$$\end{document}SC(Qν,I,wν) is spherical and root independent. Therefore, it is realized by the polar of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_{\nu , I}, w_\nu )$$\end{document}B(Qν,I,wν) by Corollary 3. _□ _□

Characterization of Bounded Faces

We are now ready to characterize the bounded faces of the _ν _ν-brick polyhedron.

Corollary 5

Let T a ν ν-tree, A⊆ T_A⊆T be a subset of ascents, and I=T ∖ A_I=T\A be the corresponding interior face of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q{\nu }, w\nu )$$\end{document}SC(Qν,wν). Then, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q{\nu }, w\nu )$$\end{document}BI(Qν,wν) is a bounded face of the ν ν-brick polyhedron. Moreover,and its face poset is the reverse containment poset on the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${J \in \mathcal{S}\mathcal{C}(Q\nu ,w\nu ): I \subseteq J}$$\end{document}{J∈SC(Qν,wν):I⊆J}.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathcal {B}^I(Q_{\nu }, w_\nu ) = \text {conv} \{ b(J)\mid I \subseteq J \text { a facet of }\mathcal{S}\mathcal{C}(Q_{\nu }, w_\nu )\} \end{aligned}$$\end{document}BI(Qν,wν)=conv{b(J)∣I⊆Ja facet ofSC(Qν,wν)}

Proof

By [11, Remark 4.11] the brick polytope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_{\nu , I}, w_\nu )$$\end{document}B(Qν,I,wν) and the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_{\nu }, w_\nu )$$\end{document}BI(Qν,wν) share the following properties: Their vertices are in correspondence Their edge directions are the same, although they may have different lengths (roots in the root configuration and modified root configuration are the same).Their local cones at the vertices are the same.In particular, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_{\nu , I}, w_\nu )$$\end{document}B(Qν,I,wν) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_{\nu }, w_\nu )$$\end{document}BI(Qν,wν) are combinatorially isomorphic, and in particular bounded (Corollary 4). Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q_{\nu , I}, w_\nu )$$\end{document}SC(Qν,I,wν) is realized by the polar of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_{\nu , I}, w_\nu )$$\end{document}B(Qν,I,wν) by Corollary 4, transforming the facets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J \in \mathcal{S}\mathcal{C}(Q_{\nu , I}, w_\nu )$$\end{document}J∈SC(Qν,I,wν) to facets \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I \cup J \in \mathcal{S}\mathcal{C}^I(Q_{\nu }, w_\nu )$$\end{document}I∪J∈SCI(Qν,wν) we obtain:Furthermore, since the face poset of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_{\nu ,I}, w_\nu )$$\end{document}B(Qν,I,wν) is the reverse containing poset of faces \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J\in \mathcal{S}\mathcal{C}(Q_{\nu , I}, w_\nu )$$\end{document}J∈SC(Qν,I,wν), then adding I to each face we obtain that the face poset of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_{\nu }, w_\nu )$$\end{document}BI(Qν,wν) is the reverse containment poset on the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${J' \in \mathcal{S}\mathcal{C}(Q_\nu , w_\nu ) \mid I \subseteq J'}$$\end{document}{J′∈SC(Qν,wν)∣I⊆J′} as desired. _□ _□

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathcal {B}^I(Q_{\nu }, w_\nu ) = \text {conv} \{b(J) \mid I \subseteq J \text { a facet of }\mathcal{S}\mathcal{C}(Q_\nu ,w_\nu )\}. \end{aligned}$$\end{document}BI(Qν,wν)=conv{b(J)∣I⊆Ja facet ofSC(Qν,wν)}.

Lemma 8

(Unique representation of bounded faces) Let T be a ν ν-tree, A⊆ T_A⊆T a subset of ascents, I=T ∖ A_I=T\A and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}^I(Q\nu , w\nu )$$\end{document}F=BI(Qν,wν) be the corresponding bounded face of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν). Then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T=J{F,\text {min}}$$\end{document}T=JF,min and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A=J^F{F,\text {min}}$$\end{document}A=JF,minF.If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}^{I'}(Q_\nu , w_\nu )$$\end{document}F=B′(Qν,wν) for _I'=T' ∖ A'_I′=T′\A′ where _T'_T′ is a _ν _ν-tree and _A'⊆ T'_A′⊆T′ a subset of ascents, then _T=T'_T=T′, _A=A'_A=A′ and _I=I'_I=I′.

Proof

Note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_{F,\text {min}}$$\end{document}JF,min is the unique facet I⊆ J_I⊆J such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j \in J \setminus I$$\end{document}j∈J\I is increasingly flippable. Since T satisfies this property, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T=J{F,\text {min}}$$\end{document}T=JF,min. Moreover, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J^F_{F,\text {min}} = J_{F,\text {min}}\setminus I = T \setminus I = A$$\end{document}JF,minF=JF,min\I=T\I=A. This proves property (1).

Property (2) follows from (1). _□ _□

Corollary 6

The bounded faces of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν) are exactly, the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}BI(Qν,wν), for _I=T∖ A_I=T\A, T a _ν _ν-tree and _A⊆ T_A⊆T a subset of ascents.

Proof

By Corollary 5, if T is a ν ν-tree, A⊆ T_A⊆T a subset of ascents, and I=T∖ A_I=T\A then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q\nu , w\nu )$$\end{document}BI(Qν,wν) is a bounded face of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν). Now let F be a bounded face of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_\nu , w_\nu )$$\end{document}B(Qν,wν), \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T=J_{F, \text {min}}$$\end{document}T=JF,min and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A=J^F_{F, \text {min}}$$\end{document}A=JF,minF. Since F is bounded then every element of A is flippable in T, otherwise F would contain an infinite ray. Moreover, every a∈ A_a∈A is increasingly flippable in T, because T is the minimal element of the face. The face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F=\mathcal {B}^I(Q\nu , w_\nu )$$\end{document}F=BI(Qν,wν) as desired. _□ _□

Question 1

Can we characterize the sets I for which the modified brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}BI(Qν,wν) is a face of the brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_\nu , w_\nu )$$\end{document}B(Qν,wν)? Corollary 6 gives an answer for bounded faces but we do not know an answer in general. See Example 3.

The following theorem summarizes the results of this section.

Theorem 11

The bounded faces of the ν ν-brick polyhedron \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q\nu , w\nu )$$\end{document}B(Qν,wν) are exactly the modified brick polyhedra \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}BI(Qν,wν), for _I=T∖ A_I=T\A, where T is a _ν ν-tree and A⊆ T_A⊆T is a subset of ascents. Moreover,and its face poset is the reverse containment poset on the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${J \in \mathcal{S}\mathcal{C}(Q\nu ,w\nu ): I \subseteq J}$$\end{document}{J∈SC(Qν,wν):I⊆J}.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathcal {B}^I(Q_{\nu }, w_\nu ) = \text {conv} \{ b(J)\mid I \subseteq J \text { a facet of }\mathcal{S}\mathcal{C}(Q_{\nu }, w_\nu )\}, \end{aligned}$$\end{document}BI(Qν,wν)=conv{b(J)∣I⊆Ja facet ofSC(Qν,wν)},

Proof

This following directly from Corollary 5 and Corollary 6. _□ _□

The Poset of Bounded Faces of νν-brick Polyhedra

It remains to show that the poset of bounded faces of the _ν _ν-brick polyhedron is anti-isomorphic to the poset of interior faces of the _ν _ν-subword complex, as stated in Theorem 5.

Proof of Theorem 5

By Corollary 6, the bounded faces of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}(Q_\nu , w_\nu )$$\end{document}B(Qν,wν) are exactly the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^I(Q_\nu , w_\nu )$$\end{document}BI(Qν,wν) for the interior face I=T∖ A_I=T\A for some ν ν-tree T and A⊆ T_A⊆T a subset of ascents. We are going to show: If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1$$\end{document}I1, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2$$\end{document}I2 are interior faces of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q\nu , w\nu )$$\end{document}SC(Qν,wν) thenCorollary 5 implies that if I is an interior face, thenTherefore, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1 \subseteq I_2$$\end{document}I1⊆I2 then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_2}(Q\nu , w\nu )\subseteq \mathcal {B}^{I_1}(Q_\nu , w_\nu )$$\end{document}BI2(Qν,wν)⊆BI1(Qν,wν). Indeed all faces of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_1}(Q_\nu , w_\nu )$$\end{document}BI1(Qν,wν) are of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{J}(Q_\nu , w_\nu )$$\end{document}BJ(Qν,wν) for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1 \subseteq J$$\end{document}I1⊆J.

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} I_1 \subseteq I_2 \Longleftrightarrow \mathcal {B}^{I_2}(Q_\nu , w_\nu )\subseteq \mathcal {B}^{I_1}(Q_\nu , w_\nu ). \end{aligned}$$\end{document}I1⊆I2⟺BI2(Qν,wν)⊆BI1(Qν,wν).

\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathcal {B}^I(Q_\nu , w_\nu ) = \text {conv}\{b(J)\mid I \subseteq J \text { facet}\}. \end{aligned}$$\end{document}BI(Qν,wν)=conv{b(J)∣I⊆Jfacet}.

We are labelling faces of the brick polyhedron by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{J}(Q_\nu , w_\nu )$$\end{document}BJ(Qν,wν), where J= T ∖ A_J=T\A, such a labelling is unique by Lemma 8. Now take a face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_2}(Q\nu , w_\nu )$$\end{document}BI2(Qν,wν) of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_1}(Q_\nu , w_\nu )$$\end{document}BI1(Qν,wν) then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {B}^{I_2}(Q_\nu , w_\nu )= \mathcal {B}^{J}(Q_\nu , w_\nu )$$\end{document}BI2(Qν,wν)=BJ(Qν,wν) for some \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1 \subseteq J$$\end{document}I1⊆J. By uniqueness, we have \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2=J$$\end{document}I2=J and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1 \subseteq I_2$$\end{document}I1⊆I2. _□ _□

Corollary 7

The complex of bounded faces of the _ν _ν-brick polyhedron is a realization of the _ν _ν-associahedron.