# Shellability of Polyhedral Joins of Simplicial Complexes and Its Application
to Graph Theory

Kengo Okura  Osaka Metropolitan University, 1-1 Gakuen-cho, Naka-ku, Sakai,
Osaka 599-8531, Japan<EMAIL_ADDRESS>
###### Abstract.

We investigate the shellability of the polyhedral join
$\mathcal{Z}^{*}_{M}(K,L)$ of simplicial complexes $K,M$ and a subcomplex
$L\subset K$. We give sufficient conditions and necessary conditions on
$(K,L)$ for $\mathcal{Z}^{*}_{M}(K,L)$ being shellable. In particular, we show
that for some pairs $(K,L)$, $\mathcal{Z}^{*}_{M}(K,L)$ becomes shellable
regardless of whether $M$ is shellable or not. Polyhedral joins can be applied
to graph theory as the independence complex of a certain generalized version
of lexicographic products of graphs which we define in this paper. The graph
obtained from two graphs $G,H$ by attaching one copy of $H$ to each vertex of
$G$ is a special case of this generalized lexicographic product and we give a
result on the shellability of the independence complex of this graph by
applying the above results.

###### Key words and phrases:

polyhedral join, shellability, lexicographic product

###### 2020 Mathematics Subject Classification:

05E45, 05C76

##  1\. Introduction

A finite simple graph $G$ is a pair $G=(V(G),E(G))$ of a finite set $V(G)$ and
a set $E(G)\subset\\{e\subset V(G)\ |\ |e|=2\\}$. We drop adjectives “finite
simple” and call $G$ a graph. $v\in V(G)$ is called a vertex of $G$ and $e\in
E(G)$ is called an edge of $G$. The independence complex of $G$ is an abstract
simplicial complex $I(G)$ defined by

$\displaystyle I(G)=\\{\sigma\subset V(G)\ |\ \\{u,v\\}\notin E(G)\text{ for
any $u,v\in\sigma$ }\\}.$

A simplex of $I(G)$ is called an independent set of $G$.

A simplicial complex $K$ is shellable if its facets can be arranged in a
linear order $F_{1},F_{2},\ldots,F_{t}$ (which we call a shelling) in such a
way that the subcomplex $\left(\bigcup_{i=1}^{k-1}\langle
F_{i}\rangle\right)\cap\langle F_{k}\rangle$ is pure and $(\dim
F_{k}-1)$-dimensional for all $k=2,\ldots,t$. (Note that this is “non-pure”
shellability defined by Björner and Wachs [3, 4].) A graph is called shellable
if its independence complex is shellable. The shellability (including vertex
decomposability, which is one of the sufficient conditions for a graph being
shellable) of graphs has been studied by many researchers, such as [6, 8, 9,
11]. In this paper, we focus on the following result by Hibi, Higashitani,
Kimura, and O’Keefe [6]. Here, a graph $G$ is called well-covered if every
maximal independent set of $G$ has the same cardinality.

######  Theorem 1.1 (Based on Hibi, Higashitani, Kimura, and O’Keefe [6,
Theorem 1.1]).

Let $G$ be a graph on a vertex set $V(G)=\\{u_{1},\ldots,u_{n}\\}$. Let
$k_{1},\ldots,k_{n}\geq 2$ be integers. Then the graph $G^{\prime}$ obtained
from $G$ by attaching the complete graph $K_{k_{i}}$ to $u_{i}$ for
$i=1,\ldots,n$ is well-covered and shellable.

Motivated by Theorem 1.1, we consider the graph $G[H;\\{v_{0}\\}]$ defined as
follows. Let $G$, $H$ be graphs and $v_{0}$ be a vertex of $H$. Define
$G[H;\\{v_{0}\\}]$ as the graph obtained from $G\sqcup\left(\bigsqcup_{u\in
V(G)}H_{u}\right)$, where $H_{u}$ is a copy of $H$, by identifying $u\in G$
with $v_{0}\in H_{u}$. Theorem 1.1 implies that if $H$ is a complete graph,
then $G[H;\\{v_{0}\\}]$ is well-covered and shellable for any graph $G$.

In this paper, we obtain a necessary and sufficient condition on $H$ and
$v_{0}$ for $G[H;\\{v_{0}\\}]$ being well-covered and shellable for any graph
$G$.

######  Theorem 1.2.

Let $H$ be a graph and $v_{0}$ be a vertex of $H$. Then the following two
conditions are equivalent.

  1. (1)

For any graph $G$, $G[H;\\{v_{0}\\}]$ is well-covered and shellable.

  2. (2)

$H$ is well-covered, both $H$ and $H\setminus\\{v_{0}\\}$ are shellable, and
for any maximal independent set $\tau$ of $H\setminus\\{v_{0}\\}$, there
exists $v\in\tau$ such that $\\{v_{0},v\\}\in E(H)$.

In order to prove Theorem 1.2, we need to investigate the independence complex
of $G[H;\\{v_{0}\\}]$. With $I(G)$ and $I(H)$, the independence complex
$I(G[H;\\{v_{0}\\}])$ is described as a polyhedral join. Polyhedral join is a
construction of simplicial complexes introduced by Ayzenberg [1, Definition
4.2, Observation 4.3]. It is similar to polyhedral product
$\mathcal{Z}_{K}(\underline{X},\underline{A})$, a well-known construction of
spaces, where $K$ is a simplicial complex and
$(\underline{X},\underline{A})=\\{(X_{u},A_{u})\\}_{u\in V(K)}$ is a family of
pairs of spaces. The definition of polyhedral joins is obtained from the
definition of polyhedral products by replacing “pairs of spaces” and “product
of spaces” with “pairs of simplicial complex and its subcomplex” and “join of
simplicial complexes”, respectively. Polyhedral joins appear in previous
studies, including when they are called by other names. Bahri, Bendersky,
Cohen, and Gitler [2, Definition 2.1] defined a simplicial complex $K(J)$ for
a simplicial complex $K$ on $V(K)=\\{1,\ldots,n\\}$ and a tuple
$J=(j_{1},\ldots,j_{n})$ of positive integers. Using our notation of
polyhedral joins, $K(J)$ is denoted by

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{\Delta^{J-1}},\underline{\partial\Delta^{J-1}})\text{,
where
}(\underline{\Delta^{J-1}},\underline{\partial\Delta^{J-1}})=\\{(\Delta^{j_{i}-1},\partial\Delta^{j_{i}-1})\\}_{i\in\\{1,\ldots,m\\}}.$

Here, $\Delta^{d}$ is the $d$-simplex and $\partial\Delta^{d}$ is its
boundary. They obtained the decomposition of polyhedral products, more
precisely, moment-angle complexes, denoted by

$\displaystyle\mathcal{Z}_{K}(D^{2},S^{1})=\mathcal{Z}_{\mathcal{Z}^{*}_{K}(\Delta^{1},\partial\Delta^{1})}(D^{1},S^{0}).$

We note that the above observation is mentioned by Vidaurre [10], who
investigated the polyhedral products over polyhedral joins. Another example is
$(j_{1},\ldots,j_{n})$-expansion of $K$, which is introduced by Moradi and
Khosh-Ahang [7, Definition 2.1]. It is denoted by

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{\mathrm{pt}^{J}},\\{\emptyset\\})\text{,
where }(\underline{\mathrm{pt}^{J}},\\{\emptyset\\})$
$\displaystyle=\left\\{\left({\bigsqcup}_{j_{i}}\mathrm{pt},\\{\emptyset\\}\right)\right\\}_{i\in\\{1,\ldots,m\\}}.$

They studied the shellability and vertex decomposability of expansions. We
generalize one of their results [7, Theorem 2.12].

This paper is organized as follows. In Section 2, we define terminologies and
notations on simplicial complexes and state some basic properties of shellable
simplicial complexes. Section 3 provides the definition of polyhedral joins
and the explicit description of simplices and facets of polyhedral joins.
Section 4 is the main part of this paper. Here we obtain two necessary
conditions and two sufficient conditions for polyhedral joins being shellable,
giving counterexamples of converse propositions. Note that some of the results
are not relevant to Theorem 1.2. Finally, in Section 5, we apply the results
obtained in Section 4 to the independence complexes of graphs and prove
Theorem 1.2.

##  2\. Preliminaries

In the following, for a positive integer $m$, we set $[m]=\\{1,2,\ldots,m\\}$.

An abstract simplicial complex $K$ is a collection of finite subsets of a
given set $V(K)$ such that if $\sigma\in K$ and $\tau\subset\sigma$, then
$\tau\in K$. In this paper, we drop the adjective “abstract”. An element of
$K$ is called a simplex of $K$. An element of $V(K)$ is called a vertex of
$K$. We suppose that $\\{v\\}\in K$ for any $v\in V(K)$. We set $\dim
K=\max_{\sigma\in K}|\sigma|-1$, where $|\sigma|$ is the cardinality of
$\sigma\subset V(K)$. If $\dim K=d$, then $K$ is called $d$-dimensional. A
maximal simplex with respect to the inclusion is called a facet of $K$. $K$ is
called pure if every facet of $K$ has the same cardinality.

$L\subset K$ is called a subcomplex of $K$ if $L$ is a simplicial complex. In
this paper, we call $(K,L)$ a pair of simplicial complexes if $K$ is a
simplicial complex and $L\subset K$ is a subcomplex of $K$. For a vertex $v\in
V(K)$ of $K$, we define a subcomplex $\mathrm{dl}_{K}(v)$ of $K$ by

$\displaystyle\mathrm{dl}_{K}(v)=\\{\sigma\in K\ |\ v\notin\sigma\\}.$

Let $\\{K_{i}\\}_{i\in[m]}$ be a family of simplicial complexes. We define a
simplicial complex $K_{1}*\cdots*K_{m}$, which we call the join of
$K_{1},K_{2},\ldots$, and $K_{m}$, by

$\displaystyle
K_{1}*\cdots*K_{m}=\left\\{\sigma\subset\bigsqcup_{i\in[m]}V(K_{i})\ \middle|\
\sigma\cap V(K_{i})\in K_{i}\text{ for any $i\in[m]$}\right\\}.$

Let $V$ be a finite set and $F_{1},\ldots,F_{t}\subset V$ be a collection of
subsets of $V$ such that $F_{i}\nsubseteq F_{j}$ for any $i\neq j$. Define a
simplicial complex $\langle F_{1},\ldots,F_{t}\rangle$ on $V$ by

$\displaystyle\langle F_{1},\ldots,F_{t}\rangle=\\{\sigma\subset V\ |\
\sigma\subset F_{i}\text{ for some }i\in[t]\\}.$

As defined in Section 1, a simplicial complex $K$ is shellable if its facets
can be arranged in a linear order $F_{1},F_{2},\ldots,F_{t}$ (which we call a
shelling) in such a way that the subcomplex $\left(\bigcup_{i=1}^{k-1}\langle
F_{i}\rangle\right)\cap\langle F_{k}\rangle$ is pure and $(\dim
F_{k}-1)$-dimensional for all $k=2,\ldots,t$. Here we state some of the
properties of shellable simplicial complexes without proofs.

######  Lemma 2.1 (Based on [3, Lemma 2.3]).

Let $K$ be a simplicial complex. An order $F_{1},F_{2},\ldots,F_{t}$ of the
facets of $K$ is a shelling if and only if for every $i,k$ with $1\leq i<k\leq
t$, there exists an index $j$ with $1\leq j<k$ and a vertex $x\in
F_{k}\setminus F_{i}$ such that $F_{j}\cap F_{k}=F_{k}\setminus\\{x\\}$.

######  Lemma 2.2 (Based on [3, Lemma 2.6]).

Let $K$ be a shellable simplicial complex. Then there exists a shelling
$F_{1},F_{2},\ldots,F_{t}$ such that $|F_{i}|\geq|F_{j}|$ for any $1\leq
i<j\leq t$.

######  Lemma 2.3 ([4, Remark 10.22]).

The join of two simplicial complexes is shellable if and only if each of the
simplicial complex is shellable.

For a simplicial complex $X$, we denote the set of all facets of $X$ by
$\mathbf{F}_{X}$. Note that for a pair $(K,L)$ of simplicial complexes, we
have

$\displaystyle\mathbf{F}_{K}\setminus\mathbf{F}_{L}$
$\displaystyle=\left\\{\sigma\in\mathbf{F}_{K}\ |\ \sigma\notin L\right\\},$
$\displaystyle\mathbf{F}_{L}\setminus\mathbf{F}_{K}$
$\displaystyle=\left\\{\tau\in\mathbf{F}_{L}\ |\ \text{there exists
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ such that
$\tau\subsetneq\sigma$}\right\\},$
$\displaystyle\mathbf{F}_{K}\cap\mathbf{F}_{L}$
$\displaystyle=\left\\{\sigma\in\mathbf{F}_{K}\ |\ \sigma\in L\right\\}.$

##  3\. Facets of Polyhedral Joins

The main subject of this paper is polyhedral join. It is a construction of
simplicial complexes, which is based on the definition by Ayzenberg [1,
Definition 4.2, Observation 4.3].

######  Definition 3.1.

Let $M$ be a simplicial complex on $[m]$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i\in[m]}$ be a family of
pairs of simplicial complexes. For a simplex $S\in M$, we define a simplicial
complex $(\underline{K},\underline{L})^{*S}$ by

$\displaystyle(\underline{K},\underline{L})^{*S}=X_{1}*X_{2}*\cdots*X_{m},\
X_{i}=\left\\{\begin{aligned} &K_{i}&&(i\in S),\\\ &L_{i}&&(i\notin
S).\end{aligned}\right.$

$(\underline{K},\underline{L})^{*S}$ is a subcomplex of $K_{1}*\cdots*K_{m}$.

$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ is a subcomplex of
$K_{1}*\cdots*K_{m}$ defined by

$\displaystyle\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})=\bigcup_{S\in
M}(\underline{K},\underline{L})^{*S}$

(union is taken in $K_{1}*\cdots*K_{m}$).

Let $(K,L)$ be a pair of simplicial complexes. If $K_{i}=K,L_{i}=L$ for any
$i\in[m]$, we write $\mathcal{Z}^{*}_{M}(K,L)$ instead of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$.

We give an explicit description of simplices and facets of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$.

######  Proposition 3.2.

Let $M$ be a simplicial complex on $[m]$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i\in[m]}$ be a family of
pairs of simplicial complexes. For $\phi\subset\bigsqcup_{i\in[m]}V(K_{i})$,
we set

$\displaystyle\phi_{i}$ $\displaystyle=\phi\cap V(K_{i})\ (i\in[m]),$
$\displaystyle\overline{\phi}$ $\displaystyle=\\{i\in[m]\ |\ \phi_{i}\notin
L_{i}\\}.$

Then $\phi\in\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ if and only if
$\phi_{i}\in K_{i}$ for any $i\in[m]$ and $\overline{\phi}\in M$.

###### Proof.

Let $\phi\in\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. Then $\phi$ is
a simplex of $\phi\in(\underline{K},\underline{L})^{*S}$ for some $S\in M$.
So, by the definition of the join, we have

  * •

$\phi\cap V(K_{i})=\phi_{i}\in K_{i}$ for any $i\in S$,

  * •

$\phi\cap V(K_{i})=\phi_{i}\in L_{i}\subset K_{i}$ for any $i\notin S$.

It follows that $\phi_{i}\in K_{i}$ for any $i\in[m]$ and that
$\overline{\phi}\subset S$. Since $M$ is a simplicial complex and $S\in M$, we
have $\overline{\phi}\in M$.

Conversely, let $\phi\subset\bigsqcup_{i\in[m]}V(K_{i})$ be a set such that
$\phi_{i}\in K_{i}$ for any $i\in[m]$ and $\overline{\phi}\in M$. By the
definition of $\overline{\phi}$, $i\notin\overline{\phi}$ implies $\phi_{i}\in
L_{i}$. So, we have
$\phi\in(\underline{K},\underline{L})^{*\overline{\phi}}\subset\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$.
∎

######  Proposition 3.3.

Let $M$ be a simplicial complex on $[m]$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i\in[m]}$ be a family of
pairs of simplicial complexes. Then $\phi\subset\bigsqcup_{i\in[m]}V(K_{i})$
is a facet of $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ if and only
if

  * •

$\phi_{i}\in\mathbf{F}_{K_{i}}\cup\mathbf{F}_{L_{i}}$ for any $i\in[m]$,

  * •

$\overline{\phi}\in M$, and

  * •

$\overline{\phi}\cup\\{i\\}\notin M$ for any $i\in[m]$ such that
$\phi_{i}\in\mathbf{F}_{L_{i}}\setminus\mathbf{F}_{K_{i}}$.

###### Proof.

Let $\phi$ be a facet of $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$.
For $k\in[m]$ and $\sigma\in K_{k}$, define
$\phi^{(k,\sigma)}\subset\bigsqcup_{i\in[m]}V(K_{i})$ by

$\displaystyle\phi^{(k,\sigma)}_{i}=\left\\{\begin{aligned} &\phi_{i}&&(i\neq
k)\\\ &\sigma&&(i=k).\end{aligned}\right.$

First, assume that there exists $\sigma\in K_{k}$ such that
$\phi_{k}\subsetneq\sigma$ for some $k\in\overline{\phi}$. We have
$\sigma\notin L_{k}$ since $\sigma\supset\phi_{k}\notin L_{k}$. Therefore, we
get $\overline{\phi^{(k,\sigma)}}=\overline{\phi}\in M$. So,
$\phi^{(k,\sigma)}$ is a simplex of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ which satisfies
$\phi^{(k,\sigma)}\supsetneq\phi$, a contradiction. Thus, $\phi_{k}$ is a
facet of $K_{k}$.

Second, assume that there exists $\tau\in L_{k}$ such that
$\phi_{k}\subsetneq\tau$ for some $k\notin\overline{\phi}$. Since
$\phi_{k},\tau\in L_{k}$, we get
$\overline{\phi^{(k,\tau)}}=\overline{\phi}\in M$. So, $\phi^{(k,\tau)}$ is a
simplex of $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ which satisfies
$\phi^{(k,\tau)}\supsetneq\phi$, a contradiction. Thus, $\phi_{k}$ is a facet
of $L_{k}$.

Finally, assume that there exists $j\in[m]$ such that
$\phi_{j}\in\mathbf{F}_{L_{j}}\setminus\mathbf{F}_{K_{j}}$ and
$\overline{\phi}\cup\\{j\\}\in M$. Then there must be $\rho\in K_{j}\setminus
L_{j}$ such that $\phi_{j}\subsetneq\rho$ since $\phi_{j}$ is a facet of
$L_{j}$ and is not a facet of $K_{j}$. We get that $\phi^{(j,\rho)}$ is a
simplex of $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ since
$\overline{\phi^{(j,\rho)}}=\overline{\phi}\cup\\{j\\}\in M$. This is a
contradiction to the maximality of $\phi$. By the above three arguments, we
conclude that a facet $\phi$ of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ satisfies three conditions
in the proposition.

Conversely, suppose that $\phi\subset\bigsqcup_{i\in[m]}V(K_{i})$ satisfies
three conditions in the proposition. Since
$\phi_{i}\in\mathbf{F}_{K_{i}}\cup\mathbf{F}_{L_{i}}\subset K_{i}$ for any
$i\in[m]$ and $\overline{\phi}\in M$, $\phi$ is a simplex of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. We assume that there
exists $\psi\in\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ such that
$\phi\subsetneq\psi$ and deduce a contradiction. There must exists $k\in[m]$
such that $\phi_{k}\subsetneq\psi_{k}$. This means that $\phi_{k}$ is not a
facet of $K_{k}$, which implies
$\phi_{k}\in\mathbf{F}_{L_{k}}\setminus\mathbf{F}_{K_{k}}$. It follows that
$k\in\overline{\psi}$ since $\phi_{k}\subsetneq\psi_{k}$ and $\phi_{k}$ is a
facet of $L_{k}$. Thus, we get
$\overline{\phi}\cup\\{k\\}\subset\overline{\psi}\in M$, which contradicts to
the third condition in the proposition. Therefore, $\phi$ is a facet of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. ∎

######  Remark 3.4.

If $\mathbf{F}_{L_{i}}\subset\mathbf{F}_{K_{i}}$ for any $i\in[m]$, then by
Proposition 3.3, $\phi\subset\bigsqcup_{i\in[m]}V(K_{i})$ is a facet of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ if and only if
$\phi_{i}\in\mathbf{F}_{K_{i}}$ for any $i\in[m]$ and $\overline{\phi}\in M$.

Before investigating the shellability of $\mathcal{Z}^{*}_{M}(K,L)$, we show a
necessary and sufficient condition for $\mathcal{Z}^{*}_{M}(K,L)$ being pure.

######  Theorem 3.5.

Let $M\neq\\{\emptyset\\}$ be a simplicial complex which is not a simplex and
$K\supsetneq L$ be a pair of simplicial complexes. Then
$\mathcal{Z}^{*}_{M}(K,L)$ is pure if and only if

  * •

$K$ is pure and $\mathbf{F}_{L}\subset\mathbf{F}_{K}$, or

  * •

$K,L,M$ are pure.

###### Proof.

We set $V(M)=[m]$.

Assume that $\mathcal{Z}^{*}_{M}(K,L)$ is pure. For $S\in\mathbf{F}_{M}$,
$\sigma\in\mathbf{F}_{K}$ and $\tau\in\mathbf{F}_{L}$, define
$\Phi_{S}(\sigma,\tau)\subset\bigsqcup_{i\in[m]}V(K)$ by

$\displaystyle\Phi_{S}(\sigma,\tau)_{i}=\left\\{\begin{aligned} &\sigma&&(i\in
S)\\\ &\tau&&(i\notin S).\end{aligned}\right.$

Here, remark that $\Phi_{S}(\sigma,\tau)$ is a facet of
$\mathcal{Z}^{*}_{M}(K,L)$ if $\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$
or $\tau\in\mathbf{F}_{K}\cap\mathbf{F}_{L}$ by Proposition 3.3. If
$\Phi_{S}(\sigma,\tau)$ is a facet of $\mathcal{Z}^{*}_{M}(K,L)$, then we have

$\displaystyle|\Phi_{S}(\sigma,\tau)|$
$\displaystyle=\sum_{i\in[m]}|\Phi_{S}(\sigma,\tau)_{i}|=|S||\sigma|+(m-|S|)|\tau|.$

Note that we have $0<|S|<m$ since $M$ is neither $\\{\emptyset\\}$ nor a
simplex.

Suppose that $\mathbf{F}_{K}\cap\mathbf{F}_{L}\neq\emptyset$. Take
$S\in\mathbf{F}_{M}$, $\sigma^{0}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ and
$\tau^{0}\in\mathbf{F}_{K}\cap\mathbf{F}_{L}$. For any facets
$\sigma,\sigma^{\prime}\in\mathbf{F}_{K}$ of $K$, $\Phi_{S}(\sigma,\tau^{0})$
and $\Phi_{S}(\sigma^{\prime},\tau^{0})$ are facets of
$\mathcal{Z}^{*}_{M}(K,L)$. Since $\mathcal{Z}^{*}_{M}(K,L)$ is pure, we have
$|\Phi_{S}(\sigma,\tau^{0})|=|\Phi_{S}(\sigma^{\prime},\tau^{0})|$, namely

$\displaystyle|S||\sigma|+(m-|S|)|\tau^{0}|=|S||\sigma^{\prime}|+(m-|S|)|\tau^{0}|.$

It follows from $|S|>0$ that

$\displaystyle|\sigma|=|\sigma^{\prime}|.$

Therefore, $K$ is pure. For any facets $\tau,\tau^{\prime}\in\mathbf{F}_{L}$
of $L$, $\Phi_{S}(\sigma^{0},\tau)$ and $\Phi_{S}(\sigma^{0},\tau^{\prime})$
are facets of $\mathcal{Z}^{*}_{M}(K,L)$. Since $\mathcal{Z}^{*}_{M}(K,L)$ is
pure, we have
$|\Phi_{S}(\sigma^{0},\tau)|=|\Phi_{S}(\sigma^{0},\tau^{\prime})|$, namely

$\displaystyle|S||\sigma^{0}|+(m-|S|)|\tau|=|S||\sigma^{0}|+(m-|S|)|\tau^{\prime}|.$

It follows from $|S|<m$ that

$\displaystyle|\tau|=|\tau^{\prime}|.$

Therefore, $L$ is pure. Hence, we obtain

$\displaystyle\dim K=|\tau^{0}|-1=\dim L.$

If there exists $\tau^{1}\in\mathbf{F}_{L}\setminus\mathbf{F}_{K}$, then there
must exist $\sigma^{1}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ such that
$\tau^{1}\subsetneq\sigma^{1}$. So, we get

$\displaystyle\dim K=|\sigma^{1}|-1>|\tau^{1}|-1=\dim L,$

which is a contradiction. Thus, we conclude that
$\mathbf{F}_{L}\setminus\mathbf{F}_{K}=\emptyset$, namely
$\mathbf{F}_{L}\subset\mathbf{F}_{K}$.

Next, suppose that $\mathbf{F}_{K}\cap\mathbf{F}_{L}=\emptyset$. Take
$S\in\mathbf{F}_{M}$ and $\tau^{0}\in\mathbf{F}_{L}$. Since $\tau^{0}$ is not
a facet of $K$, there exist $\sigma^{0}\in\mathbf{F}_{K}$ such that
$\tau^{0}\subsetneq\sigma^{0}$. For any facet $\sigma$ of $K$,
$\Phi_{S}(\sigma,\tau^{0})$ is a facet of $\mathcal{Z}^{*}_{M}(K,L)$ since
$\mathbf{F}_{K}=\mathbf{F}_{K}\setminus\mathbf{F}_{L}$. Therefore, by the same
argument as above, we obtain that both $K$ and $L$ are pure. For any facet
$T,T^{\prime}\in\mathbf{F}_{M}$ of $M$, $\Phi_{T}(\sigma^{0},\tau^{0})$ and
$\Phi_{T^{\prime}}(\sigma^{0},\tau^{0})$ are facets of
$\mathcal{Z}^{*}_{M}(K,L)$. Since $\mathcal{Z}^{*}_{M}(K,L)$ is pure, we have
$|\Phi_{T}(\sigma^{0},\tau^{0})|=|\Phi_{T^{\prime}}(\sigma^{0},\tau^{0})|$,
namely

$\displaystyle|T||\sigma^{0}|+(m-|T|)|\tau^{0}|=|T^{\prime}||\sigma^{0}|+(m-|T^{\prime}|)|\tau^{0}|.$

It follows that

$\displaystyle|T|=|T^{\prime}|$

since $\sigma^{0}\supsetneq\tau^{0}$. Therefore, we conclude that $M$ is pure.

Conversely, assume that $K$ is pure and $\mathbf{F}_{L}\subset\mathbf{F}_{K}$.
Then for any facet $\phi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}$, we get

$\displaystyle|\phi|=\sum_{i\in[m]}|\phi_{i}|=m(\dim K+1).$

Therefore, $\mathcal{Z}^{*}_{M}(K,L)$ is pure.

Finally, assume that $K,L,M$ are pure and that there exists
$\tau\in\mathbf{F}_{L}\setminus\mathbf{F}_{K}$. Since there exists
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ such that
$\tau\subsetneq\sigma$, we get

$\displaystyle\dim K=|\sigma|-1>|\tau|-1=\dim L.$

So, we obtain $\mathbf{F}_{K}\cap\mathbf{F}_{L}=\emptyset$ since both $K$ and
$L$ are pure. Thus, for any $\phi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}$,
$\overline{\phi}$ is a facet of $M$. This is because we have
$\overline{\phi}\cup\\{i\\}\notin M$ for any $i\notin\overline{\phi}$ since
$\mathbf{F}_{L}=\mathbf{F}_{L}\setminus\mathbf{F}_{K}$. Hence, we get

$\displaystyle|\phi|$
$\displaystyle=\sum_{i\in\overline{\phi}}|\phi_{i}|+\sum_{i\notin\overline{\phi}}|\phi_{i}|$
$\displaystyle=|\overline{\phi}|(\dim K+1)+(m-|\overline{\phi}|)(\dim L+1)$
$\displaystyle=(\dim M+1)(\dim K+1)+(m-\dim M-1)(\dim L+1)$

for any facet $\phi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}$ since $M$ is
pure. Therefore, we conclude that $\mathcal{Z}^{*}_{M}(K,L)$ is pure. ∎

##  4\. Shellability of Polyhedral Joins

We first present two sufficient conditions for $\mathcal{Z}^{*}_{M}(K,L)$
being shellable.

######  Theorem 4.1.

Let $M$ be an arbitrary simplicial complex and $K\supset L$ be a pair of
simplicial complexes. Suppose that $K,L$ satisfy the following three
conditions.

  1. (1)

$K$ is shellable,

  2. (2)

$\mathbf{F}_{L}\subset\mathbf{F}_{K}$, and

  3. (3)

there exists a shelling $<_{K}$ on $K$ such that $\tau<_{K}\sigma$ for any
$\tau\in\mathbf{F}_{L}$ and any
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$.

Then $\mathcal{Z}^{*}_{M}(K,L)$ is shellable.

###### Proof.

We set $V(M)=[m]$. Consider a linear order $<$ on
$\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}$ such that $\phi<\psi$ if and only if

$\displaystyle\phi_{1}=\psi_{1},\ldots,\phi_{j-1}=\psi_{j-1},\phi_{j}<_{K}\psi_{j}$

for some $j\in[m]$. We show that this order is a shelling on
$\mathcal{Z}^{*}_{M}(K,L)$.

Let $\phi,\psi$ be facets of $\mathcal{Z}^{*}_{M}(K,L)$ such that
$\phi_{1}=\psi_{1},\ldots,\phi_{j-1}=\psi_{j-1},\phi_{j}<_{K}\psi_{j}$. Since
$<_{K}$ is a shelling on $K$, there exists $\sigma\in\mathbf{F}_{K}$ and
$x\in\psi_{j}\setminus\phi_{j}$ such that $\sigma<_{K}\psi_{j}$ and
$\sigma\cap\psi_{j}=\psi_{j}\setminus\\{x\\}$ by Lemma 2.1. Define
$\chi\subset\bigsqcup_{i\in[m]}V(K)$ by

$\displaystyle\chi_{i}=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\sigma&&(i=j).\end{aligned}\right.$

If $\psi_{j}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$, then we have
$\overline{\chi}\subset\overline{\psi}\in M$. If $\psi_{j}\in\mathbf{F}_{L}$,
then by condition (3), $\sigma$ must be a facet of $L$ since
$\sigma<_{K}\psi_{j}$. So, we have $\overline{\chi}=\overline{\psi}\in M$. In
both cases, we get that $\overline{\chi}\in M$, which implies that $\chi$ is a
simplex of $\mathcal{Z}^{*}_{M}(K,L)$. Furthermore, $\chi$ is a facet of
$\mathcal{Z}^{*}_{M}(K,L)$ by Remark 3.4.

We have $\chi<\psi$ because

$\displaystyle\chi_{1}=\psi_{1},\ldots,\chi_{j-1}=\psi_{j-1},\chi_{j}=\sigma<_{K}\psi_{j}.$

Moreover, we have

$\displaystyle\chi_{i}\cap\psi_{i}$ $\displaystyle=\left\\{\begin{aligned}
&\psi_{i}&&(i\neq j)\\\ &\sigma\cap\psi_{j}&&(i=j)\end{aligned}\right.$
$\displaystyle=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\psi_{j}\setminus\\{x\\}&&(i=j).\end{aligned}\right.$

Hence, we obtain

$\displaystyle\chi\cap\psi=\psi\setminus\\{x\\}.$

Finally, we have $x\in\psi\setminus\phi$ since
$x\in\psi_{j}\setminus\phi_{j}$. Therefore, by the above argument, we get
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}$ and $x\in\psi\setminus\phi$
such that $\chi<\psi$ and $\chi\cap\psi=\psi\setminus\\{x\\}$. By Lemma 2.1,
we conclude that $\mathcal{Z}^{*}_{M}(K,L)$ is shellable. ∎

The following claim indicates that we cannot drop condition (2) in Theorem 4.1
for some $M$.

######  Claim 4.2.

Let $(K,L)$ be a pair of simplicial complexes such that
$\mathbf{F}_{L}\setminus\mathbf{F}_{K}\neq\emptyset$. Then for
$M=\langle\\{1,2\\},\\{3,4\\}\rangle$, $\mathcal{Z}^{*}_{M}(K,L)$ is not
shellable.

###### Proof.

We assume that $\mathcal{Z}^{*}_{M}(K,L)$ is shellable and deduce a
contradiction. Take $\tau^{0}\in\mathbf{F}_{L}\setminus\mathbf{F}_{K}$. Fix a
shelling on $\mathcal{Z}^{*}_{M}(K,L)$ and define
$\Phi,\Psi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}$ by

$\displaystyle\Phi$
$\displaystyle=\min\left\\{\phi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}\
\middle|\
\phi_{1}=\phi_{2}=\tau^{0},\phi_{3}\supsetneq\tau^{0},\phi_{4}\supsetneq\tau^{0}\right\\},$
$\displaystyle\Psi$
$\displaystyle=\min\left\\{\psi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(K,L)}\
\middle|\
\psi_{1}\supsetneq\tau^{0},\psi_{2}\supsetneq\tau^{0},\psi_{3}=\psi_{4}=\tau^{0}\right\\}.$

Note that $\Phi,\Psi$ are well-defined because there exists
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ such that
$\sigma\supsetneq\tau^{0}$ since
$\tau^{0}\in\mathbf{F}_{L}\setminus\mathbf{F}_{K}$.

We may suppose that $\Phi<\Psi$. Then there exists $\chi<\Psi$, $j\in[m]$ and
$x\in\Psi_{j}\setminus\Phi_{j}$ such that $\chi\cap\Psi=\Psi\setminus\\{x\\}$.
Since $\Psi_{j}\setminus\Phi_{j}\neq\emptyset$, we obtain $j\in\\{1,2\\}$.
Here, we set $j=1$. Then for $i=2,3,4$, we have
$\chi_{i}\cap\Psi_{i}=\Psi_{i}$, namely $\chi_{i}\supset\Psi_{i}$. So, we get
$\chi_{2}=\Psi_{2}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ since $\Psi_{2}$
is a facet of $K$. Thus, $2\in\overline{\chi}$. This implies that
$\chi_{i}\in\mathbf{F}_{L}$ for $i=3,4$. Therefore, we obtain
$\chi_{i}=\tau^{0}$ for $i=3,4$ since $\chi_{i}\supset\Psi_{i}=\tau^{0}$.

On the other hand, we have
$x\in\Psi_{1}\setminus\Phi_{1}=\Psi_{1}\setminus\tau^{0}$ since
$\Phi_{1}=\tau^{0}$. Then it follows from $\tau^{0}\subset\Psi_{1}$ that
$\tau^{0}\subset\Psi_{1}\setminus\\{x\\}=\chi_{1}\cap\Psi_{1}\subset\chi_{1}$.
If $\chi_{1}=\tau^{0}$, then we have $\overline{\chi}=\\{2\\}$ and
$\chi_{1}\in\mathbf{F}_{L}\setminus\mathbf{F}_{K}$. This contradicts to
Proposition 3.3 since $\chi$ is a facet of $\mathcal{Z}^{*}_{M}(K,L)$. So, we
get $\chi_{1}\supsetneq\tau^{0}$. However, this is also a contradiction to the
minimality of $\Psi$. Therefore, we conclude that $\mathcal{Z}^{*}_{M}(K,L)$
is not shellable. ∎

######  Theorem 4.3.

Let $M$ be a simplicial complex on $[m]$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i\in[m]}$ be a family of
pairs of simplicial complexes. Suppose that $M$ is shellable and that for any
$i\in[m]$,

  * •

there exists $\alpha_{i}\in\mathbf{F}_{K_{i}}$ such that
$\mathbf{F}_{L_{i}}\subset\\{\alpha_{i}\setminus\\{x\\}\ |\
x\in\alpha_{i}\\}$, and

  * •

$K_{i}$ is shellable with a shelling $<_{i}$ such that $\alpha_{i}$ is the
minimum element with respect to $<_{i}$.

Then $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ is shellable.

###### Proof.

We fix a shelling on $M$ and denote by $<_{M}$. Take an arbitrary linear order
$<^{\prime}_{i}$ on $\mathbf{F}_{L_{i}}$. Here we remark that we have
$\mathbf{F}_{K_{i}}\cap\mathbf{F}_{L_{i}}=\emptyset$ for any $i\in[m]$ since
we have $\tau\subsetneq\alpha_{i}$ for any $\tau\in\mathbf{F}_{L_{i}}$.

Let $\phi,\psi$ be facets of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. Consider a linear order
$<$ on $\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ such
that $\phi<\psi$ if and only if

  * •

$\overline{\phi}<_{M}\overline{\psi}$, or

  * •

$\overline{\phi}=\overline{\psi}$ and
$\phi_{1}=\psi_{1},\ldots,\phi_{j-1}=\psi_{j-1},\phi_{j}<_{j}\psi_{j}$ for
some $j\in\overline{\phi}$, or

  * •

$\overline{\phi}=\overline{\psi}$ and
$\phi_{1}=\psi_{1},\ldots,\phi_{j-1}=\psi_{j-1},\phi_{j}<^{\prime}_{j}\psi_{j}$
for some $j\notin\overline{\phi}$.

We show that this order is a shelling on
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$.

First, suppose that $\overline{\phi}<_{M}\overline{\psi}$. Then, by Lemma 2.1,
there exists $T\in\mathbf{F}_{M}$ and
$j\in\overline{\psi}\setminus\overline{\phi}$ such that
$T<_{M}\overline{\psi}$ and
$T\cap\overline{\psi}=\overline{\psi}\setminus\\{j\\}$. It follows from
$j\in\overline{\psi}\setminus\overline{\phi}$ that
$\psi_{j}\in\mathbf{F}_{K_{j}}$ and $\phi_{j}\in\mathbf{F}_{L_{j}}$.

If $\psi_{j}$ is not minimum with respect to $<_{j}$, namely
$\alpha_{j}<_{j}\psi_{j}$ in $\mathbf{F}_{K_{j}}$, then there exists
$\sigma\in\mathbf{F}_{K_{j}}$ and $x\in\psi_{j}\setminus\alpha_{j}$ such that
$\sigma<_{j}\psi_{j}$ and $\sigma\cap\psi_{j}=\psi_{j}\setminus\\{x\\}$. By
the assumption of the theorem, $\phi_{j}\in\mathbf{F}_{L_{j}}$ is a face of
$\alpha_{j}$. So, we get
$x\in\psi_{j}\setminus\phi_{j}\subset\psi\setminus\phi$. Now we define
$\chi\subset\bigsqcup_{i\in[m]}V(K_{i})$ by

$\displaystyle\chi_{i}=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\sigma&&(i=j).\end{aligned}\right.$

Since $\psi_{j},\sigma\in\mathbf{F}_{K_{j}}$, we have
$\overline{\chi}=\overline{\psi}\in\mathbf{F}_{M}$. Thus, by Proposition 3.3,
$\chi$ is a facet of $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$.
Furthermore, we have $\chi<\psi$ since

$\displaystyle\chi_{1}=\psi_{1},\ldots,\chi_{j-1}=\psi_{j-1},\chi_{j}=\sigma<_{j}\psi_{j}.$

Moreover, we have

$\displaystyle\chi_{i}\cap\psi_{i}$ $\displaystyle=\left\\{\begin{aligned}
&\psi_{i}&&(i\neq j)\\\ &\sigma\cap\psi_{j}&&(i=j)\end{aligned}\right.$
$\displaystyle=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\psi_{j}\setminus\\{x\\}&&(i=j),\end{aligned}\right.$

namely

$\displaystyle\chi\cap\psi=\psi\setminus\\{x\\}.$

By the above argument, we get
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\psi\setminus\phi$ such that $\chi<\psi$ and
$\chi\cap\psi=\psi\setminus\\{x\\}$.

If $\psi_{j}=\alpha_{j}$, then it follows from the assumption of the theorem
that there exists $x\in\alpha_{j}$ such that
$\phi_{j}=\alpha_{j}\setminus\\{x\\}$. In this case, we define
$\chi\subset\bigsqcup_{i\in[m]}V(K_{i})$ by

$\displaystyle\chi_{i}=\left\\{\begin{aligned}
&\psi_{i}\in\mathbf{F}_{K_{i}}&&(i\in T\cap\overline{\psi})\\\
&\phi_{j}\in\mathbf{F}_{L_{j}}&&(i=j),\\\
&\alpha_{i}\in\mathbf{F}_{K_{i}}&&(i\in T\setminus\overline{\psi}),\\\
&\psi_{i}\in\mathbf{F}_{L_{i}}&&(i\in[m]\setminus(T\cup\overline{\psi})).\\\
\end{aligned}\right.$

Then we have

$\displaystyle\overline{\chi}=(T\cap\overline{\psi})\cup(T\setminus\overline{\psi})=T.$

Hence, $\chi$ is a facet of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. It follows from
$T<_{M}\overline{\psi}$ that $\overline{\chi}<_{M}\overline{\psi}$.
Furthermore, since $\psi_{i}$ is a face of $\alpha_{i}$ if
$\psi_{i}\in\mathbf{F}_{L_{i}}$, we have

$\displaystyle\chi_{i}\cap\psi_{i}$ $\displaystyle=\left\\{\begin{aligned}
&\psi_{i}&&(i\in(T\cap\overline{\psi})\cup([m]\setminus(T\cup\overline{\phi}))),\\\
&\phi_{j}\cap\psi_{j}&&(i=j),\\\ &\alpha_{i}\cap\psi_{i}&&(i\in
T\setminus\overline{\psi})\end{aligned}\right.$
$\displaystyle=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\psi_{j}\setminus\\{x\\}&&(i=j).\end{aligned}\right.$

The last equality follows from

$\displaystyle\phi_{j}\cap\psi_{j}=(\alpha_{j}\setminus\\{x\\})\cap\alpha_{j}=\alpha_{j}\setminus\\{x\\}=\psi_{j}\setminus\\{x\\}.$

By the above argument, we get
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\psi\setminus\phi$ such that $\chi<\psi$ and
$\chi\cap\psi=\psi\setminus\\{x\\}$.

Next, suppose that $\overline{\phi}=\overline{\psi}$ and
$\phi_{1}=\psi_{1},\ldots,\phi_{j-1}=\psi_{j-1},\phi_{j}<_{j}\psi_{j}$ for
some $j\in\overline{\phi}$. There exists $\sigma\in\mathbf{F}_{K_{j}}$ and
$x\in\psi_{j}\setminus\phi_{j}$ such that $\sigma<_{j}\psi_{j}$ and
$\sigma\cap\psi_{j}=\psi_{j}\setminus\\{x\\}$. We define
$\chi\subset\bigsqcup_{i\in[m]}V(K_{i})$ by

$\displaystyle\chi_{i}=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\sigma&&(i=j).\end{aligned}\right.$

We have $\psi_{j}\in\mathbf{F}_{K_{j}}$ since
$j\in\overline{\phi}=\overline{\psi}$. So, it follows from
$\sigma\in\mathbf{F}_{K_{j}}$ that $\overline{\chi}=\overline{\psi}$. Hence,
$\chi$ is a facet of $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. By
the same argument as the first case, we see that
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\psi\setminus\phi$ satisfy $\chi<\psi$ and
$\chi\cap\psi=\psi\setminus\\{x\\}$.

Finally, suppose that $\overline{\phi}=\overline{\psi}$ and
$\phi_{1}=\psi_{1},\ldots,\phi_{j-1}=\psi_{j-1},\phi_{j}<^{\prime}_{j}\psi_{j}$
for some $j\notin\overline{\phi}$. By the assumption of the theorem, there
exists $x,y\in\alpha_{j}$ ($x\neq y$) such that
$\phi_{j}=\alpha_{j}\setminus\\{x\\}$, $\psi_{j}=\alpha_{j}\setminus\\{y\\}$.
So, we have
$\phi_{j}\cap\psi_{j}=\alpha_{j}\setminus\\{x,y\\}=\psi_{j}\setminus\\{x\\}$
since $x\neq y$. Here we define $\chi\subset\bigsqcup_{i\in[m]}V(K_{i})$ by

$\displaystyle\chi_{i}=\left\\{\begin{aligned} &\psi_{i}&&(i\neq j)\\\
&\phi_{j}&&(i=j).\end{aligned}\right.$

We have $\phi_{j},\psi_{j}\in\mathbf{F}_{L_{j}}$ since
$j\in\overline{\phi}=\overline{\psi}$. So, it follows that
$\overline{\chi}=\overline{\psi}$. Hence, $\chi$ is a facet of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. By the same argument as
the first case, we see that
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\psi\setminus\phi$ satisfy $\chi<\psi$ and
$\chi\cap\psi=\psi\setminus\\{x\\}$.

In all four cases above, we obtain
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\psi\setminus\phi$ which satisfy $\chi<\psi$ and
$\chi\cap\psi=\psi\setminus\\{x\\}$. By Lemma 2.1, we conclude that
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ is shellable. ∎

######  Remark 4.4.

Consider $M=\langle\\{1\\},\\{2\\}\rangle$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i=1,2}$ such that

$\displaystyle K_{i}=\langle\\{a_{i},b_{i}\\},\\{b_{i},c_{i}\\}\rangle,\
L_{i}=\langle\\{a_{i}\\},\\{c_{i}\\}\rangle.$

Then we see that

$\displaystyle\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})=$
$\displaystyle\langle\\{a_{1},b_{1},a_{2}\\},\\{a_{1},b_{1},c_{2}\\},\\{b_{1},c_{1},a_{2}\\},\\{b_{1},c_{1},c_{2}\\},$
$\displaystyle\
\\{a_{1},a_{2},b_{2}\\},\\{a_{1},b_{2},c_{2}\\},\\{c_{1},a_{2},b_{2}\\},\\{c_{1},b_{2},c_{2}\\}\rangle$

(see Figure 1) is shellable. However, there is no
$\alpha_{i}\in\\{\\{a_{i},b_{i}\\},\\{b_{i},c_{i}\\}\\}$ such that
$\\{a_{i}\\},\\{c_{i}\\}\subset\alpha_{i}$. So, the condition that
$\mathbf{F}_{L_{i}}\subset\\{\alpha_{i}\setminus\\{x\\}\in K\ |\
x\in\alpha_{i}\\}$ for some $\alpha_{i}\in\mathbf{F}_{K_{i}}$ is not necessary
for $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ being shellable.

$*$$c_{1}$$b_{1}$$a_{1}$$c_{2}$$a_{2}$ |  | $\cup$ |  | $*$$c_{1}$$b_{2}$$a_{1}$$c_{2}$$a_{2}$
---|---|---|---|---
Figure 1. $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ in Remark 4.4

######  Example 4.5.

Let $K$ be a simplicial complex on $[m]$ and $J=(j_{1},\ldots,j_{m})$ be a
tuple of positive integers. Define families of pairs of simplicial complexes
as follows:

$\displaystyle(\underline{\Delta^{J-1}},\underline{\partial\Delta^{J-1}})$
$\displaystyle=\\{(\Delta^{j_{i}-1},\partial\Delta^{j_{i}-1})\\}_{i\in[m]},$
$\displaystyle(\underline{\mathrm{pt}^{J}},\\{\emptyset\\})$
$\displaystyle=\left\\{\left({\bigsqcup}_{j_{i}}\mathrm{pt},\\{\emptyset\\}\right)\right\\}_{i\in[m]}.$

By Theorem 4.3,
$\mathcal{Z}^{*}_{K}(\underline{\Delta^{J-1}},\underline{\partial{\Delta^{J-1}}})$
and $\mathcal{Z}^{*}_{K}(\underline{\mathrm{pt}^{J}},\\{\emptyset\\})$ are
shellable if $K$ is shellable.

Next, we state a necessary condition for $\mathcal{Z}^{*}_{M}(K,L)$ being
shellable under a certain assumption.

######  Theorem 4.6.

Let $M$ be a simplicial complex which is not a simplex and $K\supsetneq L$ be
a pair of simplicial complexes such that
$\mathbf{F}_{L}\subset\mathbf{F}_{K}$. If $\mathcal{Z}^{*}_{M}(K,L)$ is
shellable, then both $K$ and $L$ are shellable.

###### Proof.

We set $V(M)=[m]$. Let
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i\in[m]}$ be a family of
pairs of simplicial complexes such that $K_{i}=K$, $L_{i}=L$ for any
$i\in[m]$. Fix a shelling $<$ on
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$. Take $S\in\mathbf{F}_{M}$
and $k\in[m]$ such that $k\notin S$. This is possible since $M$ is not a
simplex. We prove that both $K_{k}$ and $L_{k}$ are shellable.

First, we prove that $K_{k}$ is shellable. For a facet
$\sigma\in\mathbf{F}_{K_{k}}$, define
$\Phi^{\sigma}\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$
by

$\displaystyle\Phi^{\sigma}=\min\left\\{\phi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}\
\middle|\ \phi_{k}=\sigma\right\\}.$

Note that $\Phi^{\sigma}$ is well-defined since by Remark 3.4, there exists a
facet $\phi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$
such that

$\displaystyle\phi_{i}=\left\\{\begin{aligned} &\sigma&&(i=k)\\\ &\tau&&(i\neq
k),\end{aligned}\right.$

where $\tau$ is an arbitrary facet of $L$. For
$\sigma,\sigma^{\prime}\in\mathbf{F}_{K_{k}}$, we define a relation
$\sigma<_{K}\sigma^{\prime}$ by $\Phi^{\sigma}<\Phi^{\sigma^{\prime}}$. It is
obvious that $<_{K}$ defines a linear order on $\mathbf{F}_{K_{k}}$. We prove
that $<_{K}$ is a shelling on $K_{k}$.

For $\sigma^{\prime},\sigma\in\mathbf{F}_{K_{k}}$ such that
$\Phi^{\sigma^{\prime}}<\Phi^{\sigma}$, there exists
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\Phi^{\sigma}\setminus\Phi^{\sigma^{\prime}}$ such that
$\chi<\Phi^{\sigma}$ and
$\chi\cap\Phi^{\sigma}=\Phi^{\sigma}\setminus\\{x\\}$. If
$x\notin\Phi^{\sigma}_{k}$, then we have
$\chi_{k}\cap\Phi^{\sigma}_{k}=\Phi^{\sigma}_{k}$, which means that
$\Phi^{\sigma}_{k}\subset\chi_{k}$. By Proposition 3.3, $\Phi^{\sigma}_{k}$
and $\chi_{k}$ are facets of $K_{k}$ since
$\mathbf{F}_{K_{k}}\cup\mathbf{F}_{L_{k}}=\mathbf{F}_{K_{k}}$. So, we obtain
$\chi_{k}=\Phi^{\sigma}_{k}=\sigma$. This contradicts to the minimality of
$\Phi^{\sigma}$. Hence, we get $x\in\Phi^{\sigma}_{k}$. Moreover, it follows
from $x\in\Phi^{\sigma}\setminus\Phi^{\sigma^{\prime}}$ that
$x\in\Phi^{\sigma}_{k}\setminus\Phi^{\sigma^{\prime}}_{k}=\sigma\setminus\sigma^{\prime}$.

By $\chi\cap\Phi^{\sigma}=\Phi^{\sigma}\setminus\\{x\\}$ and
$x\in\Phi^{\sigma}_{k}$, we obtain
$\chi_{k}\cap\sigma=\chi_{k}\cap\Phi^{\sigma}_{k}=\Phi^{\sigma}_{k}\setminus\\{x\\}=\sigma\setminus\\{x\\}$.
Furthermore, we get $\Phi^{\chi_{k}}<\chi<\Phi^{\sigma}$. Therefore,
$\chi_{k}\in\mathbf{F}_{K_{k}}$ and $x\in\sigma\setminus\sigma^{\prime}$
satisfy $\chi_{k}<_{K}\sigma$ and $\chi_{k}\cap\sigma=\sigma\setminus\\{x\\}$.
By Lemma 2.1, $<_{K}$ is a shelling on $K_{k}$.

Next, we prove that $L_{k}$ is shellable. There exists
$\sigma^{0}\in\mathbf{F}_{K_{k}}\setminus\mathbf{F}_{L_{k}}$ since $K\neq L$.
For a facet $\tau\in\mathbf{F}_{L_{k}}$, define
$\Psi^{\tau}\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$
by

$\displaystyle\Psi^{\tau}=\min\left\\{\psi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}\
\middle|\ \psi_{i}=\sigma^{0}\text{ for any }i\in S,\text{ and
}\psi_{k}=\tau\right\\}.$

Note that $\Psi^{\tau}$ is well-defined. This is because there exists a facet
$\psi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ defined
by

$\displaystyle\psi_{i}=\left\\{\begin{aligned} &\sigma^{0}&&(i\in S)\\\
&\tau&&(i\notin S).\end{aligned}\right.$

For $\tau,\tau^{\prime}\in\mathbf{F}_{L_{k}}$, we define a relation
$\tau<_{L}\tau^{\prime}$ by $\Psi^{\tau}<\Psi^{\tau^{\prime}}$. It is obvious
that $<_{L}$ defines a linear order on $\mathbf{F}_{L_{k}}$. We prove that
$<_{L}$ is a shelling on $L_{k}$.

For $\tau^{\prime},\tau\in\mathbf{F}_{L_{k}}$ such that
$\Psi^{\tau^{\prime}}<\Psi^{\tau}$, there exists
$\chi\in\mathbf{F}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}$ and
$x\in\Psi^{\tau}\setminus\Psi^{\tau^{\prime}}$ such that $\chi<\Psi^{\tau}$
and $\chi\cap\Psi^{\tau}=\Psi^{\tau}\setminus\\{x\\}$. Let $j\in[m]$ be a
vertex of $M$ such that
$x\in\Psi^{\tau}_{j}\setminus\Psi^{\tau^{\prime}}_{j}$. Then we have $j\notin
S$ since $\Psi^{\tau}_{j}\neq\Psi^{\tau^{\prime}}_{j}$. So, for any $i\in S$,
we get $\chi_{i}\cap\Psi^{\tau}_{i}=\Psi^{\tau}_{i}$, namely
$\chi_{i}\supset\Psi^{\tau}_{i}=\sigma^{0}$. It follows from
$\sigma^{0}\in\mathbf{F}_{K_{k}}$ that $\chi_{i}=\sigma^{0}$ for any $i\in S$.
Hence, by the minimality of $\Psi^{\tau}$, we get $\chi_{k}\neq\tau$. On the
other hand, we get $\overline{\chi}=S$ since $S$ is a facet of $M$ and
$S\subset\overline{\chi}$. So, we have $k\notin S=\overline{\chi}$, which
means that $\chi_{k}\in\mathbf{F}_{L_{k}}$. Therefore, if $j\neq k$, we obtain
$\chi_{k}\supsetneq\tau$ and $\chi_{k},\tau\in\mathbf{F}_{L_{k}}$, a
contradiction. Thus, we conclude that $j=k$. Hence, we get
$x\in\Psi^{\tau}_{k}\setminus\Psi^{\tau^{\prime}}_{k}$ and
$\chi_{k}\cap\Psi^{\tau}_{k}=\Psi^{\tau}_{k}\setminus\\{x\\}$, namely
$x\in\tau\setminus\tau^{\prime}$ and $\chi_{k}\cap\tau=\tau\setminus\\{x\\}$.
Moreover, we have $\Psi^{\chi_{k}}<\chi$ since $\chi_{i}=\sigma^{0}$ for any
$i\in S$ and $\chi_{k}\in\mathbf{F}_{L_{k}}$. Hence, by $\chi<\Psi^{\tau}$, we
obtain $\Psi^{\chi_{k}}<\Psi^{\tau}$, namely $\chi_{k}<_{L}\tau$. By Lemma
2.1, $<_{L}$ is a shelling on $L_{k}$. ∎

######  Remark 4.7.

In general, the shellability of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ does not imply the
shellability of each $K_{i}$. For example, consider
$M=\langle\\{1\\},\\{2\\}\rangle$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i=1,2}$ such that

$\displaystyle K_{1}=\langle\\{a,b\\},\\{c,d\\}\rangle,$ $\displaystyle
L_{1}=\langle\\{b\\},\\{c,d\\}\rangle,$ $\displaystyle
K_{2}=\langle\\{e,f\\}\rangle,$ $\displaystyle L_{2}=\langle\\{f\\}\rangle.$

Then we see that

$\displaystyle\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})=\langle\\{c,d,e,f\\},\\{b,e,f\\},\\{a,b,f\\}\rangle$

(see Figure 2) is shellable. However, $K_{1}$ is not shellable.

$*$$d$$c$$b$$a$$f$ |  | $\cup$ |  | $*$$d$$c$$b$$f$$e$
---|---|---|---|---
Figure 2. $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ in Remark 4.7

######  Remark 4.8.

The shellability of $\mathcal{Z}^{*}_{M}(K,L)$ does not imply
$\mathbf{F}_{L}\subset\mathbf{F}_{K}$. For example, consider
$M=\langle\\{1\\},\\{2\\}\rangle$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i=1,2}$ such that

$\displaystyle K_{i}=\langle\\{a_{i},b_{i}\\}\rangle,\
L_{i}=\langle\\{b_{i}\\}\rangle.$

Then we see that

$\displaystyle\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})=\langle\\{a_{1},b_{1},b_{2}\\},\\{b_{1},a_{2},b_{2}\\}\rangle$

is shellable. However,
$\\{b_{i}\\}\in\mathbf{F}_{L_{i}}\setminus\mathbf{F}_{K_{i}}$ for $i=1,2$.

Even though $(K,L)$ satisfies that $K$ is shellable, $L$ is shellable and
$\mathbf{F}_{L}\subset\mathbf{F}_{K}$, $\mathcal{Z}^{*}_{M}(K,L)$ is not
necessarily shellable. In order to show this, we prove another necessary
condition.

######  Theorem 4.9.

Let $M$ be a simplicial complex which is not a simplex and $K\supsetneq L$ be
a pair of simplicial complexes. Suppose that $\mathcal{Z}^{*}_{M}(K,L)$ is
shellable. Then there exists a pair $(\sigma,\tau)$ of
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ and $\tau\in\mathbf{F}_{L}$
such that

$\displaystyle|\sigma\cap\tau|=\max_{\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}}|\rho|-1.$

###### Proof.

Fix a shelling $\phi^{1}<\cdots<\phi^{t}$ on $\mathcal{Z}^{*}_{M}(K,L)$ such
that $|\phi^{p}|\geq|\phi^{q}|$ for any $1\leq p<q\leq t$, which exists by
Lemma 2.2.

We first show that there exists an index $s$ such that
$\overline{\phi^{p}}\nsupseteq\overline{\phi^{s}}$ for any $p\in[s-1]$. Since
$M$ is not a simplex, there exists $j\in[m]$ such that
$j\notin\overline{\phi^{1}}$. Take a facet $S\ni j$ of $M$. Here, it follows
from $K\neq L$ that there exists a facet
$\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ of $K$. Now, consider a subset
$\psi\subset\bigsqcup_{i\in[m]}V(K)$ which satisfies

  * •

if $i\in S$, then $\psi_{i}=\rho$,

  * •

if $i\notin S$, then $\psi_{i}\in\mathbf{F}_{L}$.

We have $\psi_{i}\in\mathbf{F}_{K}\cup\mathbf{F}_{L}$ for any $i\in[m]$,
$\overline{\psi}=S\in M$ and $\overline{\psi}\cup\\{i\\}\notin M$ for any
$i\notin S$ since $S$ is a facet of $M$. By Proposition 3.3, $\psi$ is a facet
of $\mathcal{Z}^{*}_{M}(K,L)$. Therefore, we have $\psi=\phi^{q}$ for some
$q\in[t]$. Since $j\in
S\setminus\overline{\phi^{1}}=\overline{\phi^{q}}\setminus\overline{\phi^{1}}$,
we get $\overline{\phi^{q}}\nsubseteq\overline{\phi^{1}}$. Now we set
$s=\min\\{r\in[t]\ |\ \overline{\phi^{r}}\nsubseteq\overline{\phi^{1}}\\}$. It
follows from the minimality of $s$ that
$\overline{\phi^{p}}\subset\overline{\phi^{1}}$ for any $p\in[s-1]$. Thus, we
get $\overline{\phi^{s}}\nsubseteq\overline{\phi^{p}}$ for any $p\in[s-1]$ as
desired.

Now, take an index $s$ as above. For an index $p^{\prime}$ such that
$\overline{\phi^{p^{\prime}}}=\overline{\phi^{s}}$, $p^{\prime}$ must be
larger than $s$, which implies $|\phi^{p^{\prime}}|\leq|\phi^{s}|$. So,
$\phi^{s}$ is the largest facet among facets $\phi$ such that
$\overline{\phi}=\overline{\phi^{s}}$. By the definition of a shelling, there
must exist $p$ with $1\leq p<s$ such that
$|\phi^{p}\cap\phi^{s}|=|\phi^{s}|-1$. This equality implies that we have

$\displaystyle|\phi^{p}_{i}\cap\phi^{s}_{i}|\geq|\phi^{s}_{i}|-1$

for any $i\in[m]$. On the other hand, it follows from
$\overline{\phi^{p}}\nsupseteq\overline{\phi^{s}}$ that there exists
$j\in\overline{\phi^{s}}\setminus\overline{\phi^{p}}$, namely $j\in[m]$ such
that $\phi^{p}_{j}\in\mathbf{F}_{L}$ and
$\phi^{s}_{j}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$. Since $\phi^{s}_{j}$
is a facet of $K$, we have
$\phi^{p}_{j}\cap\phi^{s}_{j}\subsetneq\phi^{s}_{j}$. Thus, we get

$\displaystyle|\phi^{p}_{j}\cap\phi^{s}_{j}|=|\phi^{s}_{j}|-1.$

Assume that there exists $\mu\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ such
that $|\mu|>|\phi^{s}_{j}|$. Then, a subset
$\chi\subset\bigsqcup_{i\in[m]}V(K)$ defined by

$\displaystyle\chi_{i}=\left\\{\begin{aligned} &\phi^{s}_{i}&&(i\neq j)\\\
&\mu&&(i=j)\end{aligned}\right.$

is a facet of $\mathcal{Z}^{*}_{M}(K,L)$. Since $|\chi|>|\phi^{s}|$ and
$\overline{\chi}=\overline{\phi^{s}}$, this contradicts to the maximality of
$|\phi^{s}|$. Hence, we obtain
$|\phi^{s}_{j}|=\max_{\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}}|\rho|$.

Then, $\sigma=\phi^{s}_{j}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ and
$\tau=\phi^{p}_{j}\in\mathbf{F}_{L}$ satisfy

$\displaystyle|\sigma\cap\tau|=|\sigma|-1=\max_{\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}}|\rho|-1,$

which is the desired conclusion. ∎

######  Example 4.10.

Consider $M=\langle\\{1\\},\\{2\\}\rangle$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i=1,2}$ such that

$\displaystyle
K_{i}=\langle\\{a_{i},b_{i}\\},\\{b_{i},c_{i}\\},\\{d_{i}\\}\rangle,\
L_{i}=\langle\\{c_{i}\\},\\{d_{i}\\}\rangle.$

For $\\{a_{i},b_{i}\\}\in\mathbf{F}_{K_{i}}\setminus\mathbf{F}_{L_{i}}$, there
exists no $\tau\in\mathbf{F}_{L_{i}}$ such that
$|\\{a_{i},b_{i}\\}\cap\tau|=1$. For $\\{d_{i}\\}\in\mathbf{F}_{L_{i}}$, there
exists no $\sigma\in\mathbf{F}_{K_{i}}\setminus\mathbf{F}_{L_{i}}$ such that
$|\sigma\cap\\{d_{i}\\}|=1$. On the other hand, we see that

$\displaystyle\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})=$
$\displaystyle\langle\\{a_{1},b_{1},c_{2}\\},\\{b_{1},c_{1},c_{2}\\},\\{b_{1},c_{1},d_{2}\\},\\{a_{1},b_{1},d_{2}\\},$
$\displaystyle\
\\{c_{1},b_{2},c_{2}\\},\\{d_{1},b_{2},c_{2}\\},\\{d_{1},a_{2},b_{2}\\},\\{c_{1},a_{2},b_{2}\\},\\{d_{1},d_{2}\\}\rangle$

(see Figure 3) is shellable. So, Theorem 4.9 only guarantees the existence of
at least one pair $(\sigma,\tau)$, in this example, $\sigma=\\{b_{i},c_{i}\\}$
and $\tau=\\{c_{i}\\}$.

$*$$d_{1}$$c_{1}$$b_{1}$$a_{1}$$c_{2}$$d_{2}$ |  | $\cup$ |  | $*$$d_{1}$$c_{1}$$b_{2}$$a_{2}$$c_{2}$$d_{2}$
---|---|---|---|---
Figure 3. $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ in Example 4.10

######  Remark 4.11.

The converse of Theorem 4.6 and the converse of Theorem 4.9 do not hold.
Consider $M=\langle\\{1\\},\\{2\\}\rangle$ and
$(\underline{K},\underline{L})=\\{(K_{i},L_{i})\\}_{i=1,2}$ such that

$\displaystyle
K_{i}=\langle\\{a_{i},b_{i},c_{i}\\},\\{a_{i},c_{i},d_{i}\\},\\{b_{i},d_{i}\\}\rangle,\
L_{i}=\langle\\{a_{i},b_{i},c_{i}\\},\\{b_{i},d_{i}\\}\rangle.$

Two facets
$\\{a_{i},c_{i},d_{i}\\}\in\mathbf{F}_{K_{i}}\setminus\mathbf{F}_{L_{i}}$ and
$\\{a_{i},b_{i},c_{i}\\}\in\mathbf{F}_{L_{i}}$ satisfy the condition in
Theorem 4.9. Moreover, both $K=K_{1}=K_{2}$ and $L=L_{1}=L_{2}$ are shellable
and $\mathbf{F}_{L}\subset\mathbf{F}_{K}$. However,

$\displaystyle\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})=$
$\displaystyle\langle\\{a_{1},b_{1},c_{1},a_{2},b_{2},c_{2}\\},\\{a_{1},c_{1},d_{1},a_{2},b_{2},c_{2}\\},$
$\displaystyle\
\\{a_{1},b_{1},c_{1},a_{2},c_{2},d_{2}\\},\\{a_{1},b_{1},c_{1},b_{2},d_{2}\\},\\{a_{1},c_{1},d_{1},b_{2},d_{2}\\},$
$\displaystyle\
\\{b_{1},d_{1},a_{2},b_{2},c_{2}\\},\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\},\\{b_{1},d_{1},b_{2},d_{2}\\}\rangle$

(see Figure 4) is not shellable. To see this, assume that
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ is shellable and
$\\{a_{1},c_{1},d_{1},b_{2},d_{2}\\}<\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\}$ in a
shelling. There must exists a facet
$\phi\neq\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\}$ of
$\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ and
$x\in\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\}\setminus\\{a_{1},c_{1},d_{1},b_{2},d_{2}\\}=\\{b_{1},a_{2},c_{2}\\}$
such that $\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\}\setminus\\{x\\}\subset\phi$.
However, there is no facet $\phi\neq\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\}$ such
that $\phi$ includes
$\\{d_{1},a_{2},c_{2},d_{2}\\},\\{b_{1},d_{1},c_{2},d_{2}\\}$ or
$\\{b_{1},d_{1},a_{2},d_{2}\\}$. This is a contradiction. In the same way, we
also get
$\\{b_{1},d_{1},a_{2},c_{2},d_{2}\\}\nleq\\{a_{1},c_{1},d_{1},b_{2},d_{2}\\}$.
So, $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ has no shelling.

$c_{1}$$a_{1}$$b_{1}$$d_{1}$$*$$c_{2}$$a_{2}$$b_{2}$$d_{2}$ | $\cup$ | $c_{1}$$a_{1}$$b_{1}$$d_{1}$$*$$c_{2}$$a_{2}$$b_{2}$$d_{2}$
---|---|---
Figure 4. $\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})$ in Remark 4.11

######  Corollary 4.12.

Let $M$ be a simplicial complex and $K\supset L$ be a pair of simplicial
complexes. If $\dim K-\dim L\geq 2$, then $\mathcal{Z}^{*}_{M}(K,L)$ is not
shellable.

In particular, for any simplicial complex $M$ and $K$ such that $\dim K\geq
1$, $\mathcal{Z}^{*}_{M}(K,\\{\emptyset\\})$ is not shellable.

###### Proof.

It follows from $\dim K>\dim L$ that there must be $\rho\in\mathbf{F}_{K}$
such that $|\rho|=\dim K+1$ and $\rho\notin\mathbf{F}_{L}$. So, we get

$\displaystyle\dim
K=\max_{\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}}|\rho|-1.$

For any $\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ and
$\tau\in\mathbf{F}_{L}$, we have

$\displaystyle|\sigma\cap\tau|\leq|\tau|\leq\dim L+1\leq\dim
K-1=\max_{\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}}|\rho|-2.$

Therefore, there is no pair $(\sigma,\tau)$ of
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ and $\tau\in\mathbf{F}_{L}$
such that

$\displaystyle|\sigma\cap\tau|=\max_{\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}}|\rho|-1.$

By Theorem 4.9, we conclude that $\mathcal{Z}^{*}_{M}(K,L)$ is not shellable.
∎

As the last result in this section, we prove that under a certain condition,
the shellability of both $K$ and $L$ is equivalent to the shellability of
$\mathcal{Z}^{*}_{M}(K,L)$.

######  Theorem 4.13.

Let $M$ be a simplicial complex which is not a simplex and $K$ be a simplicial
complex. For a vertex $v_{0}$ of $K$, suppose that
$\mathbf{F}_{\mathrm{dl}_{K}(v_{0})}\subset\mathbf{F}_{K}$. Then
$\mathcal{Z}^{*}_{M}(K,\mathrm{dl}_{K}(v_{0}))$ is shellable if and only if
both $K$ and $\mathrm{dl}_{K}(v_{0})$ are shellable.

###### Proof.

We set $L=\mathrm{dl}_{K}(v_{0})$. If $\mathcal{Z}^{*}_{M}(K,L)$ is shellable
and $\mathbf{F}_{L}\subset\mathbf{F}_{K}$, then by Theorem 4.6, $K$ and $L$
are shellable. In order to prove the converse, it is sufficient to show that
there is a shelling $<_{K}$ on $K$ such that $\tau<_{K}\sigma$ for any
$\tau\in\mathbf{F}_{L}$ and any
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$. Then the proof is completed
by Theorem 4.1.

Let $<$ be a shelling on $K$ and $<^{\prime}$ be a shelling on $L$. Define a
relation $<_{K}$ on $\mathbf{F}_{K}$ by

  * •

$\tau<_{K}\sigma$ for any $\tau\in\mathbf{F}_{L}$ and
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$,

  * •

for any $\tau,\tau^{\prime}\in\mathbf{F}_{L}$, $\tau<_{K}\tau^{\prime}$ if and
only if $\tau<^{\prime}\tau^{\prime}$, and

  * •

for any $\sigma,\sigma^{\prime}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$,
$\sigma<_{K}\sigma^{\prime}$ if and only if $\sigma<\sigma^{\prime}$.

It is obvious that $<_{K}$ is a linear order. We prove that $<_{K}$ is a
shelling on $K$. The goal of the proof is to show that for any
$\rho,\rho^{\prime}\in\mathbf{F}_{K}$ such that $\rho<_{K}\rho^{\prime}$,
there exists $\rho^{\prime\prime}\in\mathbf{F}_{K}$ and
$u\in\rho^{\prime}\setminus\rho$ which satisfy
$\rho^{\prime\prime}<_{K}\rho^{\prime}$ and
$\rho^{\prime\prime}\cap\rho^{\prime}=\rho^{\prime}\setminus\\{u\\}$.

For any $\tau,\tau^{\prime}\in\mathbf{F}_{L}$ such that
$\tau<^{\prime}\tau^{\prime}$, there exists
$\tau^{\prime\prime}\in\mathbf{F}_{L}$ and $x\in\tau^{\prime}\setminus\tau$
such that $\tau^{\prime\prime}<^{\prime}\tau^{\prime}$ and
$\tau^{\prime\prime}\cap\tau^{\prime}=\tau^{\prime}\setminus\\{x\\}$. Since
$\tau^{\prime\prime}\in\mathbf{F}_{L}$ and
$\tau^{\prime\prime}<^{\prime}\tau^{\prime}$, we get
$\tau^{\prime\prime}<_{K}\tau^{\prime}$.

For any $\sigma,\sigma^{\prime}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$ such
that $\sigma<\sigma^{\prime}$, there exists $\rho\in\mathbf{F}_{K}$ and
$x\in\sigma^{\prime}\setminus\sigma$ such that $\rho<\sigma^{\prime}$ and
$\rho\cap\sigma^{\prime}=\sigma^{\prime}\setminus\\{x\\}$. If
$\rho\in\mathbf{F}_{L}$, then we obtain $\rho<_{K}\sigma^{\prime}$ since
$\sigma^{\prime}\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$. If
$\rho\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$, then we obtain
$\rho<_{K}\sigma^{\prime}$ again since $\rho<\sigma^{\prime}$. In both cases,
we have $\rho<_{K}\sigma^{\prime}$.

For $\tau\in\mathbf{F}_{L}$ and
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$, we have
$v_{0}\in\sigma\setminus\tau$ since $\sigma\notin\mathrm{dl}_{K}(v_{0})$ and
$\tau\in\mathrm{dl}_{K}(v_{0})$. A simplex $\sigma\setminus\\{v_{0}\\}\in L$
is not a facet of $L$ since $\sigma\setminus\\{v_{0}\\}$ is not a facet of $K$
and we have $\mathbf{F}_{L}\subset\mathbf{F}_{K}$ by the assumption.
Therefore, there exists a facet $\rho\in\mathbf{F}_{L}$ such that
$\rho\supsetneq\sigma\setminus\\{v_{0}\\}$. Since
$\rho\in\mathrm{dl}_{K}(v_{0})$, we obtain
$\rho\cap\sigma=\sigma\setminus\\{v_{0}\\}$. We also get $\rho<_{K}\sigma$
because $\rho\in\mathbf{F}_{L}$ and
$\sigma\in\mathbf{F}_{K}\setminus\mathbf{F}_{L}$. ∎

##  5\. Applications to the shellability of graphs

In this section, we prove Theorem 1.2. Here we introduce a class of graphs
which are constructed from two graphs $G,H$ and a subset $U\subset V(H)$. In
the following, a set $\\{u,v\\}\subset V(G)$ of two vertices of a graph $G$ is
denoted by $uv$.

######  Definition 5.1.

Let $G,H$ be graphs and $U\subset V(H)$ be a subset of $V(H)$. We define a
graph $G[H;U]$ by

$\displaystyle V(G[H;U])$ $\displaystyle=V(G)\times V(H),$ $\displaystyle
E(G[H;U])$ $\displaystyle=\left\\{(u_{1},v_{1})(u_{2},v_{2})\ \middle|\
\left.\begin{aligned} &u_{1}=u_{2}\text{ and }v_{1}v_{2}\in E(H),\\\ &\text{
or }\\\ &u_{1}u_{2}\in E(G)\text{ and }v_{1},v_{2}\in
U\end{aligned}\right.\right\\}.$

$G$$H$$U$ |  | $\rightarrow$ |  | $G[H;U]$
---|---|---|---|---
Figure 5. An example of $G[H;U]$

######  Example 5.2.

For graphs $G$ and $H$, $G[H;V(H)]$ is the lexicographic product $G[H]$. The
definition of the lexicographic product of two graphs is given in, for
example, [5].

######  Example 5.3.

Let $G,H$ be graphs and $v_{0}$ be a vertex of $H$. As defined in Section 1,
$G[H;\\{v_{0}\\}]$ is the graph obtained from $G\sqcup\left(\bigsqcup_{u\in
V(G)}H_{u}\right)$ by identifying $u\in V(G)$ with $v_{0}\in H_{u}$, where
$H_{u}$ is a copy of $H$.

The independence complex of $G[H;U]$ is described as a polyhedral join, stated
in the following proposition.

######  Proposition 5.4.

Let $G,H$ be graphs and $U\subset V(H)$ be a subset of $V(H)$. Then we have

$\displaystyle I(G[H;U])=\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus U)),$

where $H\setminus U$ is a graph defined by $V(H\setminus U)=V(H)\setminus U$
and $E(H\setminus U)=\\{uv\in E(H)\ |\ u,v\notin U\\}$.

###### Proof.

Remark that for $\phi\subset V(G)\times
V(H)=V(\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus U)))$, $\phi_{u}$ ($u\in
V(G)$) and $\overline{\phi}$ in Proposition 3.2 are reformulated as follows:

$\displaystyle\phi_{u}$ $\displaystyle=\\{v\in V(H)\ |\ (u,v)\in\phi\\},$
$\displaystyle\overline{\phi}$ $\displaystyle=\\{u\in V(G)\ |\ \phi_{u}\cap
U\neq\emptyset\\}.$

Let $\phi\in I(G[H;U])$ be an independent set of $G[H;U]$. Then, we have the
followings.

  * •

For any $u\in V(G)$ and $v_{1},v_{2}\in V(H)$, suppose that
$v_{1},v_{2}\in\phi_{u}$. Then we have $(u,v_{1})(u,v_{2})\notin E(G[H;U])$
since $(u,v_{1}),(u,v_{2})\in\phi$ and $\phi$ is an independent set of
$G[H;U]$. By the definition of $E(G[H;U])$, we obtain $v_{1}v_{2}\notin E(H)$.
Therefore, $\phi_{u}$ is an independent set of $H$, namely $\phi_{u}\in I(H)$.

  * •

For any $u_{1},u_{2}\in\overline{\phi}$, there exist $w_{1},w_{2}\in U$ such
that $(u_{1},w_{1}),(u_{2},w_{2})\in\phi$. Then
$(u_{1},w_{1})(u_{2},w_{2})\notin E(G[H;U])$ since $\phi$ is an independent
set of $G[H;U]$. By the definition of $E(G[H;U])$, we obtain $u_{1}u_{2}\notin
E(G)$. Therefore, $\overline{\phi}$ is an independent set of $G$, namely
$\overline{\phi}\in I(G)$.

So, by Proposition 3.2, $\phi$ is a simplex of
$\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus U))$.

Conversely, let $\psi$ be a simplex of
$\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus U))$. It follows from Proposition
3.2 that we have $\psi_{u}\in I(H)$ for any $u\in V(G)$ and
$\overline{\psi}\in I(G)$. Then, for any $(u_{1},v_{1}),(u_{2},v_{2})\in\psi$,
we have the followings.

  * •

If $u_{1}=u_{2}$, then $v_{1}v_{2}\notin E(H)$ since
$v_{1},v_{2}\in\psi_{u_{1}}$ and $\psi_{u_{1}}$ is an independent set of $H$.
Furthermore, $u_{1}=u_{2}$ implies that $u_{1}u_{2}\notin E(G)$ since $G$ has
no loops. Therefore, we get $(u_{1},v_{1})(u_{2},v_{2})\notin E(G[H;U])$.

  * •

If $u_{1}\neq u_{2}$ and $v_{1},v_{2}\in U$, then $u_{1}u_{2}\notin E(G)$
since $u_{1},u_{2}\in\overline{\psi}$ and $\overline{\psi}$ is an independent
set of $G$. Therefore, we get $(u_{1},v_{1})(u_{2},v_{2})\notin E(G[H;U])$.

  * •

If $u_{1}\neq u_{2}$ and $v_{1}\notin U$ or $v_{2}\notin U$, then
$(u_{1},v_{1})(u_{2},v_{2})\notin E(G[H;U])$.

So, we conclude that $(u_{1},v_{1})(u_{2},v_{2})\notin E(G[H;U])$. Thus,
$\psi$ is an independent set of $G[H;U]$, namely $\psi\in I(G[H;U])$. ∎

######  Example 5.5.

Let $G$ be a graph with at least one edge and $H$ be a graph which is not a
complete graph. Vander Meulen and Van Tuyl [9, Theorem 2.3] proved that
$I(G[H])$ is not shellable. We can deduce this result from Example 5.2,
Proposition 5.4 and Corollary 4.12 since $I(G)$ is not a simplex and $I(H)$ is
not $0$-dimensional.

Now we are ready to prove Theorem 1.2.

###### Proof of Theorem 1.2.

First, we show that (1) implies (2). By Proposition 5.4, (1) is equivalent to
the condition that $\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus\\{v_{0}\\}))$ is
pure and shellable for any graph $G$. It follows from Theorem 3.5 that $I(H)$
is pure, namely $H$ is well-covered. Now consider the cycle on $4$ vertices
$C_{4}$, namely the graph defined by

$\displaystyle V(C_{4})=\\{1,2,3,4\\},$ $\displaystyle
E(C_{4})=\\{12,23,34,41\\}.$

Since $I(C_{4})=\langle\\{1,3\\},\\{2,4\\}\rangle$ and
$I(C_{4}[H,H\setminus\\{v_{0}\\}])$ is shellable, Claim 4.2 indicates that
$\mathbf{F}_{I(H\setminus\\{v_{0}\\})}\subset\mathbf{F}_{I(H)}$. Hence, for
any maximal independent set $\tau$ of $H\setminus\\{v_{0}\\}$, we get that
$\tau\cup\\{v_{0}\\}$ is not an independent set of $H$. Namely there exists
$v\in\tau$ such that $v_{0}v\in E(H)$. Therefore, by Theorem 4.6, both $I(H)$
and $I(H\setminus\\{v_{0}\\})$ are shellable.

Next, we deduce (1) from (2). By the conditions in (2), $I(H)$ is pure, both
$I(H)$ and $I(H\setminus\\{v_{0}\\})$ are shellable, and
$\mathbf{F}_{I(H\setminus\\{v_{0}\\})}\subset\mathbf{F}_{I(H)}$. Therefore, it
follows from Theorem 3.5 that $I(G[H;H\setminus\\{v_{0}\\}])$ is pure for any
graph $G$ and from Theorem 4.13 that $I(G[H;H\setminus\\{v_{0}\\}])$ is
shellable for any graph $G$ which has at least one edge. For graph $G$ which
has no edges, it follows from Lemma 2.3 that

$\displaystyle\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus\\{v_{0}\\}))=\underbrace{I(H)*\cdots*I(H)}_{|V(G)|}$

is shellable since $I(H)$ is shellable. Therefore, we conclude that
$\mathcal{Z}^{*}_{I(G)}(I(H),I(H\setminus\\{v_{0}\\}))$ is pure and shellable,
namely $G[H;\\{v_{0}\\}]$ is well-covered and shellable, for any graph $G$. ∎

######  Example 5.6.

If $H$ is a complete graph, then $H$ satisfies the condition (2) in Theorem
1.2.

An example of $H$ which is not a complete graph is $C_{5}$, a cycle of length
$5$. Let $V(C_{5})=\\{a,b,c,d,e\\}$ and $E(C_{5})=\\{ab,bc,cd,de,ea\\}$. Then

$\displaystyle
I(C_{5})=\langle\\{a,c\\},\\{b,d\\},\\{c,e\\},\\{d,a\\},\\{e,b\\}\rangle$

is pure and shellable. Furthermore,

$\displaystyle\mathrm{dl}_{C_{5}}(a)=\langle\\{b,d\\},\\{e,b\\},\\{c,e\\}\rangle$

is shellable and each facet of $\mathrm{dl}_{C_{5}}(a)$ contains $b$ or $e$,
which are adjacent to $a$.

## References

  * [1] A. A. Ayzenberg,  Substitutions of polytopes and of simplicial complexes, and multigraded Betti numbers,  Transactions of the Moscow Mathematical Society, 74:175–202, 2013\.
  * [2] A. Bahri, M. Bendersky, F.R. Cohen, and S. Gitler,  Operations on polyhedral products and a new topological construction of infinite families of toric manifolds,  Homology, Homotopy and Applications, 17(2):137–160, 2015.
  * [3] Anders Björner and Michelle L. Wachs,  Shellable nonpure complexes and posets. I,  Transactions of the American Mathematical Society, 348(4):1299–1327, 1996.
  * [4] Anders Björner and Michelle L. Wachs,  Shellable nonpure complexes and posets. II,  Transactions of the American Mathematical Society, 349(10):3945–3975, 1997.
  * [5] Frank Harary,  Graph Theory,  Addison-Wesley Publishing Company, 1969.
  * [6] Takayuki Hibi, Akihiro Higashitani, Kyouko Kimura, and Augustine B. O’Keefe,  Algebraic study on Cameron-Walker graphs,  Journal of Algebra, 422:257–269, 2015.
  * [7] Somayeh Moradi and Fahimeh Khosh-Ahang,  Expansion of a simplicial complex,  Journal of Algebra and Its Applications, 15(1):1650004, 2016.
  * [8] Adam Van Tuyl and Rafael H. Villarreal,  Shellable graphs and sequentially Cohen-Macaulay bipartite graphs,  Journal of Combinatorial Theory, Series A, 115:799–814, 2008.
  * [9] Kevin N. Vander Meulen and Adam Van Tuyl,  Shellability, vertex decomposability, and lexicographical products of graphs,  Contributions to Discrete Mathematics, 12(2):63–68, 2017.
  * [10] Elizabeth Vidaurre,  On polyhedral product spaces over polyhedral joins,  Homology, Homotopy and Applications, 20(2):259–280, 2018.
  * [11] Russ Woodroofe,  Vertex decomposable graphs and obstructions to shellability,  Proceedings of the American Mathematical Society, 137(10):3235–3246, 2009.