5 Nathan Reading Seth Sullivant Laura Colmenarejo Corey Jones Stephen Terry
Jordan GradyAlmeter Mathematics $\mathcal{P}$-graph associahedra and hypercube
graph associahedra

###### Abstract

A graph associahedron is a polytope dual to a simplicial complex whose
elements are induced connected subgraphs called tubes. Graph associahedra
generalize permutahedra, associahedra, and cyclohedra, and therefore are of
great interest to those who study Coxeter combinatorics.

For any graph, any proper vertex subset which induces a connected subgraph is
called a tube, and any set of compatible tubes is called a tubing. The set of
tubings for any graph is a simplicial complex which is dual to a simple
polytope called the graph associahedron of that graph. The graph associahedron
for a graph can be realized by repeatedly truncating certain faces of a
simplex in accordance with tubes of that graph. The graph associahedron is
further generalized by nestohedra, whose nested complexes are further
generalized by nested complexes of semilattices.

This thesis characterizes nested complexes of simplicial complexes, which we
call $\Delta$-nested complexes. From here, we can define
$\mathcal{P}$-nestohedra by truncating simple polyhedra, and in more
specificity define $\mathcal{P}$-graph associahedra, which are realized by
repeated truncation of faces of simple polyhedra in accordance with tubes of
graphs.

We then define hypercube-graph associahedra as a special case. Hypercube-graph
associahedra are defined by tubes and tubings on a graph with a matching of
dashed edges, with tubes and tubings avoiding those dashed edges. These simple
rules make hypercube-graph tubings a simple and intuitive extension of
classical graph tubings. We explore properties of $\Delta$-nested complexes
and $\mathcal{P}$-nestohedra, and use these results to explore properties of
hypercube-graph associahedra, including their facets and faces, as well as
their normal fans and Minkowski sum decompositions. We use these properties to
develop general methods of enumerating $f$-polynomials of families of
hypercube-graph associahedra. Several of these hypercube-graphs correspond to
previously-studied polyhedra, such as cubeahedra, the halohedron, the type
$A_{n}$ linear $c$-cluster associahedron, and the type $A_{n}$ linear
$c$-cluster biassociahedron. We provide enumerations for these polyhedra and
others.

The author was born and raised in Chesapeake, Virginia before getting his
Bachelor’s in Mathematics at the College of William and Mary.

###### Acknowledgements.

Thanks to friends Wyn Nelson, Eric Geiger, and Hitesh Tolani for their
friendship during my time at NCSU. Thank you to my advisor Nathan Reading for
his patience and guidance during this time. Thank you to my family for all of
their support. Thank you to my love, Richard Hess.

##  Chapter 1 INTRODUCTION

###  1.1 Hypercube graph associahedra

There exist a number of constructions related to polytopes known as
associahedra, permutohedra, and nestohedra in the literature. Figure 1.1 shows
the relationships between existing constructions, and new constructions
defined for this paper. In the traditional view of things, graph associahedra
are polytopes which generalize associahedra and related polytopes. Then,
nestohedra generalize graph associahedra, and generalized permutohedra
generalize nestohedra. In addition, semilattice-nested complexes generalize
nestohedra, with the caveat that these complexes are not polytopal. In this
figure, we have drawn thick-outlined boxes around constructions defined in
this paper. As we see, hypercube-graph associahedra are developed as a
relative to graph associahedra, using $\mathcal{P}$-graph associahedra and
$\mathcal{P}$-graph nestohedra as a common generalization. The dashed edges
indicate a generalization involving duality, as the $\mathcal{P}$-nestohedron
itself is not generalized by $\Delta$-nested complexes, but the
$\mathcal{P}$-nestohedron’s nested complex is generalized by $\Delta$-nested
complexes, and the same go for $\mathcal{P}$-graph associahedra and
$\Delta$-graph nested complexes.

Figure 1.1: A summary of classes of polyhedra and simplicial complexes in the
literature and defined in this paper.

####  1.1.1 Motivation and Background

The _associahedron_ is a simple polytope first described by Dov Tamari, and
later discovered independently by Jim Stasheff in the 1960s. The associahedron
has many applications, and Jim Stasheff presents an overview of the history
and the applications of the associahedron [10, How I ‘met’ Dov Tamari].
Associahedra can be realized as compactifications of configuration spaces. The
paper defining graph associahedra is focused on the compactification of moduli
spaces [4], where the graph associahedra of the graphs of Coxeter groups are
of particular interest for understanding Coxeter complexes.

Our motivation in defining hypercube graph associahedra was focused on the
realization of graph associahedra as generalized permutahedra. Generalized
permutahedra are polyhedra whose normal fans coarsen a type $A$ Coxeter fan,
so there is a natural connection between the type $A_{n}$ root system and an
$n$-dimensional graph associahedron. The hypercube-graph associahedron is a
generalized type $B$ permutahedron, and if the graph associahedron is
understood as a type $A$ object, then the hypercube-graph associahedron is
understood as a type $B$ analogue. We had initially aimed to provide a
generalization for all Coxeter types, but eventually realized that the
construction we have defined is better understood as a generalization from the
simplex to the broader case of any simple polyhedron, which is why we study
$\mathcal{P}$-nestohedra and $\mathcal{P}$-graph associaehdra in this thesis.

The study of graph associahedra has spurred interest in several related
polytopes. These polytopes include the _multiplihedron_ and the
_composihedron_. One other related polytope is the _cubeahedron_ defined in
[5]. In that paper, it is shown that there are three cases where the moduli
spaces of stable bordered marked surfaces are polytopal, corresponding to the
associahedron, the cyclohedron, and the halohedron. The graph cubeahedron is
introduced in order to characterize the halohedron, and it is found that the
associahedron and the halohedron can be realized as cubeahedra. In Proposition
LABEL:prop:cubeahedra-hypercube, we find that the cubeahedron is a special
case of the hypercube-graph associahedron. By studying halohedra as hypercube-
graph associahedra, we have been able to provide results enumerating the faces
of the halohedron, as in Theorem 6.1.11.

####  1.1.2 Simple Polyhedra

A _simplicial complex_ $\Delta$ is a collection of subsets, called _faces_ ,
of a base set $\mathcal{S}$ such that, if $X\subseteq\mathcal{S}$ is a face of
$\Delta$ and $Y\subset X$, then $Y\in\Delta$.

A _polyhedron_ is a collection of points in a vector space $\mathbb{R}^{n}$
defined as the intersection of a finite set of inequalities of the form
$\\{x\in\mathbb{R}^{n}|c_{i}x\leq b_{i}\\}$. A _polytope_ is a bounded
polyhedron.

A _face_ $F$ of a polyhedron $P$ is a set of points such that there exists an
inequality $cx\leq b$ such that $cx=b$ for all $x\in F$, and $cx\leq b$ for
all $x\in P$. A _facet_ of an $n$-dimensional polyhedron $P$ in
$\mathbb{R}^{n}$ is an $(n-1)$-dimensional face of $P$.

A _simple polyhedron_ is a polyhedron where every nonempty co-dimension $d$
face is contained in exactly $d$ facets. We will write the family of simple
polyhedra with the calligraphic $\mathcal{P}$.

Define the _dual simplicial complex_ of a simple polyhedron $P$ as a
simplicial complex $\Delta(P)$ on the set of facets $\mathcal{S}$ of $P$. A
set $X\subseteq\mathcal{S}$ is in $\Delta(P)$ if and only if the intersection
of all facets in $X$ is nonempty. Note that the dual simplicial complex is
isomorphic as a poset to the dual of the facial lattice of $P$, minus the
empty element.

####  1.1.3 Graph associahedra

This subsection recalls the notion of a graph associahedron, which was
introduced in [5]. After this introduction, we will use the term _classical
graph associahedron_ to specify this construction, as opposed to other
constructions introduced in this thesis.

A _graph_ is an object $G=(V,E)$ where $V$ is a set of vertices and $E$ is a
set of edges which are subsets of $V$ each containing $2$ elements. In some
contexts, this is called a simple graph; in this thesis, we assume all graphs
are simple. A _subgraph_ is a graph $(V^{\prime},E^{\prime})$ with
$V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$. The _induced subgraph_ of
a vertex subset $S\subseteq V$ of a graph $G$ is the maximal subgraph of $G$
on vertex set $S$. It consists of the graph on $S$ containing all edges in $E$
that are subsets of $S$. We notate this graph $G|_{S}$.

Given a connected graph $G$ on a vertex set $[n+1]=\\{1,\ldots,n+1\\}$, we
define a _tube_ as any proper subset $t\subset[n+1]$ such that $G|_{t}$ is a
connected induced subgraph of $G$. An example graph with several tubes is
shown in Figure 1.2.

Figure 1.2: Graph with tubes.

We can define a _tubing_ as any collection of _pairwise-compatible tubes_ ,
where two tubes $t_{1},t_{2}$ are compatible if and only if $t_{1}\subset
t_{2},t_{2}\subset t_{1}$, or $t_{1},t_{2}$ are disjoint and not _adjacent_ ;
that is, there exist no edges between any vertex in $t_{1}$ and any vertex in
$t_{2}$. Examples of compatible tubes and tubings are shown in Figure 1.3, and
two pairs of incompatible tubes are shown in Figure 1.4.

Figure 1.3: Graph with tubings. Figure 1.4: Graph with pairs of incompatible
tubes.

The collection of tubings for a graph $G$ is a simplicial complex, which we
call the _tubing complex_ of $G$. This tubing complex is dual to a simple
polytope, called the _graph associahedron_ of $G$. One realization of the
graph associahedron is obtained by repeatedly _truncating_ (i.e. slicing off)
faces of a simplex, as in [4]. In this construction, every vertex of $G$ is
associated with a facet of an $n$-dimensional simplex. Nonempty ntersections
of facets are then naturally associated with proper vertex subsets of $G$. The
graph associahedorn is then constructed by truncating faces corresponding to
tubes of $G$ in ascending order of dimension.

####  1.1.4 Well-known graph associahedra

This polyhedron is known as the graph associahedron because it is a
generalization of the _associahedron_. The associahedron is a polyhedron with
many applications in combinatorics. Its $f$-vector is related to many
enumeration problems. For example, it is associated with triangulations of an
$(n+3)$-gon. The associahedron and its normal fan are heavily tied to type $A$
Coxeter combinatorics. The $n$-dimensional associahedron can be realized as
the graph-associahedron of a path graph on $n+1$ vertices. The _permutahedron_
, also known as the type $A_{n}$ permutahedron, is the convex hull of the
orbit of a generic point under action by the symmetry group of a simplex. The
permutahedron in $n$ dimensions can be realized as the graph associahedron of
a complete graph on $n+1$ vertices.

The _cyclohedron_ is another well-known graph associahedron. It can be
realized as the graph-associahedron of a cycle graph on $n+1$ vertices. It is
associated with symmetric triangulations of a $(2n+2)$-gon. It is also
associated with type $B$ Coxeter combinatorics.

####  1.1.5 Hypercube-Graph Associahedra

In this thesis, we define _$\mathcal{P}$ -nestohedra_ and _$\mathcal{P}$
-graph associahedra_ in Chapter 2, and characterize their normal fans in
Chapter 3. We realize $\mathcal{P}$-graph associahedra by repeated truncation
of simple polyhedra in a manner analogous to the realization of graph
associahedra by repeated truncation of a simplex. However, we are specifically
interested in the special case where this simple polyhedron is a hypercube.
Hypercube-graph associahedra are described in detail in Chapter 4 of this
thesis, using results from prior chapters to define them as
$\mathcal{P}$-graph associahedra. In this introduction, we describe hypercube-
graph associahedra without proofs or justifications.

A _hypercube-graph_ is a graph on vertex set
$\pm[n]=\\{-n,\ldots,-1,1,\ldots,n\\}$, with dashed edges running between
vertex pairs $\\{i,-i\\}$ for each $i\in[n]$. Figure 1.5 shows a hypercube
graph.

Figure 1.5: Example hypercube-graph on $\pm[3]$.

A _hypercube-graph tube_ is a vertex subset $t\subset\pm[n]$ such that $t$
induces a connected subgraph which contains no dashed edges, as illustrated in
Figure 1.6. A _hypercube-graph tubing_ is a collection of hypercube-graph
tubes which satisfy the usual pairwise tube compatibility rules, but adds the
condition that there may not be dashed edges between hypercube-graph tubes.
Figure 1.7 shows a pair of tubings, contrasted with several pairs of tubes
which fail for various reasons–adjacency, intersection, or dashed edges
between tubes.

Figure 1.6: Tubes of a hypercube-graph. Figure 1.7: Tubings of a hypercube-
graph versus incompatible pairs of incompatible tubes

Hypercube-graph tubings form a simplicial complex, and this simplicial complex
is dual to a simple polytope, called the _hypercube-graph associahedron_ of
that hypercube-graph. The hypercube-graph associahedron can be constructed for
a hypercube-graph $G$ by associating each pair of graph vertices $\\{i,-i\\}$
with a pair of opposing facets of a hypercube. This means that we can
associate hypercube-graph tubes of $G$ with faces of the hypercube. A
hypercube-graph associahedron of $G$ is constructed by repeatedly truncating
faces of a hypercube associated with hypercube-graph tubes of $G$ in ascending
order by dimension. Figure 1.8 shows the hypercube-graph associahedron of the
graph in Figure 1.5.

Figure 1.8: Truncation of a hypercube to create a hypercube-graph
associahedron

###  1.2 Gallery of hypercube-graph associahedra

Many special cases of hypercube-graphs are studied in Chapter 6. Here, we
provide an incomplete list of hypercube-graph associahedra studied in this
thesis.

The maximal hypercube-graph contains all possible edges. Its hypercube-graph
associahedron is shown in Figure 1.9, and when defined with symmetric
truncations, is a type $B_{3}$ permutahedron.

Figure 1.9: Type $B_{3}$ permutahedron as a hypercube-graph associahedron.
Figure 1.10: Type $A_{3}$ permutahedron as a hypercube-graph associahedron.
Figure 1.11: Type $A_{3}$ associahedron as a hypercube-graph associahedron.
Figure 1.12: Type $A_{3}$ linear biassociahedron as a hypercube-graph
associahedron. Figure 1.13: $3$-dimensional halohedron.

Figure 1.10 depicts the hypercube-graph associahedron of a hypercube-graph
consisting of a complete graph on positive vertices and a complete graph on
negative vertices. As proven in Proposition 6.1.20, this hypercube-graph
associahedron is isomorphic to a type $A_{n}$ permutahedron.

Figure 1.11 shows the hypercube-graph associahedron of a hypercube-graph
consisting of a path on positive vertices. This polyhedron has been studied
before as a path cubeahedron in [5], where it is proven to be isomorphic to an
associahedron. We further prove in Proposition 6.1.7 that it is normal to the
linear $c$-cluster fan of type $A_{n}$.

Figure 1.12 shows the hypercube-graph associahedron of a hypercube-graph
consisting of a pair of paths on positive and negative vertices. We see that
it is similar to the hypercube-graph associahedron shown in Figure 1.11, but
with symmetric truncations made.

Figure 1.13 shows the halohedron as the hypercube-graph associahedron of a
hypercube graph consisting of a cycle on positive vertices. Note that the
cycle on 3 vertices is equal to the complete graph on 3 vertices, so this
polyhedron bears resemblance to the stellahedron in 3 dimensions, but the
cyclic pattern becomes apparent in higher dimensions. The halohedron was
described as a cubeahedron in [5], and an enumeration of its vertices or
$f$-vectors was unknown. Theorem 6.1.11 provides an enumeration of the faces
of the halohedron.

###  1.3 The relationship between hypercube-graph associahedra and Coxeter
combinatorics

The symmetry group of the $n$-dimensional simplex is called the _type $A_{n}$
Coxeter group_, and the hyperplane arrangement of reflections in this group
creates a fan which we can call the type $A_{n}$ Coxeter fan. Polyhedra whose
normal fans coarsen this fan are called _generalized permutahedra_ [13].

Notably, graph associahedra are generalized permutohedra. In particular, two
important type $A_{n}$ polyhedra can be realized as graph associahedra: the
type $A_{n}$ permutohedron, and the type $A_{n}$ associahedron. Both are more
commonly referred to as simply the permutohedron or the associahedron,
respectively, but permutahedra and associahedra exist for other root systems.

The initial goal of this project was to generalize graph associahedra for any
Coxeter type, or any root system. We do find that hypercube graph
associahedra, realized as in Definition 4.3.1, have normal fans which coarsen
the type $B_{n}$ Coxeter fan, which is generated by the symmetry group of a
hypercube. We also find that the type $B_{n}$ permutohedron can be realized as
a hypercube-graph associahedron. We have not been able, however, to find a
type $B_{n}$ associahedron realized as a hypercube graph associahedron, and
conjecture in Conjecture 6.1.38 that the type $B_{n}$ associahedron cannot be
realized as a hypercube-graph associahedron for dimensions $\geq 4$.

We note that cones in any fan can be ordered by a linear functional to define
a _poset of regions._ When that fan is a Coxeter fan of a finite Coxeter group
of type $W$, that poset of regions is isomorphic to the Coxeter weak order of
type $W$. When one fan $F$ coarsens a Coxeter fan of type $W$, that fan
induces a map from the Coxeter weak order of type $W$ to the poset of regions
of $F$. These maps prove interesting, as in the work of [2] in the classical
graph associahedron case, and we believe that this is an interesting field of
study for future research in the hypercube-graph associahedron case.

###  1.4 Other results

In this paper, we explore several other hypercube-graphs. For instance, we
conjecture that the Pell Graph, defined in Subsection 6.1.5, has a poset of
maximal tubings isomorphic to the lattice of sashes defined in [9].
Furthermore, in our research we have found families of hypercube-graph
associahedra which are apparently not isomorphic to known polyhedra, but which
present interesting symmetries or have interesting $f$-polynomials. This
includes the twisted cycle and twisted path graphs defined in Subsection
6.1.3, the families of double cubeahedra defined in Subsection 6.1.2, and the
near-double path hypercube graph associahedron defined in Subsection 6.1.6. We
also define a complex of subtrees in 2.4 which can be realized as the
$\Delta$-graph nested complex of a line graph and its graphic matroid.

##  Chapter 2 $\mathcal{P}$-graph associahedra

Semilattice-nested complexes, classical nestohedra, and classical graph
associahedra were introduced for in [7], [13], and [4], and there have been
multiple related polyhedra and generalizations defined since. This chapter
defines three new concepts. Section 2.1 defines _$\Delta$ -nested complexes_,
the special case for semilattice-nested complexes when the underlying
semilattice is a simplicial complex. Section 2.2 defines _graph nested
complexes_ , generalizing work on graph associahedra for $\Delta$-nested
complexes. Finally, Section 2.3 defines _$\mathcal{P}$ -nestohedra_, simple
polyhedra which are dual to certain polyhedral $\Delta$-nested complexes and
which are obtained by repeated truncation of polyhedral faces, as well as
$\mathcal{P}$-graph associahedra, a special case.

###  2.1 Nested complexes of simplicial complexes

This section summarizes some basic results on the nested complexes of
simplicial complexes. Nested complexes are defined for semilattices in [7].
The posets defined by simplicial complexes are semilattices, and so we can use
the semilattice definition of nested complexes to characterize building sets
and nested complexes for the special case of simplicial complexes.

####  2.1.1 Simplicial complexes

A poset $L$ is called a _meet-semilattice_ if, for every pair of elements
$x,y\in L$, there exists a unique greatest lower bound called the _meet_ and
denoted $x\wedge y$. In this thesis, we will simply call these semilattices. A
theory of semilattice building sets is developed in [7], and is reiterated
here briefly before we focus on the special case where $L$ is a simplicial
complex. All semilattices have a minimal element, written in this thesis as
$\hat{0}$.

For a subset of elements $B$ of a semilattice $L$ and an element $x\in B$,
define $B_{\leq x}=\\{y\in B|y\leq x\\}$. Define $\max B_{\leq x}$ to be the
set of maximal elements in $B_{\leq x}$. For two elements $a\leq b$ in a poset
$P$, define the interval $[a,b]=\\{c\in P|a\leq c\leq b\\}$.

The following definition can be intuitively understood as follows: if $B$ is a
building set, then for every element $x\in L\backslash\\{\hat{0}\\}$, the
interval $[\hat{0},x]$ can be decomposed into the product of intervals
$[\hat{0},y]$ for all $y\in\max B_{\leq x}$. Proposition 2.1.6 provides a much
simpler case, when $L$ is isomorphic to a simplicial complex, and that is the
ony case we will need in this thesis.

######  Definition 2.1.1 ([7]).

Let $L$ be a semilattice. A subset $B$ of $L\backslash\\{\hat{0}\\}$ is called
a _semilattice building set_ of $L$ if for any $x\in L\backslash\\{\hat{0}\\}$
and $\max B_{\leq x}=\\{x_{1},\ldots,x_{k}\\}$ there is an isomorphism of
posets

$\varphi_{x}:\prod_{j=1}^{k}[\hat{0},x_{j}]\to[\hat{0},x]$

with $\varphi_{x}(\hat{0},\ldots,x_{j},\ldots,\hat{0})=x_{j}$ for
$j=1,\ldots,k$.

######  Definition 2.1.2 ([7]).

Let $L$ be a meet-semilattice and $B$ a building set of $L$. A subset $N$ in
$B$ is called _semilattice nested_ if, for any set of incomparable elements
$N^{\prime}=\\{x_{1},\ldots,x_{t}\\}\subseteq N$ with $|N^{\prime}|\geq 2$,
the join $x_{1}\vee\cdots\vee x_{t}$ exists and does not belong to $B$.

######  Definition 2.1.3.

A _simplicial complex_ $\Delta$ on a base set $S$ is a family of subsets of
$S$, or _faces_ , with the condition that every singleton set $\\{s\\}$ for
$s\in S$ is a face of $\Delta$, and such that if $F$ is a face of $\Delta$ and
$F^{\prime}\subset F$, then $F^{\prime}$ is a face of $\Delta$.

The _rank_ of a simplicial complex is the size of its largest face. A
simplicial complex is _pure_ if all of its maximal faces are of the same size.

######  Definition 2.1.4.

The _$B$ -nested complex_ of a semilattice $L$ is the set of all semilattice
nested subsets of elements of a lattice $L$ for a given building set $B$. We
will use the notation $\mathcal{N}(B,L)$ to refer to this simplicial complex.

Faces of a simplicial complex admit a partial order based on inclusion, and we
know the resulting poset is a meet-semilattice, meaning we can define
semilattice building sets on these posets.

Define $\mathcal{B}_{\subseteq S}$ to be the set of sets
$\\{T\in\mathcal{B}|T\subseteq S\\}$. For an ordered set $\mathcal{B}$ with
relation $\leq$, define $\max(\mathcal{B})$ to be the set of maximal elements
in $\mathcal{B}$; that is, $\\{S\in\mathcal{B}|S\not<T\forall
T\in\mathcal{B}\\}$. The following lemma comes very easily from Definition
2.1.1.

######  Lemma 2.1.5.

Given a simplicial complex $\Delta$ on a base set $\mathcal{S}$, a set of
faces $\mathcal{B}$ of $\Delta\backslash\hat{0}$ is a building set if and only
if:

  1. 1.

For each element $s\in\mathcal{S}$, the set $\\{s\\}$ is contained in
$\mathcal{B}$.

  2. 2.

For every nonempty set $S$ in $\Delta$, $\max(\mathcal{B}_{\subseteq S})$ is a
partition of $S$.

###### Proof.

It is simple to show that if $L$ is a semilattice and $B$ is a semilattice-
building set, then all atomic elements of $L$ must be in $B$. If $x$ is an
atom in $L$ and $x\notin B$, then $\max(B_{\leq x})$ must be empty, making
$\prod_{y\in\max B_{\leq x}}[\hat{0},y]$ an empty product. This must
contradict Definition 2.1.1, as $[\hat{0},x]$ is a non-singleton poset. The
atomic elements of a simplicial complex are the singleton sets, and so
simplicial complex building sets must contain all singleton sets.

In a simplicial complex $\Delta$, the interval $[\emptyset,S]$ for any set $S$
is equal to the Boolean lattice of subsets of $S$. We then find that
$\mathcal{B}_{\subseteq S}$ must contain all singleton subsets of $S$. From
this, we see that the union of all sets in $\max\mathcal{B}_{\subseteq S}$ is
equal to $S$. We also find that the product of
$[\emptyset,S_{1}],\ldots,[\emptyset,S_{k}]$ is equal to a Boolean lattice on
$|S_{1}|+\cdots+|S_{k}|$ elements. From these, we can deduce that a set
$\mathcal{B}$ is a building set in $\Delta$ if and only if, for every
$S\in\Delta$, the set $\max(\mathcal{B}_{\subseteq S})$ is a partition of $S$.
∎

We now wish to prove that this is equivalent to another, very useful
definition of building sets, and one which is more familiar to those who have
read the classical definition in [13]. This proposition looks very similar to
Lemma 2.1.5, but the second condition is different.

######  Proposition 2.1.6.

Given a simplicial complex $\Delta$ on a base set $\mathcal{S}$, a set of
faces $\mathcal{B}$ of $\Delta\backslash\hat{0}$ is a building set if and only
if:

  1. 1.

For each element $s\in\mathcal{S}$, the set $\\{s\\}$ is contained in
$\mathcal{B}$.

  2. 2.

For two sets $S_{1},S_{2}\in\mathcal{B}$ where $S_{1}\cap S_{2}\neq\emptyset$,
if $S_{1}\cup S_{2}\in\Delta$, then $S_{1}\cup S_{2}\in\mathcal{B}$.

###### Proof.

Lemma 2.1.5 has already established conditions for a set $\mathcal{B}$ to be a
building set. We intend to show that if $\\{s\\}\in\mathcal{B}$ for every
$s\in\mathcal{S}$, then condition (2) of Lemma 2.1.5 is equivalent to
condition (2) of Proposition 2.1.6. Refer to these conditions as the partition
condition and the intersection-union condition.

We first prove that the partition condition implies the intersection
condition. If $\max\mathcal{B}_{\subseteq S}$ is a partition of $S$ for every
nonempty face $S\in\Delta$, then consider $S=S_{1}\cup S_{2}$ for
$S_{1},S_{2}\in\mathcal{B}$ with nonempty intersection. If $S_{1}\cup
S_{2}\in\Delta$, then $\mathcal{B}_{\subseteq S}$ contains both $S_{1}$ and
$S_{2}$. This then means that $\max\mathcal{B}_{\subseteq S}$ must also
contain the union $S_{1}\cup S_{2}$. As a result, if $\mathcal{B}$ is a
building set, then the intersection-union condition holds.

Now consider the case where $\mathcal{B}$ containing $\\{s\\}$ for each
$s\in\mathcal{S}$ is a set for which the intersection-union condition holds,
and assume that the partition condition does not hold. This means there exists
a nonempty set $S\in\Delta$ such that $\max\mathcal{B}_{\subseteq S}$ is not a
partition of $S$. We know that the union of all sets in
$\max\mathcal{B}_{\subseteq S}$ is equal to $S$, so this can only fail to be a
partition if there exist two sets $S_{1},S_{2}\in\max\mathcal{B}_{\subseteq
S}$ such that $S_{1}\cap S_{2}\neq\emptyset$. However, by the intersection-
union condition, the union $S_{1}\cup S_{2}$ must be in $\mathcal{B}$. This
provides a contradiction, as now $S_{1}\cup S_{2}\in\max\mathcal{B}_{\subseteq
S}$, and either $S_{1}$ or $S_{2}$ in $\max\mathcal{B}_{\subseteq S}$ is a
proper subset of $S_{1}\cup S_{2}$, proving one of the subsets to be non-
maximal. As a result, when $\\{s\\}\in\mathcal{B}$ for all $s\in\mathcal{S}$,
the intersection-union condition and partition condition are equivalent. This
then proves the proposition. ∎

Nested sets of semilattices are defined in Definition 2.1.2. Here, we
characterize nested sets of simplicial complexes.

######  Definition 2.1.7.

Two sets $S_{1},S_{2}$ have _non-trivial intersection_ if $S_{1}\not\subseteq
S_{2}$, $S_{2}\not\subseteq S_{1}$, and $S_{1}\cap S_{2}\neq\emptyset$.

As a result, we can characterize nested sets of simplicial complexes as
follows.

######  Proposition 2.1.8.

Consider a simplicial complex $\Delta$ and $\Delta$-building set
$\mathcal{B}$. Any subset $N\subseteq\mathcal{B}$ is nested if and only if
both conditions hold:

  1. 1.

For every subset $N^{\prime}\subseteq N$ with $|N^{\prime}|\geq 2$ and every
pair of sets in $N^{\prime}$ is disjoint, $\bigcup N^{\prime}$ is in $\Delta$
and not in $\mathcal{B}$.

  2. 2.

No two sets $S_{1},S_{2}\in N$ have nontrivial intersection.

###### Proof.

Call the first condition the disjoint union condition, and call the second
condition the nontrivial intersection condition. We note that Definition 2.1.4
when applied to a simplicial complex is equivalent to saying that a set $N$ is
nested if and only if, for every subset of incomparable sets
$N^{\prime}=\\{S_{1},\ldots,S_{k}\\}\subseteq N$ with $k\geq 2$, the union
$\bigcup_{i=1}^{k}S_{i}$ is in $\Delta$ and not in $\mathcal{B}$. Note that
two sets are incomparable if one is not contained in the other as a subset.

If a set $N$ is $\mathcal{B}$-nested, then the disjoint union condition holds
for $N$, as every set $N^{\prime}$ of disjoint sets is incomparable. In
addition, if two sets $S_{1},S_{2}$ have nontrivial intersection, then they
are incomparable, and $S_{1}\cup S_{2}$ is in $\mathcal{B}$ according to
building set properties, which is a contradiction. As a result, no two sets in
a nested set have nontrivial intersection.

Now say that $N$ satisfies the disjoint union condition and the nontrivial
intersection condition; we wish to prove that $N$ is a nested set. Consider a
subset $N^{\prime}=\\{S_{1},\ldots,S_{k}\\}\subseteq N$ such that
$|N^{\prime}|\geq 2$, and the union $\bigcup N^{\prime}$ either is not in
$\Delta$ or is in $\mathcal{B}$. We note that by the nontrivial intersection
condition, no two of these sets have nontrivial intersection, and so the sets
$S_{1},\ldots,S_{k}$ all are disjoint. Now by the disjoint union condition,
$\bigcup N^{\prime}$ is in $\Delta$ but not in $\mathcal{B}$. As a result, we
have proven that these two conditions are equivalent to saying that $N$ is
$\mathcal{B}$-nested. ∎

####  2.1.2 Links of the nested complexes of simplicial complexes

In [4], every facet of a graph associahedron is associated with the graph
associahedron of a new graph, called the reconnected complement. We are
compelled to find a similar result for $\Delta$-nested complexes. We note that
each face of a simple polyhedron is dual to the link of a set in the dual
simplicial complex of that simple polyhedron. As a result, finding the links
of sets in $\Delta$-nested complexes is a natural generalization of the Carr-
Devadoss result, as well as the results we prove later in 2.3.3.

######  Definition 2.1.9.

Given a set $S$ in a simplicial complex $\Delta$, the _link_ of a face $S$ in
$\Delta$, denoted $\Delta/S$, is the subcomplex of $\Delta$ defined by

$\Delta/S=\\{X|X\in\Delta,X\cup S\in\Delta,X\cap S=\emptyset\\}.$

An equivalent but lesser-used definition is

$\Delta/S=\\{Y\backslash S|\;Y\in\Delta,S\subset Y\\}.$

######  Definition 2.1.10.

For a simplicial complex $\Delta$ and a set $S$ in a $\Delta$-building set
$\mathcal{B}$, the _building set pseudolink_ of $S$ in $\mathcal{B}$, denoted
$\mathcal{B}/S$, is defined as

$\mathcal{B}/S=\\{X|X\in\mathcal{B},X\cup S\in\Delta,X\cap
S=\emptyset\\}\cup\\{Y\backslash S|\;Y\in\mathcal{B},S\subset Y\\}.$

This definition shows parallels between the two definitions of simplicial
complex links. Note that this is not necessarily a disjoint union.

######  Lemma 2.1.11.

The pseudolink $\mathcal{B}/S$ of an element $S$ in a $\Delta$-building set
$\mathcal{B}$ is a building set of the link $\Delta/S$.

###### Proof.

Every atom $\\{x\\}$ of $\Delta/S$ is an atom in $\Delta$, and so must be in
$\mathcal{B}$. From this, we see $\\{x\\}\cup S$ is in $\Delta$, and so
$\\{x\\}$ is in $\mathcal{B}/S$. As a result, ever atom of $\Delta/S$ is in
$\mathcal{B}/S$, and so $\mathcal{B}/S$ satisfies the first condition of
simplicial building sets. Now, we must prove that if $I,J$ are sets in
$\mathcal{B}/S$ with $I\cap J\neq\emptyset$, then $I\cup J\in\mathcal{B}/S$ if
$I\cup J\in\Delta/S$.

Note that a set $X\in\Delta/S$ is in $\mathcal{B}/S$ if and only if
$X\in\mathcal{B}$ or $X\in\mathcal{B}/S$. Assume $I,J\in\mathcal{B}/S$, $I\cap
J\neq\emptyset$, and $I\cup J\in\Delta/S$. We know $I\cup J\cup S\in\Delta$.
If $I\cup S$ is in $\mathcal{B}$, then $(I\cup S)$ has nontrivial intersection
with both sets $J$ and $J\cup S$, which are both in $\mathcal{B}$. As a
result, $I\cup J\cup S\in\mathcal{B}$, and $I\cup J\in\mathcal{B}/S$. By the
same logic, if $J\cup S\in\mathcal{B}$, then $I\cup J\in\mathcal{B}/S$. As a
result, we can consider the case where $I\cup S,J\cup S\notin\mathcal{B}$.
This means that $I,J\in\mathcal{B}$, and because of their nonempty
intersection, $I\cup J\in\mathcal{B}$. As a result, either $I\cup J\cup S$ or
$I\cup J$ is in $\mathcal{B}$, which implies $I\cup J\in\mathcal{B}/S$.
Therefore, we have satisfied the two conditions of building sets, and
$\mathcal{B}/S$ is a $\Delta/S$-building set. ∎

Having shown that $\mathcal{B}/S$ is a building set, we now know that its
nested complex $\mathcal{N}(\mathcal{B}/S,\Delta/S)$ exists, and state the
following proposition about it.

######  Proposition 2.1.12.

The nested complex $\mathcal{N}(\mathcal{B}/S,\Delta/S)$ is isomorphic to the
subcomplex of $\mathcal{N}(\mathcal{B},\Delta)$ consisting of sets
$N\in\mathcal{N}(\mathcal{B},\Delta)$ such that $N$ contains no subset of $S$
as an element, and $N\cup\\{S\\}$ is $\mathcal{B}$-nested.

###### Proof.

Define $\mathcal{M}$ to be the simplicial complex of $\mathcal{B}$-nested sets
such that, for each $N\in\mathcal{M}$, no subset of $S$ is an element of $N$,
and $N\cup\\{S\\}$ is $\mathcal{B}$-nested. Define a map $\phi(T)=T\backslash
S$ for all $T\in\mathcal{B}$. We will first prove that this map is a bijection
between the base set of $\mathcal{M}$ and the base set of
$\mathcal{N}(\mathcal{B}/S,\Delta/S)$. We will then extend this map to a map
between faces of $\mathcal{M}$ and faces of the complex
$\mathcal{N}(\mathcal{B}/S,\Delta/S)$, with $\phi(N)=\\{\phi(T)|T\in N\\}$,
and prove that this map is an isomorphism.

We first prove that $\phi$ is injective on the base set of $\mathcal{M}$. Say
$T_{1},T_{2}\in\mathcal{B}$ and $\\{T_{1},S\\},\\{T_{2},S\\}$ are both nested,
and $T_{1}\backslash S=T_{2}\backslash S$. As a result,
$\phi(T_{1})=\phi(T_{2})$. In order to prove that $\phi$ is injective, we must
prove that $T_{1}=T_{2}$, which we do by investigating different cases. If
$T_{1}\cap S=\emptyset$ and $T_{2}\cap S=\emptyset$, then $T_{1}=T_{2}$.
Assume then that one of the sets intersects with $S$; without loss of
generality, assume $T_{1}\cap S\neq\emptyset$. Because $\\{T_{1},S\\}$ is
nested, by Proposition 2.1.8, the two sets can only have trivial intersection,
and we find $S\subseteq T_{1}$.

In the case where $S\cap T_{2}\neq\emptyset$, we find that $T_{1}\cap
T_{2}\neq\emptyset$, and $S\subseteq T_{1}\subseteq T_{2}$ or $S\subseteq
T_{2}\subseteq T_{1}$. In either case, we find that $T_{1}\backslash
S=T_{2}\backslash S$ implies $T_{1}=T_{2}$. Now as the only remaining case, we
must assume that $S\subseteq T_{1}$ and $T_{2}\cap S=\emptyset$. In this case,
we find $T_{1}\backslash S=T_{2}\backslash S$ implies $T_{1}$ is the disjoint
union of $S$ and $T_{2}$. This however is a contradiction, as by Proposition
2.1.8, two disjoint sets $\\{S,T_{2}\\}$ in a $\mathcal{B}$-nested set cannot
have a union in $\mathcal{B}$, but $S\cup T_{2}=T_{1}\in\mathcal{B}$. As a
result, we have proven that $\phi$ is injective into $\mathcal{B}/S$.

Next we prove that $\phi$ is surjective onto $\mathcal{B}/S$, by proving that
for every set $T\in\mathcal{B}/S$ there is a preimage in $\mathcal{M}$. If
$T\in\mathcal{B}/S$, then there exists at least one set $Y\in\mathcal{B}$ such
that $Y\backslash S=T$. We are presented with three cases: either $S,Y$ are
disjoint, $S\subseteq Y$, or $S,Y$ have nontrivial intersection. If $S,Y$ are
disjoint, then $T=Y$, and $\phi(Y)=T$. Now consider the case that $S\subseteq
Y$. We find very easily that $\\{S,Y\\}$ is nested, and so $Y$ is in the base
set of $\mathcal{M}$, and $\phi(Y)=T$. Finally, consider the case that $S,Y$
have nontrivial intersection. This means that $\\{S,Y\\}$ is not nested.
However, we know from Proposition 2.1.6 that $S\cup Y$ is in $\mathcal{B}$,
and $\\{S\cup Y,S\\}$ must be $\mathcal{B}$-nested, meaning $S\cup Y$ is in
the base set of $\mathcal{M}$ and $\phi(S\cup Y)=T$.

As a result, $\phi$ is an isomorphism between the base set of $\mathcal{M}$
and $\mathcal{B}/S$, the base set of $\mathcal{N}(\mathcal{B}/S,\Delta/S)$. We
will now prove that $N$ in $\mathcal{M}$ is $\mathcal{B}$-nested if and only
if $\phi(N)$ is $\mathcal{B}/S$-nested, proving $\phi$ is an isomorphism and
the two complexes are isomorphic.

We will prove the forward direction first. Consider the case where $N$ is in
$\mathcal{M}$, and we will prove $\phi(N)$ is $\mathcal{B}/S$-nested. Consider
two sets $T_{1},T_{2}$ in $N$. If $T_{1},T_{2}$ are disjoint, then
$\phi(T_{1}),\phi(T_{2})$ are disjoint. If $T_{1}\subseteq T_{2}$, then
$(T_{1}\backslash S)\subseteq(T_{2}\backslash S)$. As a result, the set
$\phi(N)$ has no nontrivial intersecting pairs, satisfying the second
condition of 2.1.8. Now we will prove that $\phi(N)$ satisfies the first
condition of Proposition 2.1.8, that for any subset of $\phi(N)$, with
cardinality at least two and containing disjoint subsets, their union cannot
be in $\mathcal{B}/S$.

If $N^{\prime}=\\{T_{1},\ldots,T_{k}\\}\subseteq N$ and $\phi(N^{\prime})$ is
a set of disjoint sets with $|N^{\prime}|\geq 2$, we find that
$\bigcup\phi(N^{\prime})=\bigcup N^{\prime}\backslash S$. Consider a case
where $N$ is nested and in $\mathcal{M}$ but
$\bigcup\phi(N^{\prime})\in\mathcal{B}/S$, meaning $\phi(N)$ is not nested.
Note that $\bigcup N^{\prime}\backslash S$ is in $\mathcal{B}/S$ only if
$\bigcup N^{\prime}$ or $\bigcup N^{\prime}\backslash S$ is in $\mathcal{B}$.
We know that $\bigcup N^{\prime}$ cannot be in $\mathcal{B}$ because $N$ is
$\mathcal{B}$-nested, so assume $S\subseteq\bigcup N^{\prime}$. Note as well
that $S$ can only be a subset of one element of $N^{\prime}$; otherwise,
$\phi(N^{\prime})$ is not disjoint. Without loss of generality, write
$S\subset T_{1}$. We now find that $\bigcup N^{\prime}\backslash
S\in\mathcal{B}$, and $T_{1}\in\mathcal{B}$ both have nontrivial intersection,
and the union of these two sets must be in $\mathcal{B}$. However, their union
is $\bigcup N^{\prime}$, which cannot be in $\mathcal{B}$ if $N$ is nested, so
this is a contradiction. As a result, $\phi(N)$ must be $\mathcal{B}/S$-nested
for every set $N\in\mathcal{M}$.

Now consider a case where $N$ is a subset of the base set of $\mathcal{M}$. We
now wish to prove that if $\phi(N)$ is $\mathcal{B}/S$-nested, then $N$ is
$\mathcal{B}$-nested, and therefore in $\mathcal{M}$.

If $\phi(N)$ is $\mathcal{B}/S$-nested, consider two sets $T_{1},T_{2}\in N$.
If $T_{1},T_{2}$ have nontrivial intersection, then one of the following is
true: either $\phi(T_{1}),\phi(T_{2})$ have nontrivial intersection with each
other, $T_{1}$ or $T_{2}$ have nontrivial intersection with $S$, or
$\phi(T_{1}),\phi(T_{2})$ are disjoint. The first case is a contradiction
because $\phi(N)$ is $\mathcal{B}/S$-nested, and no two sets in a nested set
can have nontrivial intersection. The second case implies that either
$\\{T_{1},S\\}$ or $\\{T_{2},S\\}$ is not nested, but when defining the base
set of $\mathcal{M}$ we assumed $\\{S,T\\}$ was nested for each set $T$ in the
base set, so this is a contradiction. The third case implies that $T_{1}\cap
T_{2}\neq\emptyset$ and $(T_{1}\backslash S)\cap(T_{2}\backslash
S)=\emptyset$, and because neither set has trivial intersection with $S$,
implies that $T_{1}\cap T_{2}=S$. This then means that $T_{1}\cup
T_{2}\in\mathcal{B}$, and $T_{1}\cup T_{2}\backslash S\in\mathcal{B}/S$, which
is a contradiction because $\phi(N)$ is $\mathcal{B}/S$-nested.

If $\phi(N)$ is $\mathcal{B}/S$-nested, consider a disjoint set
$N^{\prime}=\\{T_{1},\ldots,T_{k}\\}\subseteq N$ with $|N^{\prime}|\geq 2$. We
find that $\phi(N^{\prime})$ is a set of disjoint sets, and is a subset of
$\phi(N)$. If $\bigcup N^{\prime}\in\mathcal{B}$, we find that
$\bigcup\phi(N^{\prime})\in\mathcal{B}/S$, which is a contradiction because
$\phi(N)$ is nested.

As a result, we have proven that the map $\phi$ is a bijection between the
base sets of $\mathcal{M}$ and $\mathcal{N}(\mathcal{B}/S,\Delta/S)$, and it
extends to an isomorphism between the two simplicial complexes. ∎

This isomorphism is used in Proposition 2.1.17, but first we must state some
definitions for simplicial complexes.

######  Definition 2.1.13.

The _restriction_ of a $\Delta$-building set $\mathcal{B}$ to a simplicial
subcomplex $\Delta^{\prime}\subseteq\Delta$ is the set
$\mathcal{B}\cap\Delta^{\prime}=\\{S\in\mathcal{B}|S\in\Delta^{\prime}\\}$.

It is trivial to apply Proposition 2.1.6 to find that the restriction of a
$\Delta$-building set $\mathcal{B}$ to a subcomplex $\Delta^{\prime}$ is a
$\Delta^{\prime}$-building set.’

######  Proposition 2.1.14.

If $\Delta^{\prime}\subseteq\Delta$ and $\mathcal{B}$ is a $\Delta$-building
set, then $N$ is $(\mathcal{B}\cap\Delta^{\prime})$-nested if and only if $N$
is $\mathcal{B}$-nested and $\bigcup N\in\Delta^{\prime}$.

###### Proof.

This follows from Proposition 2.1.8. If $N$ is
$\mathcal{B}\cap\Delta^{\prime}$-nested, then there is no subset
$N^{\prime}\subseteq N$ of disjoint sets with $|N^{\prime}|\geq 2$ such that
$\bigcup N^{\prime}\in(\mathcal{B}\cap\Delta^{\prime})$, and since $\bigcup
N^{\prime}\in\Delta^{\prime}$, we know $\bigcup N^{\prime}\notin\mathcal{B}$.
In the case that $N$ is $\mathcal{B}$-nested and $\bigcup
N\in\Delta^{\prime}$, we know that for any subset of disjoint sets
$N^{\prime}\subseteq N$ with $|N^{\prime}|\geq 2$ that $\bigcup
N^{\prime}\in\Delta^{\prime}$ and $\bigcup N^{\prime}\in\mathcal{B}$, so
$\bigcup N^{\prime}\in(\mathcal{B}\cap\Delta^{\prime})$. In either case, the
second condition of 2.1.8 holds. ∎

######  Definition 2.1.15.

The _Cartesian product_ of two simplicial complexes $\Delta_{1},\Delta_{2}$
with disjoint vertex sets is equal to the simplicial complex $\\{S_{1}\cup
S_{2}|S_{1}\in\Delta_{1},S_{2}\in\Delta_{2}\\}$.

We state the two following definitions for clarity.

######  Definition 2.1.16.

The _subset complex_ of a set $S$ is the simplicial complex $\\{T|T\subseteq
S\\}$, and the _proper subset complex_ of a set $S$ is the simplicial complex
$\\{T|T\subset S\\}$.

The subset complex of a set $S$ is often identified with a Boolean lattice,
whereas the proper subset complex is often identified with the boundary
complex of a simplex. With these terms defined, we can now state the following
proposition.

######  Proposition 2.1.17.

For any set $S$ in a $\Delta$-building set $\mathcal{B}$, the link of the
singleton face $\\{S\\}$ in the $\mathcal{N}(\mathcal{B},\Delta)$ is
isomorphic to the Cartesian product of the nested complex of $\mathcal{B}$
restricted to the proper subset complex on $S$, and the nested complex
$\mathcal{N}(\mathcal{B}/S,\Delta/S)$.

###### Proof.

Proposition 2.1.8 implies that if a set $S$ is in a $\mathcal{B}$-nested set
$N$, then no other set in $N$ has nontrivial intersection with $S$. This means
that if $S^{\prime}\in N$ and $S^{\prime}\neq S$, then either
$S^{\prime}\subsetneq S$, $S\subsetneq S^{\prime}$, or $S\cap
S^{\prime}=\emptyset$. Call the set consisting of the first case
$N_{1}=\\{S^{\prime}\in N|S^{\prime}\subsetneq S\\}$, and
$N_{2}=\\{S^{\prime}\in N|S^{\prime}\not\subseteq S\\}$ is the set consisting
of the latter two cases. We find $N=N_{1}\cup N_{2}\cup\\{S\\}$ for any
$\mathcal{B}$-nested set $N$ containing $S$.

It is clear that $N_{1}$ is a member of the restriction of $\mathcal{B}$ to
the proper subset complex of $S$. For this proof, call the proper subset
complex $P(S)$, and we say $N_{1}\subseteq\mathcal{N}(\mathcal{B}\cap
P(S),P(S))$. It is also clear that $N_{2}$ is a member of $\mathcal{M}$, the
simplicial complex used in the proof of Proposition 2.1.12. We note that these
two complexes are completely disjoint, as $N_{1}$ must contain only sets which
are subsets of $S$, and $N_{2}$ must contain only sets which are not subsets
of $S$. As a result, the link of $S$ in $\mathcal{N}(\mathcal{B},\Delta)$ is
contained in the simplicial complex Cartesian product
$\mathcal{N}(\mathcal{B}\cap P(S),P(S))\times\mathcal{M}$. In order to prove
that they are equal, we prove that for $N_{1}\in\mathcal{N}(\mathcal{B}\cap
P(S),P(S))$ and $N_{2}\in\mathcal{M}$, we find $N_{1}\cup N_{2}\cup\\{S\\}$ is
$\mathcal{B}$-nested. This however is simple. We note $N_{1},N_{2}$ must
already be $\mathcal{B}$-nested, and if $T_{1},T_{2}$ have nontrivial
intersection for $T_{1}\in N_{1},T_{2}\in N_{2}$, then we would find $S$ and
$T_{2}$ have nontrivial intersection, meaning $N_{2}\notin\mathcal{M}$.
Similarly, for some set of disjoint sets $N^{\prime}\subseteq N$ with
$|N^{\prime}|\geq 2$ and $\bigcup N^{\prime}\in\mathcal{B}$, we would find
that if $N^{\prime}=N_{1}^{\prime}\cup N_{2}^{\prime}$, we would find the set
$\\{S\\}\cup N_{2}^{\prime}$ would be disjoint, have magnitude $\geq 2$, and
would have a union in $\mathcal{B}$, meaning $N_{2}\notin\mathcal{M}$.

As a result, the link of $S$ in $\mathcal{N}(\mathcal{B},\Delta)$ is the
Cartesian product of these two simplicial complexes, and because $\mathcal{M}$
is isomorphic to the pseudolink nested complex, we have proven the
proposition. ∎

###  2.2 Graph nested complexes

Graph associahedra and related graphic building sets and their nested
complexes have been studied in many papers. A description of graph
associahedra and nested complexes is given both in the introduction of this
thesis, and in Subsection 2.3.4.This section does the work to generalize this
construction to define $\Delta$-nested complexes based on graphs.

The study of graph associahedra and their associated complexes uses a set of
terminology not used in the study of other nestohedra and nested complexes. In
nested complex terminology, elements of a building set $\mathcal{B}$ are not
given a name, and collections of compatible elements of $\mathcal{B}$ are
called nested sets. We will define a building set whose elements are connected
induced subgraphs, which are called _tubes_ , and collections of compatible
tubes are called _tubings_. This terminology is used in the paper introducing
graph associahedra, [4].

For clarity, we will refer to constructions defined in prior work as graph
associahedra, tubings, tubes, etc. as _classical_ graph associahedra,
classical tubings, etc.

####  2.2.1 $\Delta$-graph Tubings

######  Definition 2.2.1.

For a simplicial complex $\Delta$ on a base set $\mathcal{S}$, a
$\Delta$-graph is a pair $(G,\Delta)$ such that $G$ is a graph on
$\mathcal{S}$ such that, if $\\{i,j\\}$ is an edge in $G$, then $\\{i,j\\}$ is
a face of $\Delta$.

######  Definition 2.2.2.

A _tube_ of a $\Delta$-graph $(G,\Delta)$ is any face of $\Delta$ which
induces a connected subgraph of $G$.

######  Definition 2.2.3.

Two tubes $t_{1},t_{2}$ of a $\Delta$-graph $(G,\Delta)$ are _weakly
compatible_ if one of the following is true:

  1. 1.

$t_{1}\subset t_{2}$

  2. 2.

$t_{2}\subset t_{1}$

  3. 3.

$t_{1}\cap t_{2}=\emptyset$ and there exist no edges between vertices in
$t_{1}$ and $t_{2}$.

For the traditional graph case, when $G$ is connected, a collection of tubes
is a tubing if and only if all tubes are pairwise weakly compatible. However,
nested sets of simplicial complexes add an extra requirement for tubings.

######  Definition 2.2.4.

A set of tubes $T$ is _strongly compatible_ if the union $\bigcup_{t\in T}t$
is a face of $\Delta$, and it is pairwise weakly compatible.

Note that weak compatibility is only defined for pairs of tubes. Strong
compatibility, on the other hand, applies to sets of tubes. A set of tubes
must be pairwise weakly compatible. However, note that it is possible for a
set of tubes to be pairwise strongly compatible, but not be strongly
compatible.

######  Definition 2.2.5.

A _tubing_ is any strongly compatible set of tubes.

######  Definition 2.2.6.

The _graphical building set_ $\mathcal{B}_{(G,\Delta)}$ of a $\Delta$-graph
$(G,\Delta)$ is the set of all tubes of $(G,\Delta)$.

######  Proposition 2.2.7.

The graphical building set $\mathcal{B}_{(G,\Delta)}$ of a $\Delta$-graph
$(G,\Delta)$ is a $\Delta$-building set.

###### Proof.

First, we see that every singleton set in $\Delta$ induces a single vertex
subgraph, which is connected, so every singleton set of $\Delta$ is a tube.

Next, consider two tubes $t_{1},t_{2}\in\mathcal{B}_{(G,\Delta)}$. If
$t_{1}\cap t_{2}\neq\emptyset$, then $t_{1}\cup t_{2}$ must induce a connected
subgraph. If $t_{1}\cup t_{2}\in\Delta$, then $t_{1}\cup t_{2}$ is a tube in
$\mathcal{B}_{(G,\Delta)}$. ∎

######  Proposition 2.2.8.

For a $\Delta$-graph $(G,\Delta)$, the set of tubings of $(G,\Delta)$ is equal
to the set of nested sets of the graphical building set of $(G,\Delta)$.

###### Proof.

First, we prove that a tubing $T$ is a nested set. First, a tubing has
pairwise weak compatibility, so no two tubes have nontrivial intersection.
Secondly, if $T^{\prime}=\\{t_{1},\ldots,t_{k}\\}\subseteq T$ is a set of
disjoint tubes with $|T^{\prime}|\geq 2$, then we see that due to weak
compatibility, $\bigcup T^{\prime}$ induces $k$ graph components with no edges
between them. As a result, $\bigcup T^{\prime}$ is not a tube. Because of
strong compatibility, $\bigcup T^{\prime}\in\Delta$. As a result, $T$ must be
a nested set.

Now we must prove that if $T$ is nested, then $T$ is a tubing. For any two
tubes $t_{1},t_{2}\in T$, we know $t_{1}\subset t_{2},t_{2}\subset t_{1}$, or
the two are disjoint. If the two are disjoint, then $t_{1}\cup t_{2}$ cannot
be a tube. If $t_{1}\cup t_{2}\in\Delta$ cannot be a tube, then there are no
edges between $t_{1}$ and $t_{2}$. This shows $T$ is pairwise weakly
compatible.

In addition, if $T$ is $\Delta$-nested, then $\bigcup T\in\Delta$. As a
result, $T$ is strongly compatible, and $T$ is a tubing.

∎

######  Definition 2.2.9.

The _$\Delta$ -building set closure_ of a set $E\subseteq\Delta$ is the
minimal $\Delta$-building set containing $E$.

It is trivial to show that the intersection of two $\Delta$-building sets is a
$\Delta$-building set, so we see that a unique minimal $\Delta$-building set
must exist.

######  Proposition 2.2.10.

The graphic building set of a $\Delta$-graph $G$ is the $\Delta$-building set
closure of the edge set of $G$.

###### Proof.

Given a building set $\mathcal{B}$ and a subset $E\subseteq\mathcal{B}$, we
find that $\mathcal{B}$ is the minimal $\Delta$-building set containing $E$ if
$\mathcal{B}$ is a building set and, for every non-singleton set
$S\in\mathcal{B}$, there exists a series $S_{1},S_{2},\ldots,S_{k}$ such that
$\bigcup_{i=1}^{k}S_{i}=S$, and $\left(\bigcup_{i=1}^{j}S_{i}\right)$ and
$S_{k}$ have nontrivial intersection.

Every tube $t$ induces a connected subgraph. Every connected graph contains a
spanning tree. Every tree consists of edges $e_{1},\ldots,e_{k}$ which can be
ordered such that the graph consisting of edges $e_{1},\ldots,e_{i}$ is
connected for each $1\leq i\leq k$, and the edge $e_{i+1}$ connects a new
vertex to a growing subtree. Bringing this together, if each edge is
represented as a pair of vertices $e=\\{u,v\\}$, then
$t=\bigcup_{i=1}^{k}e_{i}$, and $\bigcup_{i=1}^{j}e_{i}$ and $e_{j+1}$
intersect for each $1\leq j\leq k-1$. ∎

######  Remark 2.2.11.

A theory of $\Delta$-graphs may be developed where the requirement that edges
be faces of $\Delta$ is not necessary. However, if we define $\Delta$-graphs
to allow such edges, we find them extraneous. If $G$ is a $\Delta$-graph, and
$G^{\prime}$ is the union of $G$ with a set of additional edges which are not
faces in $\Delta$, then the sets of tubes and tubings of $G$ will be equal to
the sets of tubes and tubings of $G^{\prime}$. Furthermore, because we forbid
edges not in $\Delta$, this means the edge set of $G$ is a subset of $\Delta$,
and we can state Proposition 2.2.10. Finally, Chapter 4 makes great use of the
convention that ‘forbidden subsets’ use dashed edges, and this way one does
not draw a dashed and an undashed edge between the same pair of vertices. For
these reasons, we have made the decision to define $\Delta$-graphs in this
way.

####  2.2.2 Reconnected complement

Regarding classical graph tubes and tubings, the work in [4] proves that the
link of a classical $1$-tubing $\\{t\\}$ of a graph $G$ is combinatorially
isomorphic to the product of the classical tubing complex of the graph induced
by $t$ in $G$, and the classical tubing complex of the _reconnected
complement_ of $t$ in $G$, where the reconnected complement is the graph
obtained by taking the complement $G\backslash t$ of $t$ in $G$, and drawing
edges connecting all pairs $(u,v)$ such that $u$ is connected to some vertex
of $t$ and $v$ is connected to some vertex in $t$. In this subsection, we
generalize this classical reconnected complement for $\Delta$-graphs.

######  Definition 2.2.12.

Given a $\Delta$-graph $G$, a vertex $v\in G$ is _reconnectable_ to a tube $t$
if $t\cup\\{v\\}$ is in $\Delta$.

The vertices reconnectable to a tube $t$ form the base set of the link
$\Delta/t$.

######  Definition 2.2.13.

The _reconnected complement_ of the tube $t$ in a $\Delta$-graph $G$ is the
graph $G/t$ on the set of vertices not in $t$ but reconnectable to $t$, with
edges defined as follows:

  1. 1.

If $\\{x,y\\}$ is an edge in $G$, then $\\{x,y\\}$ is an edge in $G/t$.

  2. 2.

If $x,y$ are both adjacent to vertices in $t$ and $\\{x,y\\}$ is a face of
$\Delta/t$, then $\\{x,y\\}$ is an edge in $G/t$.

######  Proposition 2.2.14.

Given a $\Delta$-graph $G$ and a tube $t$ of $G$, the pseudolink of the
graphic $\Delta$-building set of $G$ with respect to $t$ is equal to the
graphic $(\Delta/t)$-building set of $G/t$.

###### Proof.

If $\mathcal{B}_{G}$ is the graphic $\Delta$-building set of $G$, then
$\mathcal{B}_{G}/t$ is the pseudolink of $\mathcal{B}_{G}$. We restate the
definition of the pseudolink:

$\mathcal{B}_{G}/t=\\{s|s\in\mathcal{B}_{G},s\cup t\in\Delta,s\cap
t=\emptyset\\}\cup\\{s\backslash t|s\in\mathcal{B}_{G},t\subset s\\}$

First, we prove that every element of $\mathcal{B}_{G}/t$ is a tube of $G/t$.
Every element in $\mathcal{B}_{G}/t$ is either equal to $s$ in
$\\{s|s\in\mathcal{B}_{G},s\cup t\in\Delta,s\cap t=\emptyset\\}$, or
$s\backslash t$ in $\\{s\backslash t|s\in\mathcal{B}_{G},t\subset s\\}$.

Consider the case that $s\in\mathcal{B}_{G},s\cup t\in\Delta,$ and $s\cap
t=\emptyset$. We find that $s,t$ are disjoint, and $s\cup t\in\Delta$ so all
vertices of $s$ are reconnectable to $t$. Note that $G/t$ is a graph
constructed from the graph induced by the vertices reconnectible to $t$ in $G$
by adding edges, so if $G|_{s}$ is connected, then $G/t|_{s}$ is connected. As
a result, $s$ is a tube in $G/t$.

Consider the other case, that $s\in\mathcal{B}_{G}$ and $t\subset s$, and we
will prove that $s\backslash t$ is a tube of $G/t$. Say that $G|_{s\backslash
t}$ has $k$ components. If $k\geq 2$, the graph $G/t$ adds a clique connecting
all components of $G|_{s\backslash t}$, meaning that $s\backslash t$ induces a
connected graph, and $s\backslash t$ is a tube of $G/t$. As a result,
$\mathcal{B}_{G}$ consists of $G/t$-tubes.

If $s$ is a tube of $G/t$, then consider the following. If $s$ is connected in
$G$, then $s$ is a tube of $G$ with $s\cap t=\emptyset$, so
$s\in\mathcal{B}_{G}/t$. If $s$ is not connected in $G$, then because the only
edges between reconnectable vertices are between neighbors of $t$, this means
every component in $G|_{s}$ contains a neighbor of $t$. This means $s\cup t$
is a tube, and therefore $(s\cup t)\backslash t=s$ is in $\mathcal{B}_{G}/t$.
As a result, we have proven the proposition. ∎

###  2.3 $\mathcal{P}$-nestohedra

####  2.3.1 Definitions for polyhedra

A _polyhedron_ is a subset of points in a vector space defined by a finite set
of non-strict hyperplane inequalities of the form
$\\{\mathbf{c}_{i}\mathbf{x}\geq y_{i}|\mathbf{x}\in\mathbb{R}^{n}\\}$ for a
set of row vectors $\mathbf{c}_{i}\in(\mathbb{R}^{n})^{*}$ and
$y_{i}\in\mathbb{R}$. For every polyhedron, we may choose a minimal set of
inequalities which define the polyhedron, each of which defines a facet. A
full-dimensional polyhedron of dimension $n$ is _simple_ if every codimension
$k$ face is contained in exactly $k$ facets. For the scope of this thesis, we
will use $\mathcal{P}$ to refer to the class of full-dimensional simple
polyhedra.

A _polytope_ is any polyhedron which is bounded. In this thesis, results are
proven for the polyhedron case wherever possible.

Consider a simple polyhedron $P$. Index the facets of $P$ by some set
$\mathcal{S}$, so that the set of facets is $\\{F_{s}|s\in\mathcal{S}\\}$. For
a subset $I\subseteq\mathcal{S}$, define the face $F_{I}$ as the intersection
of all facets $F_{s}$ for $s\in I$. Because $P$ is simple, each non-empty face
of $P$ has a unique expression as an intersection of facets of $P$.

######  Definition 2.3.1.

The _dual simplicial complex_ , written as $\Delta(P)$, of a simple polyhedron
$P$ is the simplicial complex of sets $I\subseteq S$ such that the face
$F_{I}\neq\emptyset$.

The _lineality space_ $lineal(P)$ of a polyhedron $P$ in $\mathbb{R}^{n}$ is
the set of vectors $v\in\mathbb{R}^{n}$ such that $v+x\in P$ for all $x\in P$.
This is a subspace. If $U$ is a complementary subspace to $lineal(P)$, then
$P=(P\cap U)+lineal(P)$. We say that $P$ is _pointed_ if and only if
$lineal(P)=\\{0\\}$, and this is equivalent to saying that $P$ has at least
one vertex face.

The _face lattice_ of a polyhedron $P$ is the poset of all faces of $P$,
including the empty face. For a simple polyhedron, the dual simplicial complex
is isomorphic to the of the dual face lattice with the empty face removed. In
this isomorphism, the set $S$ in the dual simplicial complex maps to the
codimension-$|S|$ face $F_{S}$ of $P$. We define the following:

######  Definition 2.3.2.

Two polyhedra $P,P^{\prime}$ are _combinatorially isomorphic_ if their face
lattices are related by an isomorphism taking each face $F$ in $P$ to a face
$F^{\prime}$ in $P^{\prime}$ such that $dim(F)=dim(F^{\prime})$.

######  Remark 2.3.3.

We note that if $P,P^{\prime}$ are both simple, then $P,P^{\prime}$ are
combinatorially isomoprhic if and only if their dual simplicial complexes are
isomorphic and $P,P^{\prime}$ have either the same dimension, or the same
dimension lineality space. We note that dual simplicial complex does not
uniquely determine polyhedra up to combinatorial isomorphism. However, dual
simplicial complexes do uniquely determine _pointed_ polyhedra up to
combinatorial isomorphism.

####  2.3.2 Defining $\mathcal{P}$-nestohedra

######  Definition 2.3.4.

A $P$-building set $\mathcal{B}$ is a building set of the dual simplicial
complex of a simple polyhedron $P$. Nested sets of a $P$-building set are
called _$P$ -nested_.

######  Definition 2.3.5.

A _$P$ -nestohedron_ of a $P$-building set $\mathcal{B}$ is a simple
polyhedron whose dual simplicial complex is isomorphic to the nested complex
of $\mathcal{B}$. Use the notation $\mathcal{K}_{P}\mathcal{B}$ to refer to a
$P$-nestohedron of $\mathcal{B}$.

We can define a method for constructing $P$-nestohedra by repeated truncation
of $P$. Consider an inequality $ax\leq b$, dividing the vector space into two
halfspaces, the open halfspace $H_{>}$ defined by $ax>b$, and the closed
halfspace $H_{\leq}$ defined by $ax\leq b$. The hyperplane $H$ is the set of
points $ax=b$. We can define $H_{<}$ and $H_{\geq}$ similarly.

######  Definition 2.3.6.

Consider a polyhedron $Q$ with a face $F$, and a halfspace $H_{\leq}$ defined
by $ax\leq b$. We say that this inequality _truncates_ $Q$ by the face $F$ if
$F\subset H_{>}$ and the following two conditions are true. First, if
$F^{\prime}\cap F\neq\emptyset$ and $F^{\prime}\not\subseteq F$ for any face
$F^{\prime}$ of $Q$, then $H\cap F^{\prime}\neq\emptyset$. Secondly, if
$F^{\prime}\cap F=\emptyset$ and $F^{\prime}$ is a face of $Q$, then
$F^{\prime}\subset H_{<}$. If a hyperplane truncates $Q$ at a face $F$, define
the _truncation of $Q$ at the face $F$_ as the polyhedron $Q\cap H_{\leq}$. We
may call this $\textrm{Tr}_{H}(Q)$.

When $Q$ is a polytope and $F$ is a proper face, we note that any inequality
which truncates $F$ separates all vertices of $F$ from all other vertices in
$Q$, effectively ‘cutting off’ that face. Figure 2.1 shows some example
truncations of faces of a cube and a square, including a facet truncation
which amounts to the perturbation of a facet-defining hyperplane and therefore
does not change the combinatorial structure of a simple polyhedron.

Figure 2.1: Example truncations.

We note in the next proposition that we can always find a truncation for any
face.

######  Proposition 2.3.7.

For any face $F$ of a polyhedron $Q$ defined by an inequality $ax\leq b$,
there exists $\varepsilon>0$ such that the inequality $ax\leq b-\varepsilon$
truncates $F$ in $Q$.

_Combinatorial blowup_ is defined in [7], where it is noted that it
specializes to stellar subdivision of an abstract simplicial complex. We
define a version of stellar subdivision here.

######  Definition 2.3.8.

Given a simplicial complex $\Delta$ and a set $S$ in $\Delta$, the _stellar
subdivision_ $\textrm{St}_{S}\Delta$ is a simplicial complex containing the
elements

  * •

$T\in\Delta$ such that $S\not\subseteq T$

  * •

Sets $T\cup\\{h\\}$ such that $S\not\subseteq T$ and $S\cup T\in\Delta$.

for some element $h\notin\Delta$. We say we replace the set $S\in\Delta$ with
the element $h$.

The _tube promotion_ process described in [4] is a special case of a stellar
subdivision operation applied to nested complexes. We note that when $P$ is a
simple polyhedron, truncation is dual to stellar subdivision.

######  Proposition 2.3.9.

If $P$ is a simple polyhedron with nonempty face $F_{S}$ defined by
intersection of facets $\\{F_{s}|s\in S\\}$ for nonempty set $S$, and $H$
truncates $P$ at $F$, then
$\Delta(\textrm{Tr}_{F_{S}}P)=\textrm{St}_{T}\left(\Delta(P)\right)$.

###### Proof.

First, we take it as trivial that if a simple polyhedron $Q$ is
$k$-dimensional, and $H$ is a hyperplane, then if $H\cap Q$ is not a face of
$Q$, then $H\cap Q$ is $k-1$-dimensional, and $H_{\leq}\cap Q$ is
$k$-dimensional. Note $H\cap Q$ does not need to be a proper or nonempty face
of $Q$. We also note that when $H$ truncates a face of a polyhedron $P$, then
$H\cap P$ is not a nonempty face of $P$, and for any $k$-dimensional face $F$
such that $F\cap H$ is nonempty, $F\cap H$ is $k-1$-dimensional and $F\cap
H_{\leq}$ is $k$-dimensional.

Now, we wish to characterize all faces of $Tr_{F_{S}}(P)$. These faces are of
two possible forms: the first is $F_{T}\cap H_{\leq}$, and the second is
$F_{T}\cap H$.

Consider the case where $S\subseteq T$. We find $F_{T}\subseteq F_{T}$, and
$F_{T}\cap H_{\leq}=F_{T}\cap H=\emptyset$. These faces are empty in the
truncation.

Consider the case where $S\not\subseteq T$. If $S\cup T\in\Delta(P)$, then
$F_{S}\cap F_{T}$ is nonempty, and by the definition of truncation, $F_{T}\cap
H\neq\emptyset$. As a result, $F\cap H_{\leq}$ is a $k$-dimensional face. If
$S\cup T\notin\Delta(P)$, then $F_{S}\cap F_{T}=\emptyset$, and by the
truncation definition, $F_{T}\subset H_{<}$. This means $F_{T}\cap
H_{le}=F_{T}$.

As a result, we have characterized all faces of the form $F_{T}\cap H_{\leq}$.
If $S\subseteq T$, then $F_{T}\cap H_{\leq}=\emptyset$, and if $S\not\subseteq
T$ for $T\in\Delta(P)$, then $F_{T}\cap H_{\leq}$ is a codimension-$|T|$ face.

Now consider the faces of the form $F_{T}\cap H$. If $S\not\subseteq T$ and
$S\cup T\notin\Delta(P)$, then $F_{T}\subset H_{<}$, and $F_{T}\cap
H=\emptyset$. If $S\not\subseteq T$ and $S\cup T\in\Delta(P)$, then as proven
above, $F_{T}\cap H\neq\emptyset$. This face is codimension-$(|T|+1)$.

Now we consider the facets of $Tr_{F_{S}}P$. These are of the form $F_{s}\cap
H_{\leq}$ for all facet indices $s\in\mathcal{S}$, and the facet $H\cap P$.
Each nonempty intersection of $k$ of these facets is codimension-$k$, meaning
that it is simple and its non-empty face poset is indeed isomorphic to its
dual simplicial complex. As a result, if we index faces of $Tr_{F_{S}}P$ as
$F^{\prime}_{T}=F_{T}\cap H_{\leq}$ and $F^{\prime}_{T\cup\\{h\\}}=F_{T}\cap
H$, we find that $\Delta(Tr_{F_{S}}P)$ is exactly equal to
$St_{S}(\Delta(P))$. ∎

We can understand the following theorem from [7] by remembering that
combinatorial blowups specialize to stellar subdivision, which we have just
proven is dual to truncation for simple polyhedra.

######  Theorem 2.3.10 ([7], Theorem 3.4).

Let $\mathcal{L}$ be a semilattice and let $G$ be a semilattice-building set
of $L$ with some chosen linear extension $G=\\{G_{1},\ldots,G_{t}\\}$, with
$G_{i}>G_{j}$ implying $i<j$. Let $\textrm{Bl}_{x}\mathcal{L}$ denote the
combinatorial blowup of $\mathcal{L}$ at element $x$. Let
$\textrm{Bl}_{k}\mathcal{L}$ denote the result of subsequent blowups
$\textrm{Bl}_{G_{k}}(\textrm{Bl}_{G_{k-1}}(\ldots\textrm{Bl}_{G_{1}}\mathcal{L}))$.
Then the final semilattice $\textrm{Bl}_{t}$ is equal to the face poset of the
semilattice-nested complex of $G$.

Note that one such linear extension can easily be found for a building set, by
ordering all elements in a building set by decreasing size. Applying this
theorem, and knowing that in this case combinatorial blowups are dual to
truncation, we prove the following.

######  Theorem 2.3.11.

For every $P$-building set $\mathcal{B}$, there exists a $P$-nestohedron of
$\mathcal{B}$ obtained by listing the elements
$\mathcal{B}=\\{S_{1},\ldots,S_{k}\\}$ such that $|S_{i}|\geq|S_{i+1}|$ for
all $i=1,\ldots,k-1$, and repeatedly truncating the faces
$F_{S_{1}},\ldots,F_{S_{k}}$ of $P$ in order.

###### Proof.

Define $\mathcal{B}_{0}=\\{\\{s\\}|s\in\mathcal{S}\\}$ for facet set
$\mathcal{S}$, and define
$\mathcal{B}_{i}=\mathcal{B}_{0}\cup\\{S_{1},\ldots,S_{i}\\}$. We note that
$P$ is the $P$-nestohedron of $\mathcal{B}_{0}$. Now we wish to prove that
$\textrm{Tr}_{F_{S_{i}}}\mathcal{K}_{P}\mathcal{B}_{i}$ is equal to
$\mathcal{K}_{P}\mathcal{B}_{i+1}$. Note that ordering $S_{1},\ldots,S_{k}$ by
size means that $S_{i}\supset S_{j}$ implies $i<j$, so Theorem 2.3.10 applies.
Because the stellar subdivision is dual to truncation, we find
$\Delta(\mathcal{K}_{P}\mathcal{B}_{i+1})$ is equal to the stellar subdivision
$\textrm{St}_{S_{i+1}}(\Delta(\mathcal{K}_{P}\mathcal{B}_{i}))$, which is
equal to the dual simplicial complex
$\Delta(\textrm{Tr}_{F_{S_{i+1}}}\mathcal{K}_{P}\mathcal{B}_{i})$. This proves
our theorem inductively. ∎

####  2.3.3 Faces of $\mathcal{P}$-nestohedra

Recall that we index facets of a simple polyhedron $P$ to be faces
$\\{F_{s}|s\in\mathcal{S}\\}$, and faces of $P$ are of the form
$F_{S}=\bigcap_{s\in S}F_{s}$ for $S\in\Delta(P)$. For a $P$-building set
$\mathcal{B}$, we note that $\Delta(\mathcal{K}_{P}\mathcal{B})$ is equal to
the nested complex $\mathcal{N}(\mathcal{B},P)$. As a result, we can index
faces of $\mathcal{K}_{P}\mathcal{B}$ with $\mathcal{B}$-nested sets, and
define $\Phi_{N}$ to be the face of $\mathcal{K}_{P}\mathcal{B}$ dual to the
nested set $N$.

We note some basic properties of faces of $\mathcal{K}_{P}\mathcal{B}$. We
find that the face $\Phi_{N}$ is codimension-$|N|$, which means that facets of
$\mathcal{K}_{P}\mathcal{B}$ are of the form $\Phi_{S}$, where
$S\in\mathcal{B}$. For two nested sets $N_{1},N_{2}$, we find that if
$N_{1}\cup N_{2}$ is $\mathcal{B}$-nested, then
$\Phi_{N_{1}}\cap\Phi_{N_{2}}=\Phi_{N_{1}\cup N_{2}}$, and otherwise
$\Phi_{N_{1}}\cap\Phi_{N_{2}}=\emptyset$.

We also note that the dual simplicial complex of a face $\Phi_{N}$ is
isomorphic to the link of $N$ in $\mathcal{N}(\mathcal{B},P)$. Proposition
2.1.17 characterizes links in nested sets as isomorphic to Cartesian products
of simplicial complexes, motivating us to find the following.

######  Proposition 2.3.12.

For two simple polyhedra $P$ and $Q$, the dual simplicial complex of the
Cartesian product $P\times Q$ is combinatorially equivalent to the Cartesian
product of $\Delta(P)$ and $\Delta(Q)$.

###### Proof.

The Cartesian product of two polyhedron is defined such that if
$x\in\mathbb{R}^{n}$ is a point in a polyhedron $P$, and $y\in\mathbb{R}^{m}$
is a point in polyhedron $Q$, then
$(x,y)=(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in\mathbb{R}^{n+m}$ is a point
in $P\times Q$.

Note that if $c(x,y)\leq b$ defines a face of $P\times Q$, then we can split
$c$ and $b$ to find new inequalities $c_{1}x\leq b_{1}$ and $c_{2}x\leq
b_{2}$. As a result, every face of $P\times Q$ is isomorphic to the product of
a face of $P$ and a face of $Q$. It is then trivial to prove that every
product of nonempty faces of $P$ and $Q$ is a face of $P\times Q$, and also
that each such product is unique. This applies to the dual simplicial
complexes as well. ∎

Note that if $\sum_{i=1}^{n}c_{i}x_{i}\leq b$ defines a facet of $P$ in
$\mathbb{R}^{n}$, then the same inequality defines a facet of $P\times Q$ in
$\mathbb{R}^{n+m}$. The facet set of $P\times Q$ can be indexed by the
disjoint union of the facet indexing sets of $P$ and $Q$.

The following is a result of Proposition 2.1.17 for the $\mathcal{P}$-building
set case.

######  Theorem 2.3.13.

For every $P$-nestohedron $\mathcal{K}_{P}\mathcal{B}$, every facet of
$\mathcal{K}_{P}\mathcal{B}$ is combinatorially isomorphic to the product of a
$F$-nestohedron, where $F$ is some face of $P$, and a simplex-nestohedron.

###### Proof.

Every facet of $\mathcal{K}_{P}\mathcal{B}$ is of the form $\Phi_{\\{S\\}}$
for some set $S\in\mathcal{B}$, and the dual complex of $\Phi_{\\{S\\}}$ is
equal to the link of $\\{S\\}$ in the nested complex of $\mathcal{B}$. Note,
though, that we have already characterized the link of $\\{S\\}$ to be
isomorphic to the Cartesian product of the nested complex
$\mathcal{N}(\mathcal{B}/S,\Delta(P))$ and the nested complex of the
restriction of $\mathcal{B}$ to the complex of proper subsets of $S$.

The link of the set $S$ in the dual complex of $P$ is the dual complex of the
face $F_{S}$, so $\mathcal{N}(\mathcal{B}/S,\Delta(P))$ is the dual complex of
an $F_{S}$-nestohedron. The complex of proper subsets of $S$ is the dual
simplicial complex of a simplex, and so the nested complex of the restriction
of $\mathcal{B}$ to this complex is the dual complex of a simplex-nestohedron.

We wish to make explicit that two edge cases, when $S$ is a singleton set or
when $\mathcal{B}/S$ is empty, are not issues with this definition.

First, we say that when a polyhedron $Q$ is a single point, $Q$ is a
$0$-dimensional simplex which contains one facet. The dual simplicial complex
of $Q$ only contains one set, the empty set, and is the proper set complex of
a singleton set. A building set on $Q$ is empty, and the nested complex is
empty. The nestohedron of a point is a point.

As a result, when $S$ is a singleton set, the set $\mathcal{B}$ restricted to
the proper subset complex of $S$ is empty, and the associated simplex
nestohedron is a point. When $\mathcal{B}/S$ is empty, the associated
$F$-nestohedron is a point. ∎

This theorem can be applied to all faces of $\mathcal{P}$-nestohedra.

######  Corollary 2.3.14.

For every $P$-nestohedron $\mathcal{K}_{P}\mathcal{B}$, every face of
$\mathcal{K}_{P}\mathcal{B}$ is combinatorially isomorphic to the product of a
$F$-nestohedron, where $F$ is some face of $P$, and a set of simplex-
nestohedra.

###### Proof.

See that $P$ is a face of $P$, so $\mathcal{K}_{P}\mathcal{B}$ is isomorphic
to the product of an $F$-nestohedron, where $F$ is some face of $P$, and an
empty set of simplex-nestohedra.

Every facet of a product of polyhedron $Q_{1}\times Q_{2}$ is isomorphic to
the product of $Q_{1}$ and a facet of $Q_{2}$, or vice versa. Every facet of a
simplex-nestohedron is the product of simplex-nestohedra. As a result, if $Q$
is the product of an $F$-nestohedron and a set of simplex-nestohedra, then
every facet of $Q$ is isomorphic to either an $F$-nestohedron and a set of
simplex-nestohedra, or an $F^{\prime}$-nestohedron and a set of simplex-
nestohedra, where $F^{\prime}$ is a facet of $F$.

Note that every proper face of a polyhedron can be expressed by repeatedly
taking facets of the polyhedron. As a result, this theorem is proven for every
face of $\mathcal{K}_{P}\mathcal{B}$ inductively. ∎

We can apply Proposition 2.2.14 to restate our theorem for $\mathcal{P}$-graph
associahedra.

######  Proposition 2.3.15.

Every facet $\Phi_{\\{t\\}}$ of a $P$-graph associahedron is combinatorially
isomorphic to the Cartesian product of the $F_{t}$-graph associahedron of the
graph $G/t$, and the simplex-graph associahedron of the graph $G|_{t}$ induced
by $t$ in $G$.

Unrelated to the main argument of this section, we note this result for two
disjoint polyhedra $P$ and $Q$.

######  Proposition 2.3.16.

Consider the case where $P,Q$ are simple polyhedra, with
$\mathcal{B}_{P},\mathcal{B}_{Q}$ a $P,Q$-building set respectively, and
disjoint facet-sets $\mathcal{S}_{P},\mathcal{S}_{Q}$. We find that the
$P\times Q$-nestohedron of $\mathcal{B}_{P}\cup\mathcal{B}_{Q}$ is equal to
the Cartesian product of the $P,Q$-nestohedra of $\mathcal{B}_{P}$ and
$\mathcal{B}_{Q}$.

d

###### Proof.

This is trivial; we simply note that if $N_{P}$ and $N_{Q}$ are
$\mathcal{B}_{P}$ and $\mathcal{B}_{Q}$-nested respectively, then $N_{P}\cup
N_{Q}$ is $\mathcal{B}_{P}\cup\mathcal{B}_{Q}$-nested, and any
$\mathcal{B}_{P}\cup\mathcal{B}_{Q}$-nested set $N$ can be decomposed in this
manner. ∎

Note that this proves that every product of $\mathcal{P}$-nestohedra is itself
a $\mathcal{P}$-nestohedron. However, it is not always the case that a
$P\times Q$-nestohedron can be written as a product of a $P$-nestohedron and a
$Q$-nestohedron; this depends on the building set of the $P\times
Q$-nestohedron.

####  2.3.4 Classical nestohedra and simplex nestohedra

The paper [13] provides a definition for _nestohedra_ , _building sets_ , and
_nested complexes_ in set-theoretic terms which closely parallel Definition
2.1.6. We will restate these definitions here, and explain their relationship
to simplex-nestohedra. Throughout this thesis, we refer to these terms as
classical building sets, classical nestohedra, and so forth to avoid
confusion.

######  Definition 2.3.17.

A classical building set $B$ of a set $S$ is any subset $B$ of the power set
of $S$, satisfying the conditions

  1. 1.

For each element $i\in S$, $\\{i\\}\in B$

  2. 2.

If $I\in B,J\in B$ and $I\cap J\neq\emptyset$, then $I\cup J\in B$.

######  Proposition 2.3.18.

There exists a unique set $B_{max}\subseteq B$ such that:

  1. 1.

$B_{max}$ is a partition of $S$

  2. 2.

For each set $I\in B_{max}$, $I$ is not a proper subset of any set in $B$.

Sets in $B_{max}$ are referred to as connected components of $B$, and a
classical building set $B$ on set $S$ is _connected_ if $B_{max}=\\{S\\}$.

######  Definition 2.3.19.

A _classical nested set_ $N$ is any subset of a classical building set $B$
such that

  1. 1.

$B_{max}\subseteq N$

  2. 2.

For any two sets $I,J\in N$, we find $I\subseteq J$, $J\subseteq I$, or $I,J$
are disjoint

  3. 3.

For any set of $k$ disjoint sets $I_{1},\ldots,I_{k}\in N$, $k\geq 2$, we find
$\bigcup_{i=1}^{k}I_{i}$ is not in $B$.

The collection of sets of the form $N\backslash B_{max}$, where $N$ is
$B$-nested, is a simplicial complex, which we call the _nested complex_ of
$B$.

######  Definition 2.3.20.

A _classical nestohedron_ of a classical building set $B$ is a simple
polyhedron whose dual simplicial complex is isomorphic to the nested complex
of $B$.

With these definitions restated for this thesis, we can prove the following
statement about classical nested complexes.

######  Proposition 2.3.21.

The nested complex of a classical building set $B$ with
$B_{max}=\\{S_{1},\ldots,S_{k}\\}$ is equal to the Cartesian product of nested
complexes $\mathcal{N}(\mathcal{B}_{i},\Delta_{i})$, where $\Delta_{i}$ is the
proper subset complex of $S_{i}$, and $\mathcal{B}_{i}$ is the
$\Delta_{i}$-building set defined by restricting $B$ to $\Delta_{i}$.

###### Proof.

Consider the case where $B_{max}$ contains only the base set $S$ of $B$. Write
$\mathcal{B}=B\backslash\\{S\\}$. We see that for sets $I,J\in B$ with
$I\subset S,J\subset S$ and $I\cap J\neq\emptyset$ that $I\cup
J\in\mathcal{B}$ if and only if $I\cup J\neq S$. This corresponds to the
$\Delta$-building set definition if $\Delta$ is the proper subset complex of
$S$. As a result, $B$ is a classical building set if and only if $\mathcal{B}$
is a simplex-building set. It is then trivial to show that in this case, a set
$N$ containing $S$ is $\mathcal{B}$-nested if and only if $N\backslash\\{S\\}$
is $B$-nested.

In the case where $B_{max}=\\{S_{1},\ldots,S_{k}\\}$ with $k\geq 2$, define
$\Delta=\prod_{i=1}^{k}\Delta_{i}$, where $\Delta_{i}$ is the proper subset
complex of $S_{i}$. Define $\mathcal{B}_{i}$ as $B$ restricted to
$\Delta_{i}$. It is then trivial to see that each building set $B$ decomposes
into $B_{max}$ and a set of smaller building sets, and that each nested
complex $N$ can be decomposed into the union of $B_{max}$ and a series of
$\Delta_{i}$-nested sets $N_{i}$ of $\mathcal{B}_{i}$ for each $i\in[k]$. ∎

As an immediate consequence of Proposition 2.3.21, we obtain the following
statement about nestohedra.

######  Proposition 2.3.22.

A polyhedron is a classical nestohedron if and only if it is combinatorially
isomorphic to the Cartesian product of a set of simplex-nestohedra.

We also note the following as a result of Proposition 2.3.16.

######  Proposition 2.3.23.

The nestohedron of a classical building set $B$ with
$B_{max}=\\{S_{1},\ldots,S_{k}\\}$ is isomorphic to the $P$-nestohedron of
$\mathcal{B}$, where $\mathcal{B}=B\backslash B_{max}$, and
$P=\prod_{i=1}^{k}D_{i}$, where $D_{i}$ is the simplex with facet set $S_{i}$.

######  Remark 2.3.24.

It should also be noted that every classical nestohedron on $S$ with building
set $B$ is combinatorially isomorphic to a face of a $P$-nestohedron with
building set $B$, where $P$ is a simplicial cone isomorphic to the product of
$|S|$ rays. This is the construction one achieves when one does not require
the set $B_{max}$ to be contained as as subset of every $B$-nested set.
Combinatorially, this structure is not much more interesting than the
nestohedron, and we note that this cone-nestohedron is isomorphic to the
product of the classical nestohedron $\mathcal{K}_{B}$ times the product of
$|B_{max}|$ rays.

We can now focus on defining classical graph associahedra. Graph associahedra
are mentioned as a special case of nestohedra in [13], and are studied in
great depth in [5]. It is important to note here that two slightly different
definitions of graph associahedra exist in the literature. When $G$ is a
connected graph, the two definitions are equivalent, but when $G$ is not
connected, the two are different, although both are nestohedra. Many papers
elide the issue by focusing on the case where a graph is connected. Throughout
this paper, the relevant definition is Definition 2.3.25, as these classical
graph associahedra are isomorphic to simplex-graph associahedra.

Once we have proven that these graph associahedra are in fact simplex-graph
associahedra, we will use the term simplex-graph associahedron over graph
associahedron to avoid confusion.

The following definition is equivalent to the one defined in [5]

######  Definition 2.3.25.

A _classical graph associahedron_ of a graph $G$ on set $S$ is a nestohedron
whose building set $B$ contains all proper vertex sets of $G$ which induce
connected subgraphs, as well as the entire vertex set of $G$.

######  Proposition 2.3.26.

The classical graph associahedron of a graph $G$ is equal to the simplex-graph
associahedron of $G$.

###### Proof.

We have already established a bijection between simplex-nestohedra and
nestohedra for which $B_{max}$ contains an entire base set. As a result, we
see that a simplex-graph associahedron is a nestohedron whose building set $B$
contains all proper vertex sets of $G$ which induce connected subgraphs, as
well as the entire vertex set of $G$. ∎

We can define an alternate nestohedron whose building set only contains graph
tubes. This is the definition of graph associahedra presented in [13].

######  Definition 2.3.27.

The _component-product classical graph associahedron_ of a graph $G$ on vertex
set $\mathcal{S}$ is the nestohedron whose building set $B$ contains all
subsets of $\mathcal{S}$ which induce connected subgraphs of $G$.

When $G$ is not connected, $G$ is the product of the simplex-graph
associahedra of each component subgraph of $G$, and will be lower-dimensional
than the simplex-graph associahedron of $G$. We should note that this graph
associahedron is less relevant to the research in this paper than the
classical graph associahedron; in general, when we present an unconnected
$\mathcal{P}$-graph, we do not expect $\mathcal{P}$-graph associahedra in
general to be isomorphic to a product of $\mathcal{P}$-graph associahedra of
component graphs.

####  2.3.5 Forbidden Subset Diagrams

Simplicial complexes can be defined in multiple ways. Given a base set
$\mathcal{S}$ and a collection of subsets $S_{1},\ldots,S_{k}$ of
$\mathcal{S}$. We say that the _forbidden subsets_ $S_{1},\ldots,S_{k}$ define
a simplicial complex $\Delta$ consisting of all subsets $J$ of $\mathcal{S}$
such that $S_{i}\not\subseteq J$ for each $1\leq i\leq k$.

Note that it is possible for two sets of forbidden subsets to define the same
simplicial complex. However, for any simplicial complex $\Delta$, there is a
unique minimal set of forbidden subsets required to define $\Delta$. A set of
forbidden subsets is minimal if and only if no two forbidden subsets are
incomparable. We can call the minimal set of forbidden subsets defining
$\Delta$ the _circuit set_ of $\Delta$. Every set of forbidden subsets can be
turned into a circuit set by removing any subsets contained in other forbidden
subsets.

A _forbidden subset diagram_ is a hypergraph on a vertex set $\mathcal{S}$,
whose edges are forbidden subsets. It is drawn with dashed edges connecting
faces of two elements, and dashed shapes drawn around forbidden subsets
containing more than 2 vertices, as in Figure 2.2.

Figure 2.2: A forbidden subset diagram on the left, and the equivalent
simplicial complex on the right.

We refer to the forbidden subset diagram of the dual simplicial complex of a
simple polyhedron as the forbidden subset diagram of that polyhedron. Figure
2.3 illustrates several low-dimensional examples. The forbidden subset diagram
of a single ray is a graph containing one vertex and no edges. The forbidden
subset diagram of a simplex on two vertices is a graph on two vertices with a
single dashed edge, and the forbidden subset diagram of a simplex on $n$
vertices is a graph on $n$ vertices with a forbidden subset containing the
entire graph.

Figure 2.3: Simple polyhedra, and their forbidden subset diagrams below.

The following proposition is a trivial result from Proposition 2.3.12:

######  Proposition 2.3.28.

For two simple polyhedra $P_{1},P_{2}$, the forbidden subset diagram of their
Cartesian product, $P_{1}+P_{2}$, is equal to the disjoint union of the
forbidden subset diagrams of $P_{1}$ and $P_{2}$.

With this, we can very easily characterize the forbidden subset diagrams of
Cartesian products of rays and simplices, especially 1-simplices whose
forbidden subsets are dashed edges. Chapter 4 characterizes hypercube-graph
associahedra using forbidden subset diagrams, and Chapter 6 includes several
cases, such as the Double Path Graph or Twisted Cycle Graph, whose facial
enumeration requires enumeration of faces of $P$-graph associahedra where $P$
is the product of a hypercube and a set of rays. However, we note that a more
fleshed-out theory of $\mathcal{P}$-graph associahedra is outside of the scope
of this thesis.

###  2.4 Graphic matroid and edge-tubing complexes

One interesting application of $\Delta$-graph tubings is the theory of edge-
tubings, or subtree tubings, presented here. Consider a graph $G=(V,E)$
consisting of vertex set $V$ and edge set $E$. Two edges $e_{1},e_{2}$ are
_adjacent_ if they share a vertex. The _graphic matroid_ is the simplicial
complex $M_{G}$ with base set $E$ such that $E^{\prime}\subseteq E$ is in
$M_{G}$ if $(V,E^{\prime})$ contains no cycles. These sets are called the
_independent sets_ of the matroid $M_{G}$. The _line graph_ of a graph
$G=(V,E)$ is the graph $L(G)=(E,E_{adj})$, where $\\{e_{1},e_{2}\\}$ is an
edge in $E_{adj}$ if edges $e_{1},e_{2}\in E$ share a vertex in $G$.

A _subtree_ of a graph $G$ is a collection of edges in $G$ which form a tree.

Given a subtree consisting of edges
$e_{1}=\\{u_{1},v_{1}\\},\ldots,e_{k}=\\{u_{k},v_{k}\\}$, the vertex set of
that subtree is the set $e_{1}\cup\cdots\cup e_{k}$, which is a subset of the
vertex set $V$.

######  Definition 2.4.1.

Two subtrees $t_{1},t_{2}$ of a graph $G$ are compatible if and only if
$t_{1}\subseteq t_{2},t_{2}\subseteq t_{1}$, or the vertex sets of
$t_{1},t_{2}$ are disjoint.

######  Proposition 2.4.2.

Given a graph $G$, the simplicial complex of pairwise-compatible subtrees of
$G$ is equal to the tubing complex $\mathcal{N}(L(G),M_{G})$.

###### Proof.

Consider a set $t$ of edges
$e_{1}=\\{u_{1},v_{1}\\},\ldots,e_{k}=\\{u_{k},v_{k}\\}$ of $G$. We note that
$t$ induces a connected subgraph of $L(G)$ if and only if $t$ is connected in
$G$. We also note that $t$ is cycle-free if and only if $t$ is an independent
set in $M_{G}$. As a result, we find a set of edges is a subtree of $G$ if and
only if it is a tube of the $M_{G}$-graph $L(G)$.

Now we consider weak compatibility rules. We need to show that $t_{1},t_{2}$
are compatible subtree if and only if they are weakly compatible tubes in
$L(G)$. This is true in the case that $t_{1}\subseteq t_{2}$ or vice-versa.
Now we note that two edges $e_{1},e_{2}$ in $G$ have disjoint vertex sets if
and only if there is no edge in $L(G)$ connecting the nodes $e_{1},e_{2}$.
From there, we see that two compatible disjoint subtrees have no shared
vertices in their vertex sets if and only if $t_{1}$ and $t_{2}$ in $L(G)$ are
not adjacent, and the subtrees $t_{1},t_{2}$ are compatible as subtrees if and
only if they are weakly compatible as tubes of $L(G)$.

Finally, we note that any union of subtrees with disjoint vertex sets cannot
contain a cycle, and so any collection of weakly compatible tubes cannot have
a union not in $L(G)$. As a result, a collection of subtrees is pairwise
compatible in $G$ if and only if it is a tubing of $L(G)$ in $M_{G}$, proving
our proposition. ∎

Call these tubings _subtree tubings_ of $G$. Figure 2.4 shows a collection of
subtree-tubings for a given graph, with subtrees drawn bold and in color. Note
that the edges $abc$ do not form a subtree, and as a result do not form a tube
in the $M_{G}$-graph $L(G)$.

Figure 2.4: An example graph (top left), its line graph (top right), and two
subtree tubings with accompanying tubings in the line graph.

We can draw subtree tubings similarly to standard tubings, by drawing shapes
around edges instead of vertices. Figure 2.5 shows a subtree tubing of a cycle
on four vertices, and the corresponding graph tubing of its line-graph.

Figure 2.5: subtree tubing of a cycle and its corresponding line-graph tubing.

We are not familiar with any literature which describes these tubings.
Clearly, when $G$ is a tree, $M_{G}$ is a Boolean lattice, and the set of
subtree-tubings containing the entire graph $G$ is just equal to the classical
graph tubing complex of $L(G)$; as a result, the graph associahedron of the
line graph of a tree is connected to the subtree-tubing complex of that tree.
Otherwise, we have not found these simplicial complexes in other contexts.

##  Chapter 3 Normal fans of $\mathcal{P}$-nestohedra

This chapter explores the normal fans of $\mathcal{P}$-nestohedra, in large
part by restating results regarding preposets and the normal fans of classical
nestohedra, and extending them to the $\Delta$-nested complex and
$\mathcal{P}$-nestohedron cases. We start by describing preposets and braid
cones in Sections 3.1 and 3.2, describing existing results but providing an
explicit realization of braid cones and focusing on preposets and braid cones
defined by nested sets. We then introduce two new constructions, facial
preposets and $\Delta$-braid cones, in Section 3.3, which allow us to define
fans from nested complexes. Section 3.4 finds a way to define these nested
complex fans as the coarsest common refinements of a set of simpler fans, and
Section 3.5 characterizes nested complex fans as coarsenings of the
barycentric subdivision of the fan of a simplicial complex. Finally, all of
this comes together in Section 3.6 to characterize the normal fans of
$\mathcal{P}$-nestohedra.

###  3.1 Preposets

A _binary relation_ $R$ on a set $S$ is a subset $R\subseteq S\times S$. A
_preposet_ is a reflexive and transitive binary relation. This means that
$(x,x)\in R$ for all $x\in S$, and if $(x,y),(y,z)\in R$, then $(x,z)\in R$.
We will use the notation $x\preceq_{R}y$ to denote that $(x,y)\in R$.

An _equivalence relation_ $\equiv$ is a binary relation that is reflexive,
symmetric, and transitive. Every preposet $Q$ defines an equivalence relation,
defined such that $x\equiv_{Q}y$ if and only if $x\preceq_{Q}y$ and
$y\preceq_{Q}x$. We can define a _poset_ as a preposet whose equivalence
relation divides a set into singleton equivalence classes. Every preposet $Q$
gives rise to a poset $Q/\equiv_{Q}$ on the equivalence classes of
$S/\equiv_{Q}$.

Given two binary relations $R_{1},R_{2}$ on a set $S$, let $R_{1}\subseteq
R_{2}$ denote containment as subsets of $S\times S$, and let $R_{1}\cup R_{2}$
be the union of the two relations. If $R$ is a reflexive binary relation,
define $\overline{R}$ to be the smallest preposet such that
$R\subseteq\overline{R}$. We can call this the _transitive closure_ of $R$.

For preposets $P,Q$ on the same set $S$, note that the binary relation $P\cup
Q$ is not necessarily a preposet. We note however that $\overline{P\cup Q}$
is.

A _cover relation_ in a preposet $Q$ is a special pair $x\lessdot_{Q}y$ such
that $x\preceq_{Q}y$ and there exists no element $z$ such that
$x\prec_{Q}z\prec_{Q}y$. The _Hasse diagram_ of a poset is an oriented graph
on a poset whose edges are cover relations. The Hasse diagram of a preposet
$Q$ is the Hasse diagram of the poset $Q/\equiv_{Q}$.

Let $R^{op}$ be the _opposite_ of a binary relation $R$, such that
$x\preceq_{R}y$ if and only if $y\preceq_{R^{op}}x$.

For two preposets $P$ and $Q$ on the same set, let us say that $Q$ is a
_contraction_ of $P$ if there is a binary relation $R\subseteq P$ such that
$Q=\overline{P\cup R^{op}}$. In other words, there is a way to obtain $Q$ from
$P$ by merging certain equivalence classes in $P$ along relations in $P$,
typically cover relations.

A preposet is a tree if its Hasse diagram is a tree. A preposet $Q$ is a
_rooted tree_ if it is a tree, and for every equivalence class $I\in
Q/\equiv_{Q}$, there is at most one set $J\in Q/\equiv_{Q}$ such that
$I\preceq_{Q/\equiv_{Q}}J$. A forest is a preposet whose connected components
are trees.

An _order ideal_ of a preposet $Q$ is a set $I$ such that, for $x,y\in Q$, if
$x\preceq_{Q}y$ and $y\in I$, then $x\in I$.

###  3.2 Preposets of classical nested sets and braid cones

Section 3 of [12] outlines a bijection between preposets and braid cones.
Braid cones are crucial to the study of generalized permutohedra, of which
nestohedra are one example. In this section we will restate definitions and
results for braid cones, before using them to define a generalization which we
call _$\Delta$ -braid cones_ or $\mathcal{P}$-braid cones.

####  3.2.1 Preposets of classical nested sets

A _principal order ideal_ of a preposet $Q$ on vertex set $\mathcal{S}$ is an
order ideal of the form ${I_{y}=\\{x\in\mathcal{S}|x\preceq_{Q}y\\}}$. The
_principal order ideal poset_ of $Q$ is the collection of principal order
ideals for all $y\in\mathcal{S}$ ordered by inclusion. For any preposet $Q$,
the principal order ideal poset is isomorphic to the poset $Q/\equiv_{Q}$.

######  Definition 3.2.1.

For a set $N$ containing subsets of a base set $\mathcal{S}$, define a binary
relation $P_{N}$ on the base set $\mathcal{S}$, such that $i\preceq j$ if and
only if every set $I\in N$ that contains $j$ also contains $i$.

We note that for a general set $N$ of subsets of a base set $\mathcal{S}$,
this preposet is not unique and may not reflect all the structure of $N$. For
example, if $N=\\{\\{1,2\\},\\{2,3\\},\\{1,3\\}\\}$ and
$\mathcal{S}=\\{1,2,3\\}$, then $P_{N}$ is the empty preposet on
$\mathcal{S}$. However, when $N$ is a nested set, we can define $P_{N}$ more
concretely. Consider a classical building set $B$ on vertex set $\mathcal{S}$
and a $B$-nested set $N$. Remember that each classical nested set contains
$B_{max}$ as a subset, so every vertex $i\in\mathcal{S}$ is contained in at
least one set in $N$. For every element $i\in\mathcal{S}$, if $i\in I$ and
$i\in J$ for $I,J\in N$, then the two sets cannot be disjoint or have
nontrivial intersection, so either $I\subseteq J$ or $J\subseteq I$. As a
result, for each element $i\in\mathcal{S}$, there is a unique smallest set
$I_{i}\in N$ which contains $i$. The preposet $P_{N}$ can also be
characterized in terms of these sets as follows.

######  Proposition 3.2.2.

For a classical $B$-nested set $N$ where $B$ has base set $\mathcal{S}$, the
preposet $P_{N}$ is equal to the preposet on the base set $\mathcal{S}$ such
that for any two elements $i,j\in\mathcal{S}$, $i\preceq j$ if and only if
$I_{i}\subseteq I_{j}$.

We can note that every set $I_{i}$ in $N$ is a principal order ideal of
$P_{N}$, and we can state the following.

######  Proposition 3.2.3.

For any classical nested set $N$, $N$ is the set of principal order ideals of
$P_{N}$.

Figure 3.1 shows a classical nested set $N$ on the set $\\{1,2,3,4\\}$, and
the resulting preposet $P_{N}$. For any classical $B$-nested set $N$, the
preposet $P_{N}$ is a forest of rooted trees. Each component of this preposet
is a rooted tree on a subset of $B_{max}$.

Figure 3.1: A graph tubing and its associated preposet

####  3.2.2 Defining braid cones

The foundational text on braid cones and faces of generalized permutohedra is
[12]. This subsection restates basic findings from this paper, and Section 3.3
of this thesis adapts their work to $\Delta$-braid cones.

For a finite set $\mathcal{S}$, define the vector space
$\mathbb{R}^{\mathcal{S}}$ to be the $|\mathcal{S}|$-dimensional vector space
with basis vectors $\\{e_{i}|i\in\mathcal{S}\\}$. A vector
$x\in\mathbb{R}^{\mathcal{S}}$ contains components $x_{i}$ for
$i\in\mathcal{S}$. Define the vector
$(1,\ldots,1)=\sum_{i\in\mathcal{S}}e_{i}$. If $|\mathcal{S}|\geq 1$, we
define the vector space $\mathbb{R}^{\mathcal{S}}/(1,\ldots,1)$ to be the set
of equivalence classes of $\mathbb{R}^{\mathcal{S}}$ modulo $(1,\ldots,1)$. We
write the equivalence class of a vector $x\in\mathbb{R}^{\mathcal{S}}$ as
$[x]$, taking care not to confuse this notation with $[n]$ for integers. We
note that comparison of components within one vector is well-defined on these
equivalence classes; that is, if $[x]=[x^{\prime}]$, then $x_{i}\leq x_{j}$ if
and only if $x_{i}^{\prime}\leq x_{j}^{\prime}$ for any $i,j$ in $[n+1]$. It
also holds that $x_{i}-x_{j}=x_{i}^{\prime}-x_{j}^{\prime}$. We note that any
$(|\mathcal{S}|-1)$ elements of $\mathcal{S}$ define a basis of
$\mathbb{R}^{\mathcal{S}}$, and $\sum_{i\in\mathcal{S}}[e_{i}]=0$.

A _cone_ in a vector space is any set that is closed under addition and
multiplication by a nonnegative scalar. Polyhedral cones are cones that are
polyhedra. Polyhedral cones can also be defined as any set in a vector space
defined by a finite set of homogeneous linear inequalities of the form $ax\leq
0$. A polyhedron is _pointed_ if it contains a vertex face, which for cones
must be the origin of the vector space. Non-polyhedral cones exist, but are
not covered in this thesis, and we will assume from here that any cone
mentioned is a polyhedral cone.

The _braid arrangement_ on a set $\mathcal{S}$ is the arrangement of
hyperplanes in $\mathbb{R}^{\mathcal{S}}/(1,\ldots,1)$ defined by equalities
of the form $x_{i}-x_{j}=0$ for $i\neq j$ in $\mathcal{S}$. When
$\mathcal{S}=[n+1]$, this is the _$n$ -dimensional braid arrangement_, and
these hyperplanes divide the space into cones of the form

$C_{\sigma}=\\{x_{\sigma(1)}\leq x_{\sigma(2)}\leq\cdots\leq
x_{\sigma(n+1)}\\}$

where $\sigma$ is a permutation $\sigma\in\mathfrak{S}_{n+1}$. These cones are
called _Weyl chambers_ of the type $A_{n}$ Coxeter group.

######  Definition 3.2.4.

Given a preposet $Q$ on $\mathcal{S}$, define the _braid cone_ $K_{Q}$ of $Q$
as the cone in the space $\mathbb{R}^{\mathcal{S}}/(1,\ldots,1)\mathbb{R}$
defined by inequalities $x_{i}\leq x_{j}$ for each relation $i\preceq_{Q}j$ in
$Q$.

The following proposition is a rephrasing of [12, Proposition 3.5] in the
notation used in this thesis.

######  Proposition 3.2.5.

Given two preposets $Q,Q^{\prime}$ on $\mathcal{S}$:

  1. 1.

$K_{\overline{Q\cup Q^{\prime}}}=K_{Q}\cap K_{Q^{\prime}}$.

  2. 2.

The preposet $Q$ is a contraction of $Q^{\prime}$ if and only if $K_{Q}$ is a
face of $K_{Q^{\prime}}$.

  3. 3.

$Q$ is a poset if and only if $K_{Q}$ is full-dimensional, i.e.,
$(|\mathcal{S}|-1)$-dimensional.

  4. 4.

The linear span of $K_{Q}$ is the cone $K_{\equiv_{Q}}$, where the equivalence
relation $\equiv_{Q}$ is considered a preposet, and $K_{\equiv_{Q}}$ is the
subspace defined by equations $x_{i}=x_{j}$ if $i\equiv_{Q}j$.

  5. 5.

The cone $K_{Q/\equiv_{Q}}$ is isomorphic to $K_{Q}$.

  6. 6.

$K_{Q}$ is pointed if and only if $Q$ is connected, i.e., the Hasse diagram of
$Q$ is a connected graph.

  7. 7.

If $Q$ is a poset, then the minimal set of inequalities describing $K_{Q}$ is
$\\{x_{i}\leq x_{j}|i\lessdot_{Q}j\\}$.

  8. 8.

The Hasse diagram of $Q$ is a tree if and only if $\sigma$ is a full-
dimensional simplicial cone.

  9. 9.

When $\mathcal{S}=[n+1]$, for $\sigma\in\mathfrak{S}_{n+1}$, the cone $K_{Q}$
contains the Weyl chamber $C_{\sigma}$ if and only if $Q$ is a poset and
$\sigma$ is its linear extension, that is
$\sigma(1)\prec_{Q}\cdots\prec_{Q}\sigma(n+1)$.

Recalling that $Q/\equiv_{Q}$ is a poset, we can state a corollary to
statements 3 and 5.

######  Corollary 3.2.6.

If the preposet $Q$ has $k+1$ equivalence classes then the cone $K_{Q}$ is
$k$-dimensional.

This comes from the fact that $K_{\equiv_{Q}}$ is a $k$-dimensional space, and
$K_{Q\equiv_{Q}}$ is full-dimensional in that space, and isomorphic to
$K_{Q}$.

For a classical nested set $N$, define the notation $K_{N}=K_{P_{N}}$.

The following is a result from [12].

######  Proposition 3.2.7.

For a classical building set $B$, the set of cones $K_{N}$ such that $N$ is
$B$-nested forms a fan, and the face poset of this fan is isomorphic to the
nested complex of $B$.

This fan is the normal fan of a classical $B$-nestohedron constructed by
Minkowski sums of simplices as described in [13]. We note that for two
$B$-nested sets, $K_{N}\cap K_{N^{\prime}}=K_{N\cap N^{\prime}}$. In addition,
the three statements are equivalent: $K_{N}\subseteq K_{N^{\prime}}$, $K_{N}$
is a face of $K_{N^{\prime}}$, and $N\subseteq N^{\prime}$.

####  3.2.3 Expressing braid cones as conic hulls of their rays

Define the _conic hull_ $\operatorname{Cone}V$ of a set of vectors
$V=\\{v_{s}|s\in S\\}$ indexed by some set $S$ to be the set of finite sums of
the form $\sum_{s\in S}a_{s}v_{s}$, where $a_{s}\geq 0$ for each $s\in S$. The
conic hull of a single nonzero vector is a one-dimensional pointed cone,
called a _ray_ , and the conic hull of a cone is itself. Polyhedral cones are
exactly the cones that can be defined as conic hulls of a finite set of
vectors. When a polyhedral cone is pointed, it is equal to the conic hull of a
set of vectors $v_{1},\ldots,v_{k}$, such that each vector $v_{i}$ is
contained in the interior of a ray face of the cone.

Every polyhedral cone is equal to the conic hull of a set of vectors, and
every polyhedral pointed cone is equal to the conic hull of a set of vectors
containing one vector in each ray face of the cone.

######  Definition 3.2.8.

A _ray preposet_ is a preposet $R$ containing two equivalence classes: a
_lower class_ , and an _upper class_ , such that $i\prec j$ for all $i$ in the
lower class and $j$ in the upper class of $R$.

We know from Proposition 3.2.5 that the cone $K_{Q}$ is pointed if and only if
$Q$ is connected, and $K_{Q}$ is one-dimensional if and only if it is a
preposet with 2 equivalence classes, so we can see $K_{Q}$ is a ray if and
only if $Q$ is a ray preposet.

A _ray contraction_ of a preposet $Q$ is a ray preposet which is a contraction
of $Q$. Ray contractions are obtained by contracting edges one-by-one in the
Hasse diagram of a preposet until only one edge remains. Note that in general,
there is not a bijection between edges in the Hasse diagram and rays of a
preposet cone; Figure 3.2 illustrates two possible ray contractions which
arise from leaving one edge alone and contracting the rest of the edges. The
choice and order of edge contraction generally matters.

In general, we can characterize braid cones as follows.

######  Proposition 3.2.9.

Given a connected preposet $Q$ on a set $S$, the cone $K_{Q}$ is equal to the
conic hull of the rays of the form $K_{R}$, where $R$ is a ray contraction of
$Q$.

###### Proof.

From Proposition 3.2.5, we know from statement 6 that connected preposets have
pointed cones, and pointed hulls are equal to the conic hulls of ray faces.
From statement 2, we know that all faces of a cone $K_{Q}$ are cones of the
face $K_{Q^{\prime}}$ where $Q^{\prime}$ is a contraction of $Q$, and we know
a cone $K_{Q^{\prime}}$ is a ray if and only if $Q^{\prime}$ is a ray
preposet, so $K_{Q}$ is equal to the conic hull of all rays of the form
$K_{R}$, where $R$ is a ray contraction of $Q$. ∎

Figure 3.2: Contracting until no dashed edges remain leads to two possible ray
contractions.

When the Hasse diagram of a preposet $Q$ is a connected tree, edge contraction
order does not matter, and ray contractions are in bijection with individual
edges of the Hasse diagram. When $Q$ is also a rooted tree, then it is even
simpler to characterize the ray contractions of $Q$.

######  Proposition 3.2.10.

If the preposet $Q$ on base set $\mathcal{S}$ is a rooted tree, then $R$ is a
ray contraction of $Q$ if and only if the lower class of $R$ is the principal
order ideal of a non-maximal element in $Q$.

######  Lemma 3.2.11.

For any ray preposet $R$ with lower class $I$, $K_{R}$ is the conic hull of
the vector $\sum_{i\in I}[-e_{i}]$.

###### Proof.

Write $v=\sum_{i\in I}[-e_{i}]$. This is the equivalence class of the vector
$x$ in $\mathbb{R}^{\mathcal{S}}$ with $x_{i}=0$ if $i\notin I$ and $x_{i}=-1$
if $i\in I$. We note then that $v_{i}=v_{j}$ if $i,j\in I$ or $i,j\notin I$,
and $v_{i}<v_{j}$ if $i\in I,j\notin I$. These are then exactly the conditions
regarding whether or not $i\equiv_{R}j$ or $i<_{R}j$ in $R$. As a result,
$v_{i}\leq v_{j}$ if and only if $i\leq_{R}j$. This means that $v$ is in the
interior of $K_{R}$, and as $K_{R}$ is a ray, this proves $K_{R}$ is equal to
the conic hull of $v$. ∎

######  Definition 3.2.12.

Given a preposet $Q$ on a set $S$, the _principal order ideal vector_ of an
element $j\in S$ is the sum

$w_{j}^{Q}=\sum_{i\preceq_{q}j}[-e_{i}]$

######  Proposition 3.2.13.

If $P/\equiv_{P}$ is a rooted tree on base set $\mathcal{S}$, then the cone
$K_{P}$ is the conic hull of principal order ideal vectors $w_{i}^{P}$ for all
$i\in\mathcal{S}$.

###### Proof.

Recall that $K_{P}$ is equal to the conic hull of all cones of the form
$K_{R}$, where $R$ is a ray contraction of $P$. Because $P$ is a rooted tree,
the only ray contractions of $P$ are those which have lower class $I_{i}$,
where $I_{i}$ is the principal order ideal of some non-maximal element
$i\in\mathcal{S}$. As a result, if $i$ is a non-maximal element in $P$, and
$R$ is a ray contraction with lower class $I_{i}$, then $K_{R}$ is equal to
the conic hull of the vector $w_{i}^{P}$.

As a result, $K_{P}$ is equal to the conic hull of principal order ideal
vectors $w_{i}^{P}$ for all non-maximal elements $i\in P$. When $m$ is a
maximal element in $P$, we find that $w_{m}^{P}=\sum_{j\in S}[-e_{j}]$. As a
result, $w_{m}^{P}\equiv 0$, and $K_{P}$ is equal to the conic hull of all
vectors $w_{i}^{P}$ for $i\in\mathcal{S}$. ∎

In the special case where $N$ is a classical nested set of $B$ with
$|B_{max}|=1$, Proposition 3.2.3 states that the sets of $N$ are exactly the
principal order ideals of the preposet $P_{N}$. We note that $P_{N}$ is a
rooted tree, so Proposition 3.2.13 implies the following:

######  Proposition 3.2.14.

For a nested set $N$ of a connected classical nested set $B$, the cone $K_{N}$
is equal to ${\operatorname{Cone}\\{\sum_{i\in I}[-e_{i}]|I\in N\\}}$.

###  3.3 Facial Preposets, $\Delta$-nested sets, and $\Delta$-braid cones

This material was motivated by the desire to characterize the normal fans of
$\mathcal{P}$-nestohedra in a manner analogous to the normal fans of classical
nestohedra. Speaking informally, the normal fan of a $\mathcal{P}$-nestohedron
looks like portions of the normal fans of classical nestohedra, stitched
together. When two nested sets share the same support, the related cones in
the normal fan behave very similarly to the braid cones of the related
classical nested sets. However, we need to be able to manage the fact that two
$\mathcal{B}$-nested sets for a $\Delta$-building set $\mathcal{B}$ will
likely not have the same support. If we want a set of propositions similar to
Proposition 3.2.5 for $\Delta$-braid cones, we will need to deal with the fact
that preposets defined from $\mathcal{B}$-nested sets should have the same
support so that contractions and unions of preposets are well-defined, which
leads us to the decision to define facial preposets the way we do in the
following subsection.

####  3.3.1 Introducing facial preposets

Consider a simplicial complex $\Delta$ with base set $S$. We introduce an
element $\infty$, and if $Q$ is a preposet on $\mathcal{S}\cup\\{\infty\\}$,
then define the _finite elements_ of $Q$ to be the elements
$\\{x\in\mathcal{S}|x\prec_{Q}\infty\\}$, and the _infinite elements_ to be
the elements $\\{x\in\mathcal{S}|x\equiv_{Q}\infty\\}$. Now define
$Q_{finite}$ to be the preposet on the finite elements of $Q$, ordered by
$\preceq_{Q}$.

######  Definition 3.3.1.

Given a simplicial complex $\Delta$ on base set $\mathcal{S}$, a _facial
preposet_ of $\Delta$ is a preposet on $\mathcal{S}\cup\\{\infty\\}$ if
$x\preceq_{Q}\infty$ for all $x\in\mathcal{S}$, and the base set of
$Q_{finite}$ is a face of $\Delta$.

We note that every facial preposet has a connected Hasse diagram. We also note
that every contraction of a facial preposet is a facial preposet.

Facial preposets will be used to define cones we will call _$\Delta$ -braid
cones_. Subsection 3.3.5 describes a method for defining $\Delta$-braid cones
from $\Delta$-nested sets, and defining cones corresponding to
$\Delta$-preposets is our primary motivation for introducing facial preposets.

####  3.3.2 $\Delta$-braid cones arising from facial preposets

Classical braid cones are traditionally defined by linear inequalities, and we
have been able to provide an alternate realization for some of them by finding
sets of vectors whose conic hull is a braid cone. In this subsection we will
define a new class of cones from facial preposets, called $\Delta$-braid
cones, defined primarily as conic hulls of certain vectors. The definition of
these $\Delta$-braid cones is defined specifically to allow for the definition
of cones from $\Delta$-nested sets in subsection 3.3.5.

For a simplicial complex $\Delta$ on set $S$ with indexed vector set
$V=\\{v_{s}|s\in V\\}$, define $\mathcal{F}(\Delta,V)$ to be the set of cones
$C^{V}_{I}=\operatorname{Cone}\\{v_{s}|s\in I\\}$ for each face $I\in\Delta$.
This is not always a fan; later we will only focus on the case where $\Delta$
is the dual simplicial complex of a simple polyhedron, which will guarantee
that we can make a fan to represent $\Delta$. For now, call it a cone complex.

######  Definition 3.3.2.

A cone complex $\mathcal{F}(\Delta,V)$ is _non-degenerate_ if $C^{V}_{I}\cap
C^{V}_{I^{\prime}}=C^{V}_{I\cap I^{\prime}}$ for all $I,I^{\prime}\in\Delta$,
and each cone $C^{V}_{I}$ is $|I|$-dimensional.

We recall that a fan is a collection of cones such that any intersection of
two cones in the fan is a cone in the fan. It is possible for a cone complex
to fail to be a fan, and it is also possible for a cone complex to be a fan
but be degenerate by failing dimensionality requirements. Figure 3.3
illustrates these possible cases in two dimensions. When
$\mathcal{F}(\Delta,V)$ is non-degenerate, the poset of cones defined by
inclusion is isomorphic to $\Delta$.

Figure 3.3: A non-degenerate fan and two degenerate cone complexes.

Ray preposets are connected preposets with two equivalence classes, and so we
know that only connected preposets have ray contractions. When $Q$ is a facial
preposet, $Q$ is connected, and so there exist ray contractions of $Q$. In
addition, these ray contractions are all facial preposets. In the same way
that we can characterize braid cones of connected preposets as conic hulls of
rays defined by ray contractions, we can define $\Delta$-braid cones as conic
hulls of rays defined by ray contractions.

######  Definition 3.3.3.

When a facial preposet $R$ is a ray preposet, define the _$\Delta$ -braid
cone_ $K_{R}^{V}$ to be the ray of the vector $\sum_{i\in R_{finite}}v_{i}$.
When a facial preposet $Q$ is not a ray preposet, define $K_{Q}^{V}$ to be the
conic hull of all rays $K_{R}^{V}$ where $R$ is a ray contraction of $Q$.

####  3.3.3 Properties of $\Delta$-braid cones

In this subsection, we wish to prove a $\Delta$-braid cone analogue to
Proposition 3.2.7. First, we will have to prove an analogue to Proposition
3.2.5. We do this for certain cones by defining linear isomorphisms which map
$\Delta$-braid cones onto classical braid cones and which allow us to apply
Proposition 3.2.5 directly. For example, in order to characterize the
intersection of two $\Delta$-braid cones, we will find a linear isomorphism
mapping both cones onto classical braid cones, and then characterize the
intersection of their images.

A map taking $\Delta$-braid cones to classical braid cones implies a map from
facial preposets to preposets. There are two obvious ways to turn facial
preposets into preposets. The first method, removing the element $\infty$ from
a facial preposet, is very useful for characterizing the normal fan of a
simplex-nestohedron as both a classical nestohedron and as a
$\mathcal{P}$-nestohedron, and we devote Subsection 3.3.6 to studying this
correspondence. The second method for defining a preposet from a facial
preposet $Q$ is to forget that $Q$ is a facial preposet, and treat the element
$\infty$ in $Q$ like any other element. We note that if $Q$ is a facial
preposet on the set $S$, then $Q$ is a preposet on the set
$S\cup\\{\infty\\}$. When we treat $Q$ as a preposet, we will refer to it as
the _finitized_ preposet of $Q$.

######  Lemma 3.3.4.

For a facial preposet $Q$ on base set $\mathcal{S}$, define the vector set $V$
in the vector space $\mathbb{R}^{\mathcal{S}}/(1,\ldots,1)$ such that
$v_{i}=[-e_{i}]$ for each $i\in\mathcal{S}$. We find that the cone $K_{Q}$ of
the finitized preposet $Q$ is equal to the cone $K^{V}_{Q}$.

###### Proof.

We first prove this for the case that $Q$ is a ray preposet as well as being a
facial preposet. In this case, if $Q$ has lower class $I$, we find that
$Q_{finite}$ is the preposet on $I$ such that all elements are equivalent, and
we find $K^{V}_{Q}$ is equal to the conic hull of the single vector
$\sum_{i\in I}v_{i}=\sum_{i\in I}[-e_{i}]$, which is equal to $K_{Q}^{V}$.

Now consider the case where $Q$ is not a ray preposet. We note that every
contraction of a facial preposet is a facial preposet, so if $R$ is a ray
contraction of $Q$ then it is also a facial preposet. As a result, the conic
hull of $K_{Q}$ is equal to the conic hull of all rays $K_{R}$ where $R$ is a
ray contraction of $Q$, which is equal to the conic hull of $K_{R}^{V}$ for
any ray contraction $R$ of $Q$, which we have defined as $K_{Q}^{V}$. ∎

######  Proposition 3.3.5.

Consider two facial preposets $Q,Q^{\prime}$ of a simplicial complex $\Delta$,
such that $Q/\equiv_{Q},Q^{\prime}/\equiv_{Q^{\prime}}$ are rooted trees.
Assume that $V$ is a set of vectors such that $\mathcal{F}(\Delta,V)$ is non-
degenerate.

  1. 1.

If $I$ is a face of $\Delta$, then the cone $C^{V}_{I}$ is equal to the cone
$K_{Q^{\prime\prime}}$, where $Q^{\prime\prime}$ is the facial preposet
defined as follows: $i\prec j$ for all $i\in I,j\in\mathcal{S}\backslash I$,
and $j\equiv\infty$ for all $j\in\mathcal{S}\backslash I$.

  2. 2.

If $I$ is a face of $\Delta$, then the base set of $Q_{finite}$ is a subset of
$I$ if and only if the cone $K_{Q}^{V}$ is contained in the cone $C^{V}_{I}$.

  3. 3.

The preposet $Q$ is a contraction of $Q^{\prime}$ if and only if $K_{Q}^{V}$
is a face of $K_{Q^{\prime}}^{V}$.

  4. 4.

The cone $K_{\overline{Q\cup Q^{\prime}}}$ is equal to the cone $K_{Q}^{V}\cap
K_{Q^{\prime}}^{V}$.

  5. 5.

$Q\subseteq Q^{\prime}$ if and only if $K_{Q^{\prime}}^{V}\subseteq
K_{Q}^{V}$.

  6. 6.

The dimension of $K_{Q}^{V}$ is the number of equivalence classes in
$Q_{finite}$.

###### Proof.

  1. 1.

The facial preposet $Q^{\prime\prime}$ has a finite set whose equivalence
classes are the singleton subsets of $I$, and is such that all elements of $I$
are incomparable in the preposet. This facial preposet is a rooted tree, with
maximal equivalence class $(\mathcal{S}\cup\\{\infty\\})\backslash I$, and
edges in the Hasse diagram between the equivalence class and the elements in
$I$. As a result, the ray contractions of this preposet are the ray preposets
whose lower class only contains one element in $I$. The conic hull of these
rays is the conic hull of the vectors $\\{v_{i}|i\in I\\}$, which is exactly
the cone $C^{V}_{I}$.

  2. 2.

Consider the case where the base set of $Q_{finite}$ is a subset of $I$. Every
facial ray contraction $R$ of $Q$ has a finite set that is a subset of $I$,
and so is a sum of a subset of vectors of the form $v_{i}$ for $i\in I$. As a
result, $K_{Q}^{V}$ is a conic hull of a collection of vectors in the cone
$C^{V}_{I}$, and so $K_{Q}^{V}\subseteq C^{V}_{I}$.

Now consider the case that $Q_{finite}$ is not a subset of $I$. This means
there exists at least one element $j\in Q_{finite}$ such that $j\notin I$.
Define $J$ to be the principal ideal of $j$ in $Q_{finite}$. The vector
$v_{J}=\sum_{i\in J}v_{i}$ is in $K_{Q}^{V}$ but not in $C^{V}_{I}$, and is
contained in the interior of $C^{V}_{J}$. Because $\mathcal{F}(\Delta,V)$ is a
fan, we note that the interior of $C^{V}_{J}$ intersects with $C^{V}_{I}$ if
and only if $C^{V}_{J}\subseteq C^{V}_{I}$. Because $\mathcal{F}(\Delta,V)$ is
non-degenerate, we also note that $C^{V}_{J}\subseteq C^{V}_{I}$ if and only
if $J\subseteq I$, which is not the case. As a result, $v_{J}\in K_{Q}^{V}$ is
not contained in $C^{V}_{I}$, and $K_{Q}^{V}\not\subseteq C^{V}_{I}$.

  3. 3.

First, note that if $Q$ is a contraction of $Q^{\prime}$, then the base set of
the finite set of $Q$, which we are writing as $I$, is a subset of the base
set of the finite set $I^{\prime}$ of $Q^{\prime}$, and
$K_{Q}^{V},K_{Q^{\prime}}^{V}\subseteq C^{V}_{I^{\prime}}$. Secondly, if
$K_{Q}$ is a face of $K_{Q^{\prime}}$, then $K_{Q}\subseteq
C^{V}_{I^{\prime}}$ and $I\subseteq I^{\prime}$. As a result, it is sufficient
to prove that this is true in the case where $I\subseteq I^{\prime}$.

Define a linear map on the linear span of $C^{V}_{I^{\prime}}$, into the space
$\mathbb{R}^{I^{\prime}\cup\\{\infty\\}}/(1,\ldots,1)$, defined by
$T(v_{i})=[-e_{i}]$ for $i\in I^{\prime}$. We note that $\\{v_{i}|i\in
I^{\prime}\\}$ are linearly independent, and the set of vectors $[-e_{i}]$ for
$i\in I^{\prime}$ are all linearly independent, with $\sum_{i\in
I^{\prime}}[-e_{i}]=[e_{\infty}]$. This map is therefore a linear isomorphism.
We can see from Lemma 3.3.4 and the definition of $\Delta$-braid cones that
$T$ is an isomorphism such that $T(K_{Q^{\prime}}^{V})=K_{Q^{\prime}}$ and
$T(K_{Q}^{V})=K_{Q}$. In addition, from Proposition 3.2.5, $K_{Q}$ is a face
of $K_{Q^{\prime}}$ if and only if $Q$ is a contraction of $Q^{\prime}$, and
the linear isomorphism proves that $K_{Q}^{V}$ is a face of
$K_{Q^{\prime}}^{V}$ if and only if $Q$ is a contraction of $Q^{\prime}$.

  4. 4.

We wish to prove that $K_{\overline{Q\cup Q^{\prime}}}^{V}=K^{V}_{Q}\cap
K^{V}_{Q^{\prime}}$. Note that the linear isomorphism $T$ defined in part (3)
cannot be defined on the linear span of the vectors $\\{v_{i}|i\in I\cup
I^{\prime}\\}$, as the vectors might not be linearly independent. However, we
know the cone $C^{V}_{I\cap I^{\prime}}$ is simplicial, and the vectors
$\\{v_{i}|i\in I\cap I^{\prime}\\}$ must be independent. As a result, it is
our goal in this proof to find new preposets $P$ and $P^{\prime}$, such that
$K_{P}^{V}=K_{Q}^{V}\cap C^{V}_{I^{\prime}}$ and
$K_{P^{\prime}}^{V}=K_{Q^{\prime}}^{V}\cap C^{V}_{I}$, and then prove that
$\overline{P\cup P^{\prime}}=\overline{Q\cup Q^{\prime}}$, and $K_{P}^{V}\cap
K_{P^{\prime}}^{V}=K_{\overline{P\cup P^{\prime}}}^{V}$.

We define $P$ as the preposet defined by taking $Q$ and defining
$x\equiv_{P}\infty$ for all $x\in I\backslash I^{\prime}$. This removes
elements from $Q_{finite}$ that are not contained in $Q^{\prime}_{finite}$.
The finite set of $P$ is a subset of $I\cap I^{\prime}$, but may possibly not
be equal to $I\cap I^{\prime}$. We find that $P$ is a contraction of $Q$, and
therefore $K_{P}^{V}$ is a face of $K_{Q}^{V}$ and is contained in
$C^{V}_{I\cap I^{\prime}}$. Note that $C^{V}_{I\cap I^{\prime}}$ is a face of
$C^{V}_{I}$, which contains $K_{Q}^{V}$, so $C^{V}_{I\cap I^{\prime}}\cap
K_{Q}^{V}$ is a face of $K_{Q}^{V}$. From this, we find that $K_{P}^{V}$ is a
face of $K_{Q}^{V}\cap C^{V}_{I\cap I^{\prime}}$. However, $P$ is the minimal
contraction of $Q$ with finite set contained in $I\cap I^{\prime}$. As a
result, $K_{P}^{V}=K_{Q}^{V}\cap C^{V}_{I\cap I^{\prime}}$.

We can define $P^{\prime}$ in an analogous way, being the minimal contraction
of $Q^{\prime}$ with finite set contained in $I\cap I^{\prime}$, and find
$K_{P^{\prime}}^{V}=K_{Q^{\prime}}^{V}\cap C^{V}_{I\cap I^{\prime}}$. We then
see that $K_{P}^{V}\cap K_{P^{\prime}}^{V}=K_{Q}^{V}\cap K_{Q^{\prime}}^{V}$.

Now consider $\overline{P\cup P^{\prime}}$. It is trivial to see that
$\overline{P\cup P^{\prime}}=\overline{Q\cup Q^{\prime}}$. All we need to do
now is prove that $K_{\overline{P\cup P^{\prime}}}^{V}=K_{P}^{V}\cap
K_{P^{\prime}}^{V}$. Now, we need only define the map $T$, defined before for
part (3), on the set of vectors $\\{v_{i}|i\in I\cap I^{\prime}\\}$. With this
linear isomorphism, we can find a mapping taking $K_{P}^{V}$ to $K_{P}$,
$K_{P^{\prime}}^{V}$ to $K_{P^{\prime}}$, and $K_{\overline{P\cup
P^{\prime}}}^{V}$ to $K_{\overline{P\cup P^{\prime}}}$. Using Proposition
3.2.5, we find that $K_{\overline{P\cup P^{\prime}}}=K_{P}\cap
K_{P^{\prime}}$, and because of the linear isomorphism $T$, we have proven our
statement.

  5. 5.

Note that $Q\subseteq Q^{\prime}$ if and only if $Q^{\prime}=\overline{Q\cup
Q^{\prime}}$, which is true if and only if $K_{Q^{\prime}}^{V}=K_{Q}^{V}\cap
K_{Q^{\prime}}^{V}$, which is true if and only if $K_{Q^{\prime}}^{V}\subseteq
K_{Q}^{V}$.

  6. 6.

The cone $K_{Q}^{V}$ is isomorphic to the cone $K_{Q}$, which is the full-
dimensional cone of $Q/\equiv_{Q}$ inside the linear span of $K_{Q}$. The
preposet $Q/\equiv_{Q}$ has $k+1$ elements, where $k$ is the number of
equivalence classes of $Q_{finite}$, and so $K_{Q}$ is $k$-dimensional, and
$K_{Q}^{V}$ is $k$-dimensional.

∎

Note that several statements in Proposition 3.2.5 do not have parallels in
Proposition 3.3.5. For instance, every facial preposet is connected by the
equivalence class containing infinity, and so every $\Delta$-braid cone is
pointed, which is not the case for general preposets and braid cones.

####  3.3.4 $\Delta$-facial preposets arising from $\Delta$-nested sets

Definition 3.2.1 defines a preposet $P_{N}$ from a set $N$ of subsets of a
base set $\mathcal{S}$. We define a similar construction to $P_{N}$, but this
time defining a preposet on a base set including the element $\infty$.

######  Definition 3.3.6.

Consider a simplicial complex $\Delta$ on base set $\mathcal{S}$ and a
$\Delta$-building set $\mathcal{B}$. For a $\mathcal{B}$-nested set $N$,
define $Q(N)$ to be the preposet on $\mathcal{S}\cup\\{\infty\\}$ such that
$i\preceq j$ if and only if every set in $N$ which contains $j$ also contains
$i$.

We note that $\infty$ is contained in no set in $N$, so $i\preceq\infty$ for
all $i\in\mathcal{S}$, and $i\equiv\infty$ if and only if $i\notin\bigcup N$,
meaning the finite set of $Q(N)$ is $\bigcup{N}$, which is a face of $\Delta$.
As a result, $Q(N)$ is a facial preposet.

We note that $Q(N)$ defined for a nested set over a building set with base set
$\mathcal{S}$ is equal to $P_{N}$ defined on the base set
$\mathcal{S}\cup\\{\infty\\}$. For a $\mathcal{B}$-nested set $N$, we find
that for each element $i$ in the set $\bigcup N=\bigcup_{I\in N}I$, there is a
unique minimal set $I_{i}\in N$ such that $i\in I_{i}$. The following
proposition is directly analogous to Proposition 3.2.2, but applies to facial
preposets of $\Delta$-nested sets instead of preposets of classical nested
sets.

######  Proposition 3.3.7.

The facial preposet $Q(N)$ defined by a $\mathcal{B}$-nested set $N$ of a
simplicial complex $\Delta$ is equal to the facial preposet of $\Delta$ such
that if $i,j\in\bigcup N$, then $i\preceq j$ if and only if $I_{i}\subseteq
I_{j}$, and $i\equiv\infty$ for all $i\in S\backslash(\bigcup N)$.

We note that $Q(N)$ is a rooted tree, and $Q(N)_{finite}$ is a forest of
rooted trees. We will use the notation $K_{N}^{V}=K_{Q(N)}^{V}$ to denote the
$\Delta$-braid cone defined by a $\Delta$-nested set.

######  Proposition 3.3.8.

For two $\mathcal{B}$-nested sets $N,N^{\prime}$ of a simplicial complex
$\Delta$, the following statements are equivalent:

  1. 1.

$N\subseteq N^{\prime}$

  2. 2.

$Q(N)$ is a contraction of $Q({N^{\prime}})$

  3. 3.

$Q({N^{\prime}})\subseteq Q(N)$

  4. 4.

If $V$ is a vector set such that $\mathcal{F}(\Delta,V)$ is non-degenerate,
then $K_{N}^{V}$ is a face of $K^{V}_{N^{\prime}}$.

  5. 5.

If $V$ is a vector set such that $\mathcal{F}(\Delta,V)$ is non-degenerate,
then $K_{N}^{V}\subseteq K_{N^{\prime}}^{V}$.

###### Proof.

First we should note some analogous statements for classical $B$-nested sets.
If $M,M^{\prime}$ are $B$-nested for a classical building set $B$, then the
following four statements are equivalent: $M\subseteq M^{\prime}$,
$P_{M^{\prime}}\subseteq P_{M}$, $P_{M}$ is a contraction of $P_{M^{\prime}}$,
and $K_{M}$ is a face of $K_{M^{\prime}}$.

Consider the case where $N^{\prime}=N\cup\\{I\\}$. We wish to prove that
$Q(N)$ can be obtained by contracting a single cover relation in
$Q(N^{\prime})$. If $I$ is maximal in $N^{\prime}$, define the set $J=I\cap
Q(N)_{finite}$. We leave it as trivial that $Q(N)$ is found by contracting the
equivalence classes $J$ and $Q(N)_{infinite}$ in $Q(N^{\prime})$. As a result,
$Q(N^{\prime})$ is a contraction of $Q(N)$ in this case. Alternatively, if $I$
is not maximal in $N^{\prime}$, then the base sets of $Q(N)_{finite}$ and
$Q(N^{\prime})_{finite}$ are equal. If we restrict $\mathcal{B}$ to the set
$\bigcup N^{\prime}$, then we find $N,N$ are both nested sets of a classical
building set $B=\\{S\in\mathcal{B}|S\subseteq\bigcup N\\}$. Because
$N,N^{\prime}$ are $B$-nested and $N\subseteq N^{\prime}$, we know that
$P_{N^{\prime}}$ is a contraction of $P_{N}$. Because
$P_{N}=Q(N)_{finite},P_{N^{\prime}}=Q(N)_{finite}$, this means $Q(N^{\prime})$
is a contraction of $Q(N)$. This argument has applied to the case that
$|N^{\prime}|=|N|+1$, but applied inductively, we find (1) implies (2).

Proposition 3.3.5 means that (2) implies (3).

We wish to prove that (3) implies (1). Assume that $Q(N^{\prime})\subseteq
Q(N)$. For an element $i$ in the preposet $Q(N)$, define principal ideals
$I_{i}=\\{x|x\preceq_{Q(N)}i\\}$, and
$I^{\prime}_{i}=\\{x|x\preceq_{Q(N^{\prime})}i\\}$. We find that for each $i$
in the base set $\mathcal{S}$ of $\Delta$ that either $I_{i}\in N$ or
$I_{i}=\mathcal{S}\cup\\{\infty\\}$, and similarly for $Q(N^{\prime})$.

We also can see that each set $I_{i}$ is equal to the union $\bigcup_{j\in
J}I^{\prime}_{j}$ for some set $J\subseteq\mathcal{S}$. We wish to prove that
$I_{i}\in N^{\prime}$. If not, then there exists a minimal subset
$J\subseteq\mathcal{S}$ such that $\bigcup_{j\in J}I^{\prime}_{j}=I_{i}$.
Because this set is minimal, we find $I^{\prime}_{j},I^{\prime}_{j^{\prime}}$
are incomparable for any $j,j^{\prime}\in J$. As a result, there exists a
subset of $N^{\prime}$ of order $\geq 2$ whose union is $I_{i}$. We know that
$I_{i}\in\mathcal{B}$, which is a contradiction. Proposition 2.1.8 states that
no union of a subset of order $\geq 2$ of incomparable elements of a
$\mathcal{B}$-nested set is equal to a set in $\mathcal{B}$. As a result, we
find that every set $I\in N$ is contained in $N^{\prime}$, and $N\subseteq
N^{\prime}$.

We know (2) and (4) are equivalent according to Proposition 3.3.5. Similarly,
we know (3) and (5) are equivalent according to the same proposition. ∎

######  Proposition 3.3.9.

For two $\mathcal{B}$-nested sets $N,N^{\prime}$, we find
$\overline{Q(N^{\prime})\cup Q(N)}=Q(N\cap N^{\prime})$.

###### Proof.

Note that $Q(N\cap N^{\prime})$ is the smallest common contraction of $Q(N)$
and $Q(N^{\prime})$, and as a result $\overline{Q(N)\cup
Q(N^{\prime})}\subseteq Q(N\cap N^{\prime})$. However, proving that the two
preposets are actually equal is not trivial. We will instead rely upon the
fact that when $B$ is a classical building set, and $M,M^{\prime}$ are
$B$-nested, then the set of cones of $B$-nested sets is a fan, and
specifically, $K_{M}\cap K_{M^{\prime}}=K_{M\cap M^{\prime}}$ and
$\overline{P(M)\cup P(M^{\prime})}=P(M\cap M^{\prime})$. We will use a linear
isomorphism similar to the one used in Proposition 3.3.5 part (4).

For any face $I\in\Delta$, define the facial preposet $Q_{I}$ as the unique
facial preposet with finite set equal to $I$, and $i,j$ incomparable for all
distinct $i,j\in I$. We wish to prove a lemma that $\overline{Q_{I}\cup