# On the Homotopy Type of the Polyhedral Join over the Independence Complex of
a Forest

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

We consider a certain class of simplicial complexes which includes the
independence complexes of forests. We show that if a simplicial complex $K$
belongs to this class, then the polyhedral join
$\mathcal{Z}^{*}_{K}(\underline{X},\emptyset)$ is homotopy equivalent to a
wedge sum of CW complexes of the form
$\Sigma^{r}X_{i_{1}}*X_{i_{2}}*\cdots*X_{i_{k}}$, where $\underline{X}$ is a
family $\\{X_{i}\\}_{i\in V(K)}$ of CW complexes and $\Sigma$ denotes the
unreduced suspension. This result is applied to study the homotopy type of the
independence complex of the lexicographic product $G[H]$ of a graph $H$ over a
forest $G$. We denote by $L_{m}$ a tree on $m$ vertices with no branches. We
show that the geometric realization of the independence complex of $L_{m}[H]$
is homotopy equivalent to a wedge sum of spheres if $m\neq 2,3$ and the
geometric realization of the independence complex of $H$ is homotopy
equivalent to a wedge sum of same dimensional spheres.

###### Key words and phrases:

polyhedral join, homotopy type, independence complex, lexicographic product

###### 2020 Mathematics Subject Classification:

05E45, 05C69, 05C76

##  1\. Introduction

Let $\mathcal{C}$ be a (convenient) category of spaces or the category of
abstract simplicial complexes. Consider an associative operation
$\star:\mathcal{C}\times\mathcal{C}\to\mathcal{C}$ such that if both
$i_{A}:A\to X$ and $i_{b}:B\to Y$ are the inclusion maps, then so is
$i_{A}\star i_{B}:A\star B\to X\star Y$. For an abstract simplicial complex
$K$ on $[m]=\\{1,2,\ldots,m\\}$ and a family of pairs of spaces (complexes)
$(\underline{X},\underline{A})=\\{(X_{i}\supset A_{i})\\}_{i\in[m]}$, we can
define a union $\mathcal{Z}^{\star}_{K}(\underline{X},\underline{A})$ of
subspaces (subcomplexes) of $X_{1}\star X_{2}\star\cdots\star X_{m}$ by

$\displaystyle\mathcal{Z}^{\star}_{K}(\underline{X},\underline{A})=\bigcup_{\sigma\in
K}Y^{\sigma}_{1}\star Y^{\sigma}_{2}\star\cdots\star Y^{\sigma}_{m},\ \
Y^{\sigma}_{i}=\left\\{\begin{aligned} &X_{i}&&(i\in\sigma),\\\
&A_{i}&&(i\notin\sigma).\end{aligned}\right.$

(In the following, if $(X_{i},A_{i})=(X,A)$ $(i\in[m])$ for some pair $(X,A)$,
then we write $(\underline{X},\underline{A})=(X,A)$.) A representative example
of this construction is the polyhedral product
$\mathcal{Z}^{\times}_{K}(\underline{X},\underline{A})$, which was defined by
Bahri, Bendersky, Cohen, and Gitler [3] and has been investigated by many
researchers since then.

We assume that $\mathcal{C}$ is the category of finite CW complexes (or the
category of abstract simplicial complexes), and that $\star$ is the join
operation $*$. Then $\mathcal{Z}^{*}_{K}(\underline{X},\underline{A})$ is the
polyhedral join of the family $(\underline{X},\underline{A})$ over $K$, which
was defined by Ayzenberg [2]. In this paper, we study the homotopy type of the
polyhedral joins of finite CW complexes over the simplicial complex $K$ which
meets a certain condition. This condition is a stronger version of vertex-
decomposability, introduced by Björner and Wachs [5], and so we name it
s-vertex-decomposability. We obtain the following decomposition. Here, we set

$\displaystyle X^{*k}$ $\displaystyle=\left\\{\begin{aligned}
&\underbrace{X*X*\cdots*X}_{k}&&(k>0)\\\
&\emptyset&&(k=0),\end{aligned}\right.$ $\displaystyle\Sigma^{r}X$
$\displaystyle=X*S^{r-1},$

where $S^{d}$ denotes the $d$-dimensional sphere.

######  Theorem 1.1.

Let $K$ be a connected non-empty s-vertex-decomposable simplicial complex on
$[m]$ and $\underline{X}=\\{X_{i}\\}_{i\in[m]}$ be a family of finite CW
complexes. Then we have

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X},\emptyset)\simeq\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}}X_{1}^{*k_{1,\alpha}}*\cdots*X_{m}^{*k_{m,\alpha}}\right)$

for a family $\\{(r_{\alpha},k_{1,\alpha},\ldots,k_{m,\alpha})\\}_{\alpha\in
A}$ of tuples of $m+1$ non-negative integers.

We apply results on polyhedral joins to independence complexes of graphs. In
this paper, a graph $G$ always means a finite undirected graph with no
multiple edges and loops. Its vertex set and edge set are denoted by $V(G)$
and $E(G)$, respectively. A subset $\sigma$ of $V(G)$ is an independent set if
any two vertices of $\sigma$ are not adjacent. The independent sets of $G$ are
closed under taking subsets, so they form an abstract simplicial complex. We
call this abstract simplicial complex the independence complex of $G$ and
denote by $I(G)$. Namely

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

Independence complexes of graphs are no less important than other simplicial
complexes constructed from graphs and have been studied in many contexts.

A lot of research on the geometric realization of the independence complexes
of graphs has been going on since Kozlov [14] determined the homotopy type of
$|I(L_{n})|$ and $|I(C_{n})|$, where $L_{m}$ is a tree on $m$ vertices with no
branches, and $C_{n}$ is a cycle on $n$ vertices ($n\geq 3$). One of the tools
which are often used in previous studies is discrete Morse theory. It is a
method introduced by Forman [9] and reformulated by Chari [7]. Bousquet-Mélou,
Linusson, and Nevo [6] and Thapper [16] studied the independence complexes of
grid graphs by performing discrete Morse theory as a combinatorial algorithm
called a matching tree. However, it is hard to distinguish two CW complexes
that have the same number of cells in each dimension only by discrete Morse
theory. We need topological approaches in case discrete Morse theory is not
available. For example, it is effective to represent an independence complex
of a graph as a union of independence complexes of subgraphs, as in Engström
[8], Adamaszek [1], and Barmak [4]. Iriye [12], who investigated the
independence complexes of some grid graphs by using these methods
simultaneously, conjectured that the geometric realizations of the
independence complexes of any cylindrical square grid graphs are homotopy
equivalent to wedge sums of spheres.

As Harary [10] mentioned, there are various ways to construct a graph
structure on $V(G_{1})\times V(G_{2})$ for given two graphs $G_{1}$ and
$G_{2}$. A cylindrical square grid graph is the Cartesian product of $L_{m}$
and $C_{n}$. It seems natural to consider other products of $L_{m}$ and
$C_{n}$ and investigate the geometric realizations of their independence
complexes. In this paper, we are interested in the lexicographic product. The
lexicographic product ${G}[{H}]$ can be regarded to have
$\\#\left(V(G)\right)$ pseudo-vertices. Each of them is isomorphic to $H$ and
two pseudo-vertices are “adjacent” if the corresponding vertices of $G$ are
adjacent. Independence complexes of lexicographic products are studied by
Vander Meulen and Van Tuyl [18] from a combinatorial point of view.

${L_{4}}[{L_{3}}]$ |  | ${L_{3}}[{L_{4}}]$
---|---|---
Figure 1. Lexicographic products ${L_{4}}[{L_{3}}]$ and ${L_{3}}[{L_{4}}]$.

The following claims correlate our study on the polyhedral join over s-vertex-
decomposable simplicial complex and the study on the independence complex of
the lexicographic product over a forest.

  * •

For two graphs $G,H$, we have

$\displaystyle|I({G}[{H}])|\cong\mathcal{Z}^{*}_{I(G)}(|I(H)|,\emptyset).$
(1-1)

  * •

If a graph $G$ is a forest, then $I(G)$ is s-vertex-decomposable.

Using these claims, we can deduce the following result on the independence
complex of the lexicographic product from Theorem 1.1.

######  Theorem 1.2.

Let $G$ be a forest and $H$ be a graph. Suppose that $G$ has no vertex $u$
such that $uv\in E(G)$ for any $v\in V(G)\setminus\\{u\\}$ and that $|I(H)|$
is homotopy equivalent to a wedge sum of spheres. Then, $|I({G}[{H}])|$ is
homotopy equivalent to a wedge sum of spheres.

There is various previous research on graphs such that the geometric
realizations of their independence complexes are homotopy equivalent to wedge
sums of spheres. For example, the result of Van Tuyl and Villarreal [17,
Theorem 2.13] implies that if $G$ is a chordal graph, then $|I(G)|$ is either
contractible or homotopy equivalent to a wedge sum of spheres. (Later,
Woodroofe [19, Theorem 1] refined this result.) This fact was also proved by
Kawamura [13, Theorem 1.1].

We also present the following explicit calculation.

######  Theorem 1.3.

Let $X$ be a finite CW complex. Then we have

$\displaystyle\mathcal{Z}^{*}_{I(L_{n})}(X,\emptyset)\simeq\left\\{\begin{aligned}
&X&&(n=1),\\\ &X\sqcup X&&(n=2),\\\ &X^{*2}\sqcup X&&(n=3),\\\
&\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r}X^{*k}\right)&&(n\geq
4).\end{aligned}\right.$

Here, $\binom{p}{q}$ denotes the binomial coefficient. We define
$\binom{p}{q}=0$ if $q<0$ or $p<q$. So, the number of the wedge summand is
finite.

This calculation deduces the following result.

######  Theorem 1.4.

If $|I(H)|\simeq{\bigvee}_{n}S^{k}$, then

$\displaystyle|I({L_{m}}[{H}])|\simeq$ $\displaystyle\left\\{\begin{aligned}
&{\bigvee}_{n}S^{k}&&(m=1),\\\
&\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}S^{k}\right)&&(m=2),\\\
&\left({\bigvee}_{n^{2}}S^{2k+1}\right)\sqcup\left({\bigvee}_{n}S^{k}\right)&&(m=3),\\\
&\bigvee_{d\geq 0}\left({\bigvee}_{\sum_{p\geq
0}n^{p}\binom{p+1}{3(d-pk+1)-m}\binom{d-pk+1}{p}}S^{d}\right)&&(m\geq
4).\end{aligned}\right.$

Even though this is precisely the case in which we cannot use discrete Morse
theory, we successfully determine the homotopy type of $|I({L_{m}}[{H}])|$.
With Kozlov’s computation [14, Proposition 5.2], we can determine the homotopy
types of $|I({L_{m}}[{C_{n}}])|$ for any $m\geq 1$ and $n\geq 3$ by Theorem
1.4. This result is in contrast to the case of cylindrical square grid graphs,
in which we cannot easily determine the homotopy type for large $m,n$.

##  2\. Preliminaries

For a positive integer $m$, we set $[m]=\\{1,2,\ldots,m\\}$. We denote the
one-point space by $\mathrm{pt}$ and the $d$-dimensional sphere by $S^{d}$.

Let $(X_{1},x_{1}),\ldots,(X_{n},x_{n})$ be pointed spaces. The wedge sum
$\bigvee_{i\in[n]}X_{i}$ of these pointed spaces is defined by

$\displaystyle\bigvee_{i\in[n]}X_{i}=\left.\bigsqcup_{i\in[n]}X_{i}\middle/(x_{i}\sim
x_{j}\text{ for any $i,j\in[n]$}).\right.$

If $(X_{1},x_{1}),\ldots,(X_{n},x_{n})$ are CW pairs and $X_{i}$ is connected,
then the replacement of the base point $x_{i}$ with another $0$-cell $y_{i}$
does not change the homotopy type of the wedge sum. Hence, the wedge sum
$X_{1}\vee\cdots\vee X_{n}$ of connected non-empty CW complexes
$X_{1},\ldots,X_{n}$ is well-defined up to homotopy. We denote the wedges sum
of $n$ copies of $X$ by ${\bigvee}_{n}X$. Namely

$\displaystyle{\bigvee}_{n}X=\left\\{\begin{aligned}
&\underbrace{X\vee\cdots\vee X}_{n}&&(n\geq 1),\\\
&\mathrm{pt}&&(n=0).\end{aligned}\right.$

Though the $0$-sphere $S^{0}$ is not connected, we use the following
notations:

$\displaystyle{\bigvee}_{n}S^{0}$
$\displaystyle=\underbrace{\mathrm{pt}\sqcup\cdots\sqcup\mathrm{pt}}_{n+1},$
$\displaystyle X\vee\left({\bigvee}_{n}S^{0}\right)$
$\displaystyle=X\sqcup\underbrace{\mathrm{pt}\sqcup\cdots\sqcup\mathrm{pt}}_{n}.$

In this paper, we deal with finite CW complexes. For two CW complexes, it is
known that the join $X*Y$ has a CW structure with the cells being the product
cells of $X\times Y\times(0,1)$ or the cells of $X$ or $Y$ (see [11]). We use
the following properties of joins without proofs.

######  Proposition 2.1.

Let $X,Y$ be finite CW complexes and $X_{1},X_{2}\subset X$,
$Y_{1},Y_{2}\subset Y$ be subcomplexes.

  1. (1)

$X_{1}*Y_{1}$ is a subcomplex of $X*Y$.

  2. (2)

we have

$\displaystyle(X_{1}\cup X_{2})*Y$ $\displaystyle\cong(X_{1}*Y)\cup(X_{2}*Y),$
$\displaystyle(X_{1}\cap X_{2})*(Y_{1}\cap Y_{2})$
$\displaystyle\cong(X_{1}*Y_{1})\cap(X_{2}*Y_{2}).$

For a space $X$, the unreduced suspension of $X$, denoted by $\Sigma X$, is
defined by

$\displaystyle\Sigma X=X*S^{0}.$

Unreduced suspension often appears in this paper since the following lemma
plays an important role.

######  Lemma 2.2.

Let $X$ be a finite CW complex and $X_{1},X_{2}$ be subcomplexes of $X$ such
that $X=X_{1}\cup X_{2}$. If the inclusion maps $i_{1}:X_{1}\cap X_{2}\to
X_{1}$ and $i_{2}:X_{1}\cap X_{2}\to X_{2}$ are null-homotopic, then we have

$\displaystyle X\simeq
X_{1}\cup_{\mathrm{pt}}X_{2}\cup_{\mathrm{pt}}\Sigma(X_{1}\cap X_{2}).$

In addition, suppose that $X_{1}$ and $X_{2}$ are connected. Then we have

$\displaystyle X\simeq X_{1}\vee X_{2}\vee\Sigma(X_{1}\cap X_{2}).$

###### Proof.

We have

$\displaystyle X_{1}\cup X_{2}$ $\displaystyle\simeq(X_{1}\cup
X_{2})\times[0,1]$ $\displaystyle\simeq X_{1}\times\\{0\\}\cup(X_{1}\cap
X_{2})\times[0,1]\cup X_{2}\times\\{1\\}$

since $(X_{1},X_{1}\cap X_{2})$ and $(X_{2},X_{1}\cap X_{2})$ are CW pairs.

Let $u\in X_{1}$ and $v\in X_{2}$ be points such that $i_{1}\simeq c_{u}$ and
$i_{2}\simeq c_{v}$, where $c_{u}:X_{1}\cap X_{2}\to X_{1}$ and
$c_{v}:X_{1}\cap X_{2}\to X_{2}$ are the constant maps to $u$ and $v$,
respectively. Then, since $(X,X_{1})$ and $(X,X_{2})$ are CW pairs, we have

$\displaystyle X_{1}\times\\{0\\}\cup(X_{1}\cap X_{2})\times[0,1]\cup
X_{2}\times\\{1\\}$ $\displaystyle\simeq$ $\displaystyle
X_{1}\cup_{\\{(u,0)\\}}(X_{1}\cap
X_{2})*\\{(u,0),(v,1)\\}\cup_{\\{(v,1)\\}}X_{2}$ $\displaystyle=$
$\displaystyle X_{1}\cup_{\\{(u,0)\\}}\Sigma(X_{1}\cup
X_{2})\cup_{\\{(v,1)\\}}X_{2}.$

This is the desired conclusion. ∎

######  Proposition 2.3.

Let $X,Y,Z$ be finite non-empty CW complexes. Then we have

$\displaystyle(X\sqcup Y)*Z\simeq(X*Z)\vee(Y*Z)\vee\Sigma Z.$

In particular, we have

$\displaystyle\Sigma(X\sqcup Y)\simeq\Sigma X\vee\Sigma Y\vee S^{1}.$

###### Proof.

By Proposition 2.1, we have

$\displaystyle(X\sqcup Y)*Z\cong(X*Z)\cup_{\emptyset*Z}(Y*Z).$

We obtain the desired conclusion by Lemma 2.2 since two inclusion maps
$\emptyset*Z\to X*Z$, $\emptyset*Z\to Y*Z$ are null-homotopic. ∎

######  Proposition 2.4.

Let $X,Y,Z$ be non-empty finite CW complexes. Then we have

$\displaystyle(X\vee Y)*Z\simeq(X*Z)\vee(Y*Z).$

In particular, we have

$\displaystyle\Sigma(X\vee Y)\simeq\Sigma X\vee\Sigma Y.$

###### Proof.

By Proposition 2.1, we have

$\displaystyle(X\vee Y)*Z\cong(X*Z)\cup_{\mathrm{pt}*Z}(Y*Z).$

We obtain the desired conclusion by Lemma 2.2 since $\mathrm{pt}*Z$ is
contractible. ∎

A finite abstract simplicial complex $K$ is a collection of finite subsets of
a given finite set $V(K)$ such that if $\sigma\in K$ and $\tau\subset\sigma$,
then $\tau\in K$. In this paper, we drop the adjectives “finite” and
“abstract”. An element of $K$ is called a simplex of $K$. For a simplex
$\sigma$ of $K$, we set $\dim\sigma=\\#\left(\sigma\right)-1$, where
$\\#\left(\sigma\right)$ is the cardinality of $\sigma$. The geometric
realization of $K$ is denoted by $|K|$.

Let $V$ be a finite set and $F_{1},\ldots,F_{t}\subset V$ be a collection of
subsets of $V$. 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]\\}.$

In particular, $\langle[n+1]\rangle$ is called $n$-simplex and denoted by
$\Delta^{n}$.

$L\subset K$ is called a subcomplex of $K$ if $L$ is a simplicial complex. For
a simplicial complex $K$ and a vertex $v$ of $K$, we define subcomplexes
$\mathrm{st}_{K}(v),\mathrm{dl}_{K}(v),\mathrm{lk}_{K}(v)$ of $K$ by

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

By definition, we have

$\displaystyle
K=\mathrm{st}_{K}(v)\cup_{\mathrm{lk}_{K}(v)}\mathrm{dl}_{K}(v).$ (2-1)

Let $\\{K_{i}\\}_{i\in[m]}$ be a family of simplicial complexes. The join of
$K_{1},\ldots,K_{m}$, denoted by $K_{1}*\cdots*K_{m}$, is a simplicial complex
defined by

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

A finite undirected simple graph $G$ is a pair $(V(G),E(G))$, where $V(G)$ is
a finite set and $E(G)$ is a subset of $2^{V(G)}$ such that
$\\#\left(e\right)=2$ for any $e\in E(G)$. An element of $V(G)$ is called a
vertex of $G$, and an element of $E(G)$ is called an edge of $G$. In order to
indicate that $e=\\{u,v\\}$ ($u,v\in V(G)$), we write $e=uv$. In this paper,
we drop the adjectives “finite”, “undirected”, and “simple”, and call $G$ a
graph.

For a vertex $v\in V(G)$, an open neighborhood $N_{G}(v)$ of $v$ in $G$ is
defined by

$\displaystyle N_{G}(v)=\\{u\in V(G)\ |\ uv\in E(G)\\}.$

A closed neighborhood $\overline{N}_{G}(v)$ of $v$ in $G$ is defined by
$\overline{N}_{G}(v)=N_{G}(v)\sqcup\\{v\\}$.

A full subgraph $H$ of a graph $G$ is a graph such that

$\displaystyle V(H)$ $\displaystyle\subset V(G),$ $\displaystyle E(H)$
$\displaystyle=\\{uv\in E(G)\ |\ u,v\in V(H)\\}.$

For two full subgraphs $H,K$ of $G$, a full subgraph whose vertex set is
$V(H)\cap V(K)$ is denoted by $H\cap K$, and a full subgraph whose vertex set
is $V(H)\setminus V(K)$ is denoted by $H\setminus K$. If $V(G)=V(H)\sqcup
V(K)$ and $uv\notin E(G)$ for any $u\in V(H)$ and $v\in V(K)$, we write
$G=H\sqcup K$. For a subset $U\subset V(G)$, $G\setminus U$ is the full
subgraph of $G$ such that $V(G\setminus U)=V(G)\setminus U$.

Let $L_{n}$ be a tree on $n$ vertices with no branches, and $C_{n}$ be a cycle
on $n$ vertices ($n\geq 3$). Namely

$\displaystyle V(L_{n})=\\{1,2,\ldots,n\\},$ $\displaystyle E(L_{n})=\\{ij\ |\
|i-j|=1\\},$ $\displaystyle V(C_{n})=\\{1,2,\ldots,n\\},$ $\displaystyle
E(C_{n})=E(L_{n})\cup\\{n1\\}.$

A graph $G$ is a forest if $G$ does not contain $C_{n}$ as a full subgraph for
any $n\geq 3$.

Recall that the independence complex $I(G)$ of a graph $G$ is a simplicial
complex defined by

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

For a full subgraph $H$ of $G$, $I(H)$ is a subcomplex of $I(G)$. Furthermore,
if $H,K$ are full subgraphs of $G$, then $I(H\cap K)=I(H)\cap I(K)$.

Let $G$ be a graph and $v$ be a vertex of $G$. By definition, we have

$\displaystyle\mathrm{st}_{I(G)}(v)$ $\displaystyle=I(G\setminus N_{G}(v)),$
$\displaystyle\mathrm{dl}_{I(G)}(v)$ $\displaystyle=I(G\setminus\\{v\\}),$
$\displaystyle\mathrm{lk}_{I(G)}(v)$
$\displaystyle=I(G\setminus\overline{N}_{G}(v)).$

##  3\. S-Vertex-Decomposable Simplicial Complex

In this section, we define a class of simplicial complexes, which we call
s-vertex-decomposable simplicial complexes.

######  Definition 3.1.

Let $K$ be a simplicial complex. We say that $K$ is s-vertex-decomposable if

  * •

$K$ is either a simplex or $\\{\emptyset\\}$, or

  * •

there exist vertices $v,w$ of $K$ such that

    * –

$\mathrm{dl}_{K}(v)$, $\mathrm{lk}_{K}(v)$ are s-vertex-decomposable, and

    * –

$\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$.

We call $v$ an s-shedding vertex of $K$.

An important example of s-vertex-decomposable simplicial complex is the
independence complex of a forest.

######  Theorem 3.2.

Let $G$ be a graph. If $G$ is a forest, then $I(G)$ is s-vertex-decomposable.

###### Proof.

We prove the theorem by induction on $\\#\left(V(G)\right)$. If
$\\#\left(V(G)\right)=0$, then $I(G)=\\{\emptyset\\}$, which is s-vertex-
decomposable.

For a non-negative integer $n$, assume that $I(G^{\prime})$ is s-vertex-
decomposable for any forest $G^{\prime}$ such that
$\\#\left(V(G^{\prime})\right)<n$. Let $G$ be a forest such that
$\\#\left(V(G)\right)=n$. If $G$ has no edge, then $I(G)$ is s-vertex-
decomposable since $I(G)=\Delta^{n-1}$. If $G$ has at least one edge, then $G$
has a leaf $l$. Let $v\in V(G)$ be a unique vertex of $G$ such that $vl\in
E(G)$. Then $\mathrm{dl}_{I(G)}(v)=I(G\setminus\\{v\\})$,
$\mathrm{lk}_{I(G)}(v)=I(G\setminus\overline{N}_{G}(v))$ are s-vertex-
decomposable by the assumption of the induction. Furthermore, we have

$\displaystyle\mathrm{dl}_{I(G)}(v)=I(G\setminus\\{v\\})=I(G\setminus
N_{G}(l))=\mathrm{st}_{I(G)}(l).$

Therefore, $I(G)$ is s-vertex-decomposable. ∎

######  Remark 3.3.

The converse of Theorem 3.2 does not hold. A counterexample is $G$ in Figure
2.

$v$$w$$G$ |  | $v$$w$$I(G)$ |  | $w$$\mathrm{dl}_{I(G)}(v)$ |  | $\emptyset$$\mathrm{lk}_{I(G)}(v)$
---|---|---|---|---|---|---
Figure 2. A graph $G$ such that $I(G)$ is s-vertex-decomposable but $G$ is not
a forest

We observe that if an s-vertex-decomposable simplicial complex is not
connected, then the number of connected components must be $2$, and one of the
connected components is a $0$-simplex.

######  Proposition 3.4.

Let $K$ be a non-empty s-vertex-decomposable simplicial complex. If $K$ is not
connected, then

$\displaystyle K=\mathrm{st}_{K}(w)\sqcup\langle\\{v\\}\rangle,$

for some $v,w\in V(K)$.

###### Proof.

We first observe that $K$ is not a simplex since $K$ is not connected. So,
there exists $v,w$ such that $\mathrm{dl}_{K}(v)$, $\mathrm{lk}_{K}(v)$ are
s-vertex-decomposable, and $\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$. Here we
have

$\displaystyle
K=\mathrm{st}_{K}(v)\cup_{\mathrm{lk}_{K}(v)}\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(v)\cup_{\mathrm{lk}_{K}(v)}\mathrm{st}_{K}(w).$

Thus, if $K$ is not connected, then $\mathrm{lk}_{K}(v)$ must be empty since
both $\mathrm{st}_{K}(v)$ and $\mathrm{st}_{K}(w)$ are connected. Therefore,
we get the desired conclusion since $\mathrm{lk}_{K}(v)=\emptyset$ implies
that $\mathrm{st}_{K}(v)=\langle\\{v\\}\rangle$. ∎

Recall from [5, Definition 11.1] that a simplicial complex $K$ is called
vertex decomposable if

  * •

$K$ is either a simplex or $\\{\emptyset\\}$, or

  * •

there exists a vertex $v$ of $K$ such that

    * –

$\mathrm{dl}_{K}(v)$, $\mathrm{lk}_{K}(v)$ are vertex-decomposable, and

    * –

no maximal simplex of $\mathrm{lk}_{K}(v)$ is maximal in $\mathrm{dl}_{K}(v)$.

We show that s-vertex-decomposability is a stronger version of vertex-
decomposability.

######  Lemma 3.5.

Let $K$ be a simplicial complex and $v,w$ be vertices of $K$ such that
$\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$. Then we have

  1. (1)

$v\neq w$ ,

  2. (2)

$\mathrm{lk}_{K}(w)=\mathrm{dl}_{K}(v)\cap\mathrm{dl}_{K}(w)$,

  3. (3)

$\mathrm{lk}_{K}(v)\subset\mathrm{lk}_{K}(w)$.

###### Proof.

We get $v\neq w$ from $v\notin\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)\ni w$. We
also obtain

$\displaystyle\mathrm{lk}_{K}(w)=\mathrm{st}_{K}(w)\cap\mathrm{dl}_{K}(w)=\mathrm{dl}_{K}(v)\cap\mathrm{dl}_{K}(w).$

Thus, in order to prove (3), it remains to show that
$\mathrm{lk}_{K}(v)\subset\mathrm{dl}_{K}(w)$. We have $\\{v,w\\}\notin K$
since $v\notin\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$. Thus, if
$\sigma\in\mathrm{lk}_{K}(v)$ contains $w$, then it implies
$\\{v,w\\}\subset\sigma\cup\\{v\\}\in K$, a contradiction. So, $w\notin\sigma$
for any $\sigma\in\mathrm{lk}_{K}(v)$. ∎

######  Proposition 3.6.

Let $K$ be a simplicial complex. If $K$ is s-vertex-decomposable, then $K$ is
vertex-decomposable.

###### Proof.

Let $K$ be a s-vertex-decomposable simplicial complex. We prove the
proposition by induction on $\\#\left(V(K)\right)$. If
$\\#\left(V(K)\right)=0$, then $K=\\{\emptyset\\}$, which is vertex-
decomposable.

For a non-negative integer $n$, suppose that if $K^{\prime}$ is s-vertex-
decomposable simplicial complex such that $\\#\left(V(K^{\prime})\right)<n$,
then $K^{\prime}$ is vertex-decomposable. Consider $K$ with
$\\#\left(V(K)\right)=n$. If $K=\Delta^{n-1}$, then $K$ is vertex-
decomposable. Assume that there exist vertices $v,w$ of $K$ such that

  * •

$\mathrm{dl}_{K}(v)$, $\mathrm{lk}_{K}(v)$ are s-vertex-decomposable, and

  * •

$\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$.

$\mathrm{dl}_{K}(v)$ and $\mathrm{lk}_{K}(v)$ are vertex-decomposable by the
assumption of the induction. Furthermore, for any maximal simplex
$\sigma\in\mathrm{lk}_{K}(v)$, we have

$\displaystyle\sigma\subsetneq\sigma\cup\\{w\\}\in\mathrm{st}_{K}(w)=\mathrm{dl}_{K}(v).$

The above inclusion follows from Lemma 3.5. So, $\sigma$ is not maximal in
$\mathrm{dl}_{K}(v)$. Hence, $K$ is vertex-decomposable. ∎

##  4\. Homotopy type of Polyhedral Join over S-Vertex-Decomposable Simplicial
Complex

As defined in Section 1, the polyhedral join of finite CW complexes (or
simplicial complexes) is defined as follows.

######  Definition 4.1 (Based on [2, Definition 4.2, Observation 4.3]).

Let $K$ be a simplicial complex on $[m]$ and
$(\underline{X},\underline{A})=\\{(X_{i},A_{i})\\}_{i\in[m]}$ be a family of
finite CW pairs. For a simplex $\sigma\in K$, we define
$(\underline{X},\underline{A})^{*\sigma}$ by

$\displaystyle(\underline{X},\underline{A})^{*\sigma}=Y_{1}*Y_{2}*\cdots*Y_{m},\
Y_{i}=\left\\{\begin{aligned} &X_{i}&&(i\in\sigma),\\\
&A_{i}&&(i\notin\sigma).\end{aligned}\right.$

$(\underline{X},\underline{A})^{*\sigma}$ is a subcomplex of
$X_{1}*\cdots*X_{m}$ by Proposition 2.1.

$\mathcal{Z}^{*}_{K}(\underline{X},\underline{A})$ is a subcomplex of
$X_{1}*\cdots*X_{m}$ defined by

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X},\underline{A})=\bigcup_{\sigma\in
K}(\underline{X},\underline{A})^{*\sigma}$

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

If each $X_{i}$ is a simplicial complex and $A_{i}$ is a subcomplex of
$X_{i}$, then $\mathcal{Z}^{*}_{K}(\underline{X},\underline{A})$ is defined as
a simplicial complex by (2-2).

In the following, we consider the polyhedral join
$\mathcal{Z}^{*}_{K}(\underline{X},\emptyset)$, where $K$ is a simplicial
complex and $\underline{X}$ is a family of finite CW complexes. We denote this
polyhedral join by $\mathcal{Z}^{*}_{K}(\underline{X})$.

$\mathcal{Z}^{*}_{K}(\underline{X})$ behaves well toward operations on the
simplicial complex $K$.

######  Proposition 4.2.

Let $K$ be a simplicial complex and $\underline{X}=\\{X_{v}\\}_{v\in V(K)}$ be
a family of finite CW complexes.

  1. (1)

Let $L\subset K$ be a subcomplex of $K$. Then
$\mathcal{Z}^{*}_{L}(\underline{X})$ is a subcomplex of
$\mathcal{Z}^{*}_{K}(\underline{X})$.

  2. (2)

Let $L_{1},L_{2}\subset K$ be subcomplexes of $K$ such that $K=L_{1}\cup
L_{2}$. Then we have

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})=\mathcal{Z}^{*}_{L_{1}}(\underline{X})\cup_{\mathcal{Z}^{*}_{L_{1}\cap
L_{2}}(\underline{X})}\mathcal{Z}^{*}_{L_{2}}(\underline{X}).$

###### Proof.

(1) directly follows from the definition of polyhedral joins.

We prove (2). First, we have

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})$
$\displaystyle=\bigcup_{\sigma\in K}(\underline{X},\emptyset)^{*\sigma}$
$\displaystyle=\left(\bigcup_{\sigma\in
L_{1}}(\underline{X},\emptyset)^{*\sigma}\right)\cup\left(\bigcup_{\tau\in
L_{2}}(\underline{X},\emptyset)^{*\tau}\right)$
$\displaystyle=\mathcal{Z}^{*}_{L_{1}}(\underline{X})\cup\mathcal{Z}^{*}_{L_{2}}(\underline{X}).$

Remarking that we obtain
$\mathcal{Z}^{*}_{L_{1}}(\underline{X})\cap\mathcal{Z}^{*}_{L_{2}}(\underline{X})\supset\mathcal{Z}^{*}_{L_{1}\cap
L_{2}}(\underline{X})$ from (1), it remains to show that
$\mathcal{Z}^{*}_{L_{1}}(\underline{X})\cap\mathcal{Z}^{*}_{L_{2}}(\underline{X})\subset\mathcal{Z}^{*}_{L_{1}\cap
L_{2}}(\underline{X})$. For a point
$x\in\mathcal{Z}^{*}_{L_{1}}(\underline{X})\cap\mathcal{Z}^{*}_{L_{2}}(\underline{X})$,
there exist $\sigma\in L_{1}$ and $\tau\in L_{2}$ such that

$\displaystyle x$
$\displaystyle\in(\underline{X},\emptyset)^{*\sigma}\cap(\underline{X},\emptyset)^{*\tau}$
$\displaystyle=(A_{1}*\cdots*A_{m})\cap(B_{1}*\cdots*B_{m})$
$\displaystyle\left(\begin{aligned} &A_{i}=\left\\{\begin{aligned}
&X_{i}&&(i\in\sigma)\\\ &\emptyset&&(i\notin\sigma)\end{aligned}\right.\\\
&B_{i}=\left\\{\begin{aligned} &X_{i}&&(i\in\tau)\\\
&\emptyset&&(i\notin\tau)\end{aligned}\right.\end{aligned}\right)$
$\displaystyle=(A_{1}\cap B_{1})*\cdots*(A_{m}\cap B_{m})$
$\displaystyle\left(A_{i}\cap B_{i}=\left\\{\begin{aligned}
&X_{i}&&(i\in\sigma\cap\tau)\\\
&\emptyset&&(i\notin\sigma\cap\tau)\end{aligned}\right.\right)$
$\displaystyle=(\underline{X},\emptyset)^{*(\sigma\cap\tau)}.$

The second equality follows from Proposition 2.1. So, we get
$x\in\mathcal{Z}^{*}_{L_{1}\cap L_{2}}(\underline{X})$ since
$\sigma\cap\tau\in L_{1}\cap L_{2}$. ∎

######  Remark 4.3.

Proposition 4.2 does not hold for
$\mathcal{Z}^{*}_{K}(\underline{X},\underline{A})$ if
$\underline{A}\neq\emptyset$. For example, consider
$K=\langle\\{1\\},\\{2\\}\rangle$, $L_{1}=\langle\\{1\\}\rangle$,
$L_{2}=\langle\\{2\\}\rangle$, and $X_{1}=a\sqcup b$, $A_{1}=a$,
$X_{2}=c\sqcup d$, $A_{2}=c$, where $a,b,c,d$ are points. Then

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X},\underline{A})=(ac\cup
bc)\cup(ac\cup ad)=bc\cup ac\cup ad,$
$\displaystyle\mathcal{Z}^{*}_{L_{1}}(\underline{X},\underline{A})\cup_{\mathcal{Z}^{*}_{L_{1}\cap
L_{2}}(\underline{X},\underline{A})}\
\mathcal{Z}^{*}_{L_{2}}(\underline{X},\underline{A})=(a\sqcup b)\sqcup(c\sqcup
d),$

where $ac,bc,ad$ denote line segments (see Figure 3).

$a$$b$$c$$d$$(X_{1}*A_{2})\cup(A_{1}*X_{2})$ |  | $a$$b$$c$$d$$X_{1}\cup X_{2}$
---|---|---
Figure 3. An example of $\mathcal{Z}^{*}_{L_{1}\cup
L_{2}}(\underline{X},\underline{A})\neq\mathcal{Z}^{*}_{L_{1}}(\underline{X},\underline{A})\cup\mathcal{Z}^{*}_{L_{2}}(\underline{X},\underline{A})$

######  Proposition 4.4.

Let $K,L$ be simplicial complexes and $\underline{X}=\\{X_{v}\\}_{v\in
V(K)\sqcup V(L)}$ be a family of finite CW complexes. Then we have

$\displaystyle\mathcal{Z}^{*}_{K*L}(\underline{X})\cong\mathcal{Z}^{*}_{K}(\underline{X})*\mathcal{Z}^{*}_{L}(\underline{X}).$

###### Proof.

Remark that each simplex of $K*L$ is a disjoint union of simplexes $\sigma\in
K$ and $\tau\in L$. Thus,

$\displaystyle\mathcal{Z}^{*}_{K*L}(\underline{X})$
$\displaystyle=\bigcup_{\sigma\sqcup\tau\in
K*L}(\underline{X},\emptyset)^{*(\sigma\sqcup\tau)}$
$\displaystyle=\bigcup_{\sigma\in K,\tau\in
L}\left((\underline{X},\emptyset)^{*\sigma}*(\underline{X},\emptyset)^{*\tau}\right)$
$\displaystyle\cong\left(\bigcup_{\sigma\in
K}(\underline{X},\emptyset)^{*\sigma}\right)*\left(\bigcup_{\tau\in
L}(\underline{X},\emptyset)^{*\tau}\right)$
$\displaystyle=\mathcal{Z}^{*}_{K}(\underline{X})*\mathcal{Z}^{*}_{L}(\underline{X}).$

Note that the homeomorphism follows from Proposition 2.1. ∎

Now we consider $\mathcal{Z}^{*}_{K}(\underline{X})$ with $K$ s-vertex-
decomposable. The following theorem is essentially important throughout this
paper.

######  Theorem 4.5.

Let $K$ be a simplicial complex. Suppose that there exist vertices $v,w$ of
$K$ such that $\mathrm{lk}_{K}(v)\neq\emptyset$ and
$\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$. Let $\underline{X}=\\{X_{v}\\}_{v\in
V(K)}$ be a family of non-empty finite CW complexes. Then we have

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})\simeq$
$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\vee\left(\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v}\right)\vee\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X}).$

###### Proof.

By Proposition 4.2 and the decomposition (2-1), we have

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})=\mathcal{Z}^{*}_{\mathrm{st}_{K}(v)}(\underline{X})\cup_{\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})}\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X}).$

Let
$i:\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\to\mathcal{Z}^{*}_{\mathrm{st}_{K}(v)}(\underline{X})$
and
$j:\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\to\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
be the inclusion maps. By Proposition 4.4, we have

$\displaystyle\mathcal{Z}^{*}_{\mathrm{st}_{K}(v)}(\underline{X})$
$\displaystyle=\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)*\langle\\{v\\}\rangle}(\underline{X})$
$\displaystyle\cong\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v},$
$\displaystyle\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
$\displaystyle=\mathcal{Z}^{*}_{\mathrm{st}_{K}(w)}(\underline{X})$
$\displaystyle\cong\mathcal{Z}^{*}_{\mathrm{lk}_{K}(w)}(\underline{X})*X_{w}.$

Let $x\in X_{v}$ and $y\in X_{w}$ be points. Then, we have

$\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*\\{x\\}$
$\displaystyle\subset\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v},$
$\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*\\{y\\}$
$\displaystyle\subset\mathcal{Z}^{*}_{\mathrm{lk}_{K}(w)}(\underline{X})*\\{y\\}$
$\displaystyle\subset\mathcal{Z}^{*}_{\mathrm{lk}_{K}(w)}(\underline{X})*X_{w}.$

Note that the second inclusion is obtained from Lemma 3.5. These inclusions
indicate that $i,j$ are null-homotopic. Therefore, by Lemma 2.2, we obtain

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})=$
$\displaystyle\mathcal{Z}^{*}_{\mathrm{st}_{K}(v)}(\underline{X})\cup_{\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})}\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
$\displaystyle\simeq$
$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\vee\mathcal{Z}^{*}_{\mathrm{st}_{K}(v)}(\underline{X})\vee\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
$\displaystyle\simeq$
$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\vee\left(\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v}\right)\vee\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X}).$

So, the proof is completed. ∎

######  Remark 4.6.

The assumption “$\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$” in Theorem 4.5 cannot
be replaced with “no maximal simplex of $\mathrm{lk}_{K}(v)$ is maximal in
$\mathrm{dl}_{K}(v)$”, which appears in the definition of vertex-
decomposability. Consider a simplicial complex $K$ and a vertex $v$ in Figure
4.

$a$$b$$u$$v$$d$$c$$K$ |  | $a$$b$$u$$d$$c$$\mathrm{dl}_{K}(v)$ |  | $b$$u$$c$$\mathrm{lk}_{K}(v)$
---|---|---|---|---
Figure 4. An example of $v$ that does not satisfy the assumption in Theorem
4.5

We get

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})$
$\displaystyle\simeq(X_{u}*X_{a}*X_{b})\vee(X_{u}*X_{b}*X_{v})\vee(X_{u}*X_{v}*X_{c})$
$\displaystyle\
\vee(X_{u}*X_{c}*X_{d})\vee\Sigma(X_{u}*X_{b})\vee\Sigma(X_{u}*X_{v})\vee\Sigma(X_{u}*X_{c}),$
$\displaystyle\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
$\displaystyle\simeq(X_{u}*X_{a}*X_{b})\vee(X_{u}*X_{c}*X_{d})\vee\Sigma
X_{u},$ $\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})$
$\displaystyle\simeq(X_{u}*X_{b})\vee(X_{u}*X_{c})\vee\Sigma X_{u}$

by the same argument as in the proof of Theorem 4.5. Therefore, we conclude
that

$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\vee\left(\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v}\right)\vee\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
$\displaystyle\simeq$
$\displaystyle\Sigma((X_{u}*X_{b})\vee(X_{u}*X_{c})\vee\Sigma X_{u})$
$\displaystyle\ \vee((X_{u}*X_{b})\vee(X_{u}*X_{c})\vee\Sigma X_{u})*X_{v}$
$\displaystyle\ \vee(X_{u}*X_{a}*X_{b})\vee(X_{u}*X_{c}*X_{d})\vee\Sigma
X_{u}$ $\displaystyle\simeq$
$\displaystyle(X_{u}*X_{a}*X_{b})\vee(X_{u}*X_{b}*X_{v})\vee(X_{u}*X_{v}*X_{c})$
$\displaystyle\
\vee(X_{u}*X_{c}*X_{d})\vee\Sigma(X_{u}*X_{b})\vee\Sigma(X_{u}*X_{v})\vee\Sigma(X_{u}*X_{c})$
$\displaystyle\ \vee\Sigma X_{u}\vee\Sigma^{2}X_{u}$ $\displaystyle\simeq$
$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})\vee\Sigma
X_{u}\vee\Sigma^{2}X_{u}$ $\displaystyle\not\simeq$
$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X}).$

Theorem 1.1 and Theorem 1.3 are obtained from Theorem 4.5.

###### Proof of Theorem 1.1.

If $K$ is a simplex, then we have

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})=X_{1}*\cdots*X_{m}.$

We prove the theorem by induction on $m$. If $m=1$, then $K=\Delta^{0}$ and
$\mathcal{Z}^{*}_{K}(\underline{X})=X_{1}$. Let $n$ be a positive integer.
Assume that $\mathcal{Z}^{*}_{K^{\prime}}(\underline{X})$ can be decomposed as
in Theorem 1.1 for any s-vertex-decomposable simplicial complex $K^{\prime}$
with $\\#\left(V(K^{\prime})\right)<n$. Consider an s-vertex-decomposable
simplicial complex $K$ with $\\#\left(V(K)\right)=n$ which is not a simplex.
Let $v,w$ be vertices of $K$ such that

  * •

$\mathrm{dl}_{K}(v)$, $\mathrm{lk}_{K}(v)$ are s-vertex-decomposable, and

  * •

$\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$.

We have $\mathrm{lk}_{K}(v)\neq\emptyset$ since $K$ is connected. Thus, by
Theorem 4.5, we get

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})\simeq$
$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\vee\left(\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v}\right)\vee\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X}).$

Since $\mathrm{dl}_{K}(v)=\mathrm{st}_{K}(w)$ is connected and
$\\#\left(V(\mathrm{dl}_{K}(v))\right)<\\#\left(V(K)\right)=n$, we get from
the assumption of the induction that

$\displaystyle\mathcal{Z}^{*}_{\mathrm{dl}_{K}(v)}(\underline{X})$
$\displaystyle\simeq\bigvee_{\beta\in
B}\left(\Sigma^{s_{\beta}}X_{1}^{*l_{1,\beta}}*\cdots*X_{m}^{*l_{m,\beta}}\right)$

for a family $\\{(s_{\beta},l_{1,\beta},\ldots,l_{m,\beta})\\}_{\beta\in B}$.

If $\mathrm{lk}_{K}(v)$ is connected, then there exists
$\\{(r_{\alpha},k_{1,\alpha},\ldots,k_{m,\alpha})\\}_{\alpha\in A}$ such that

$\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})$
$\displaystyle\simeq\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}}X_{1}^{*k_{1,\alpha}}*\cdots*X_{m}^{*k_{m,\alpha}}\right).$

Therefore, we obtain

$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\simeq$
$\displaystyle\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}+1}X_{1}^{*k_{1,\alpha}}*\cdots*X_{m}^{*k_{m,\alpha}}\right),$
$\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v}\simeq$
$\displaystyle\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}}X_{1}^{*k_{1,\alpha}}*\cdots*X_{v}^{*(k_{v,\alpha}+1)}*\cdots*X_{m}^{*k_{m,\alpha}}\right).$

If $\mathrm{lk}_{K}(v)$ is not connected, then by Proposition 3.4,
$\mathrm{lk}_{K}(v)=\mathrm{st}_{K}(u)\sqcup\langle\\{u^{\prime}\\}\rangle$
for some $u,u^{\prime}\in V(K)$. Since $\mathrm{st}_{K}(u)$ is connected and
$\\#\left(V(\mathrm{st}_{K}(u))\right)<\\#\left(V(\mathrm{lk}_{K}(v))\right)$
$<n$, it follows from Proposition 4.2 that

$\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})$
$\displaystyle\simeq\left(\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}}X_{1}^{*k_{1,\alpha}}*\cdots*X_{m}^{*k_{m,\alpha}}\right)\right)\sqcup
X_{u^{\prime}}$

for a family $\\{(r_{\alpha},k_{1,\alpha},\ldots,k_{m,\alpha})\\}_{\alpha\in
A}$. Then, by Proposition 2.3, we get

$\displaystyle\Sigma\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})\simeq$
$\displaystyle\left(\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}+1}X_{1}^{*k_{1,\alpha}}*\cdots*X_{m}^{*k_{m,\alpha}}\right)\right)\vee\Sigma
X_{u^{\prime}}\vee S^{1},$
$\displaystyle\mathcal{Z}^{*}_{\mathrm{lk}_{K}(v)}(\underline{X})*X_{v}\simeq$
$\displaystyle\left(\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}}X_{1}^{*k_{1,\alpha}}*\cdots*X_{v}^{*(k_{v,\alpha}+1)}*\cdots*X_{m}^{*k_{m,\alpha}}\right)\right)$
$\displaystyle\ \vee(X_{v}*X_{u^{\prime}})\vee\Sigma X_{v}.$

Here, remark that a sphere $S^{r}$ can be written as

$\displaystyle S^{r}=\Sigma^{r-1}X_{1}^{*0}*\cdots*X_{m}^{*0}.$

In both cases, $\mathcal{Z}^{*}_{K}(\underline{X})$ is denoted by

$\displaystyle\mathcal{Z}^{*}_{K}(\underline{X})\simeq\bigvee_{\gamma\in\Gamma}\left(\Sigma^{t_{\gamma}}X_{1}^{*j_{1,\gamma}}*\cdots*X_{m}^{*j_{m,\gamma}}\right).$

for some family
$\\{(t_{\gamma},j_{1,\gamma},\ldots,j_{m,\gamma})\\}_{\gamma\in\Gamma}$ of
tuples of non-negative integers, as desired. ∎

######  Remark 4.7.

The above proof indicates that
$r_{\alpha}+k_{1,\alpha}+\cdots+k_{m,\alpha}\geq 2$ for any $\alpha\in A$ if
$m\geq 2$. So, the wedge sum in Theorem 1.1 is well-defined up to homotopy
since each wedge summand is connected.

###### Proof of Theorem 1.3.

We have

$\displaystyle I(L_{1})=\langle\\{1\\}\rangle,$ $\displaystyle
I(L_{2})=\langle\\{1\\},\\{2\\}\rangle,$ $\displaystyle
I(L_{3})=\langle\\{1,3\\},\\{2\\}\rangle.$

So, we get

$\displaystyle\mathcal{Z}^{*}_{I(L_{1})}(\underline{X})=X_{1},$
$\displaystyle\mathcal{Z}^{*}_{I(L_{2})}(\underline{X})=X_{1}\sqcup X_{2},$
$\displaystyle\mathcal{Z}^{*}_{I(L_{3})}(\underline{X})=(X_{1}*X_{3})\sqcup
X_{2}.$

By setting $X_{1}=X_{2}=X_{3}=X$, we get the desired equality for $n=1,2,3$.

Let $n\geq 1$. The proof of Theorem 3.2 indicates that $n+2$ is an s-shedding
vertex of $I(L_{n+3})$. Furthermore, we have

$\displaystyle\mathrm{lk}_{I(L_{n+3})}(n+2)$
$\displaystyle=I(L_{n+3}\setminus\overline{N}_{L_{n+3}}(n+2))=I(L_{n})\neq\emptyset,$
$\displaystyle\mathrm{dl}_{I(L_{n+3})}(n+2)$
$\displaystyle=I(L_{n+3}\setminus\\{n+2\\})$
$\displaystyle=I(L_{n+1}\sqcup\\{n+3\\})=I(L_{n+1})*\langle\\{n+3\\}\rangle.$

So, by Theorem 4.5, we obtain

$\displaystyle\mathcal{Z}^{*}_{I(L_{n+3})}(X)\simeq$
$\displaystyle\Sigma\mathcal{Z}^{*}_{I(L_{n})}(X)\vee(\mathcal{Z}^{*}_{I(L_{n})}(X)*X)\vee(\mathcal{Z}^{*}_{I(L_{n+1})}(X)*X).$
(4-1)

Define $Y_{n}$ for $n\geq 1$ by

$\displaystyle Y_{n}=\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{N_{n}(k,r)}\Sigma^{r}X^{*k}\right),$

where

$\displaystyle N_{n}(k,r)$
$\displaystyle=\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}.$

We note that $N_{n}(k,r)>0$ for non-negative integers $k,r$ if and only if
$0\leq n-2k-3r+1\leq k+1$ and $0\leq r\leq k+r$. This inequality implies that

$\displaystyle\max\left\\{\frac{n-3r}{3},0\right\\}\leq$ $\displaystyle
k\leq\frac{n-3r+1}{2},$ $\displaystyle 0\leq$ $\displaystyle
r\leq\frac{n+1}{3}.$

So, it follows that

$\displaystyle Y_{n}=\bigvee_{0\leq
r\leq\frac{n+1}{3}}\left(\bigvee_{\max\left\\{\frac{n-3r}{3},0\right\\}\leq
k\leq\frac{n-3r+1}{2}}\left({\bigvee}_{N_{n}(k,r)}\Sigma^{r}X^{*k}\right)\right).$

In order to complete the proof, it is sufficient to show that
$\mathcal{Z}^{*}_{I(L_{n})}(X)\simeq Y_{n}$ for any $n\geq 4$. First, the
explicit descriptions of $Y_{1}$, $Y_{2}$, and $Y_{3}$ are obtained as
follows.

$\displaystyle Y_{1}$ $\displaystyle=\bigvee_{0\leq
r\leq\frac{1+1}{3}}\left(\bigvee_{\max\left\\{\frac{1-3r}{3},0\right\\}\leq
k\leq\frac{2-3r}{2}}\left({\bigvee}_{N_{1}(k,r)}\Sigma^{r}X^{*k}\right)\right)$
$\displaystyle=\bigvee_{\frac{1}{3}\leq
k\leq\frac{2}{2}}\left({\bigvee}_{N_{1}(k,0)}X^{*k}\right)$
$\displaystyle={\bigvee}_{N_{1}(1,0)}X$
$\displaystyle={\bigvee}_{\binom{2}{0}\binom{1}{0}}X$ $\displaystyle=X,$
$\displaystyle Y_{2}$ $\displaystyle=\bigvee_{0\leq
r\leq\frac{2+1}{3}}\left(\bigvee_{\max\left\\{\frac{2-3r}{3},0\right\\}\leq
k\leq\frac{3-3r}{2}}\left({\bigvee}_{N_{2}(k,r)}\Sigma^{r}X^{*k}\right)\right)$
$\displaystyle=\left(\bigvee_{\frac{2}{3}\leq
k\leq\frac{3}{2}}\left({\bigvee}_{N_{2}(k,0)}X^{*k}\right)\right)\vee\left(\bigvee_{0\leq
k\leq\frac{0}{2}}\left({\bigvee}_{N_{3}(k,1)}\Sigma X^{*k}\right)\right)$
$\displaystyle=\left({\bigvee}_{N_{2}(1,0)}X\right)\vee\left({\bigvee}_{N_{2}(0,1)}S^{0}\right)$
$\displaystyle=\left({\bigvee}_{\binom{2}{1}\binom{1}{0}}X\right)\vee\left({\bigvee}_{\binom{1}{0}\binom{1}{1}}S^{0}\right)$
$\displaystyle=X\vee X\vee S^{0},$ $\displaystyle Y_{3}$
$\displaystyle=\bigvee_{0\leq
r\leq\frac{3+1}{3}}\left(\bigvee_{\max\left\\{\frac{3-3r}{3},0\right\\}\leq
k\leq\frac{4-3r}{2}}\left({\bigvee}_{N_{3}(k,r)}\Sigma^{r}X^{*k}\right)\right)$
$\displaystyle=\left(\bigvee_{\frac{3}{3}\leq
k\leq\frac{4}{2}}\left({\bigvee}_{N_{3}(k,0)}X^{*k}\right)\right)\vee\left(\bigvee_{0\leq
k\leq\frac{1}{2}}\left({\bigvee}_{N_{3}(k,1)}\Sigma X^{*k}\right)\right)$
$\displaystyle=\left({\bigvee}_{N_{3}(1,0)}X\right)\vee\left({\bigvee}_{N_{3}(2,0)}X^{*2}\right)\vee\left({\bigvee}_{N_{3}(0,1)}S^{0}\right)$
$\displaystyle=\left({\bigvee}_{\binom{2}{2}\binom{1}{0}}X\right)\vee\left({\bigvee}_{\binom{3}{0}\binom{2}{0}}X^{*2}\right)\vee\left({\bigvee}_{\binom{1}{1}\binom{1}{1}}S^{0}\right)$
$\displaystyle=X\vee X^{*2}\vee S^{0}.$

Though $Y_{2}\neq\mathcal{Z}^{*}_{I(L_{2})}(X)$ and
$Y_{3}\neq\mathcal{Z}^{*}_{I(L_{3})}(X)$, we obtain from Proposition 2.3, 2.4
that

$\displaystyle\Sigma\mathcal{Z}^{*}_{I(L_{2})}(X)$
$\displaystyle=\Sigma(X\sqcup X)\simeq\Sigma X\vee\Sigma X\vee S^{1}=\Sigma
Y_{2},$ $\displaystyle\mathcal{Z}^{*}_{I(L_{2})}(X)*X$ $\displaystyle=(X\sqcup
X)*X\simeq(X*X)\vee(X*X)\vee\Sigma X=Y_{2}*X,$
$\displaystyle\Sigma\mathcal{Z}^{*}_{I(L_{3})}(X)$
$\displaystyle=\Sigma(X^{*2}\sqcup X)\simeq\Sigma X^{*2}\vee\Sigma X\vee
S^{1}=\Sigma Y_{3},$ $\displaystyle\mathcal{Z}^{*}_{I(L_{3})}(X)*X$
$\displaystyle=(X^{*2}\sqcup X)*X\simeq(X^{*2}*X)\vee(X*X)\vee\Sigma
X=Y_{3}*X.$

Now assume that we have

$\displaystyle\Sigma\mathcal{Z}^{*}_{I(L_{n})}(X)$ $\displaystyle\simeq\Sigma
Y_{n}\simeq\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r+1}X^{*k}\right),$
$\displaystyle\mathcal{Z}^{*}_{I(L_{n})}(X)*X$ $\displaystyle\simeq
Y_{n}*X\simeq\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r}X^{*(k+1)}\right),$
$\displaystyle\mathcal{Z}^{*}_{I(L_{n+1})}(X)*X$ $\displaystyle\simeq
Y_{n+1}*X\simeq\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+2}\binom{k+r}{r}}\Sigma^{r}X^{*(k+1)}\right)$

for some $n\geq 1$. Then, by (4-1), we obtain

$\displaystyle\mathcal{Z}^{*}_{I(L_{n+3})}(X)$ $\displaystyle\simeq$
$\displaystyle\Sigma\mathcal{Z}^{*}_{I(L_{n})}(X)\vee(\mathcal{Z}^{*}_{I(L_{n})}(X)*X)\vee(\mathcal{Z}^{*}_{I(L_{n+1})}(X)*X)$
$\displaystyle\simeq$ $\displaystyle\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r+1}X^{*k}\right)\right)$
$\displaystyle\ \vee\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r}X^{*(k+1)}\right)\right)$
$\displaystyle\ \vee\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+2}\binom{k+r}{r}}\Sigma^{r}X^{*(k+1)}\right)\right)$
$\displaystyle\simeq$ $\displaystyle\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r+1}X^{*k}\right)\right)$
$\displaystyle\ \vee\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}+\binom{k+1}{n-2k-3r+2}\binom{k+r}{r}}\Sigma^{r}X^{*(k+1)}\right)\right)$
$\displaystyle=$ $\displaystyle\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+1}\binom{k+r}{r}}\Sigma^{r+1}X^{*k}\right)\right)$
$\displaystyle\ \vee\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+2}{n-2k-3r+2}\binom{k+r}{r}}\Sigma^{r}X^{*(k+1)}\right)\right)$
$\displaystyle=$ $\displaystyle\left(\bigvee_{k\in\mathbb{N}_{\geq
0},s=r+1\in\mathbb{N}}\left({\bigvee}_{\binom{k+1}{n-2k-3(s-1)+1}\binom{k+(s-1)}{s-1}}\Sigma^{s}X^{*k}\right)\right)$
$\displaystyle\ \vee\left(\bigvee_{l=k+1\in\mathbb{N},r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{(l-1)+2}{n-2(l-1)-3r+2}\binom{(l-1)+r}{r}}\Sigma^{r}X^{*l}\right)\right)$
$\displaystyle\simeq$ $\displaystyle\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{n-2k-3r+4}\binom{k+r-1}{r-1}+\binom{k+1}{n-2k-3r+4}\binom{k+r-1}{r}}\Sigma^{r}X^{*k}\right)\right)$
$\displaystyle=$ $\displaystyle\left(\bigvee_{k,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{k+1}{(n+3)-2k-3r+1}\binom{k+r}{r}}\Sigma^{r}X^{*k}\right)\right)$
$\displaystyle=$ $\displaystyle Y_{n+3}.$

Hence, by induction on $n$, we conclude that we have
$\mathcal{Z}^{*}_{I(L_{n})}(X)\simeq Y_{n}$ for any $n\geq 4$, as desired. ∎

##  5\. The Independence Complex of the Lexicographic Product over a Forest

The lexicographic product ${G}[{H}]$ of $H$ over $G$, which is called
composition by Harary [10], is defined as follows.

######  Definition 5.1.

Let $G,H$ be graphs. The lexicographic product ${G}[{H}]$ of $H$ over $G$ is a
graph defined by

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

The independence complex of ${G}[{H}]$ and the polyhedral join are related in
the following way.

######  Proposition 5.2.

Let $G,H$ be graphs. Then we have

$\displaystyle I({G}[{H}])=\mathcal{Z}^{*}_{I(G)}(I(H),\emptyset).$

###### Proof.

Follows from [15, Example 25, Proposition 27]. ∎

######  Proposition 5.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 and their subcomplexes. For a family
$\underline{X}=\\{X_{v}\\}_{v\in\bigsqcup_{i\in[m]}V(K_{i})}$ of finite CW
complexes, we have

$\displaystyle\mathcal{Z}^{*}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}(\underline{X})\cong\mathcal{Z}^{*}_{M}(\mathcal{Z}^{*}_{\underline{K}}(\underline{X}),\mathcal{Z}^{*}_{\underline{L}}(\underline{X})),$

where
$(\mathcal{Z}^{*}_{\underline{K}}(\underline{X}),\mathcal{Z}^{*}_{\underline{L}}(\underline{X}))=\\{(\mathcal{Z}^{*}_{K_{i}}(\underline{X}),\mathcal{Z}^{*}_{L_{i}}(\underline{X}))\\}_{i\in[m]}$.

###### Proof.

Using Proposition 4.4, we obtain

$\displaystyle\mathcal{Z}^{*}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}(\underline{X})$
$\displaystyle=$
$\displaystyle\bigcup_{\sigma\in\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}(\underline{X},\emptyset)^{*\sigma}$
$\displaystyle=$ $\displaystyle\bigcup_{S\in
M}\left(\bigcup_{\sigma\in(\underline{K},\underline{L})^{*S}}(\underline{X},\emptyset)^{*\sigma}\right)$
$\displaystyle=$ $\displaystyle\bigcup_{S\in
M}\mathcal{Z}^{*}_{(\underline{K},\underline{L})^{*S}}(\underline{X})$
$\displaystyle=$ $\displaystyle\bigcup_{S\in
M}\mathcal{Z}^{*}_{J_{1}*\cdots*J_{m}}(\underline{X})$
$\displaystyle\left(J_{i}=\left\\{\begin{aligned} &K_{i}&&(i\in S)\\\
&L_{i}&&(i\notin S)\end{aligned}\right.\right)$ $\displaystyle\cong$
$\displaystyle\bigcup_{S\in
M}\left(\mathcal{Z}^{*}_{J_{1}}(\underline{X})*\cdots*\mathcal{Z}^{*}_{J_{m}}(\underline{X})\right)$
$\displaystyle=$ $\displaystyle\bigcup_{S\in
M}(\mathcal{Z}^{*}_{\underline{K}}(\underline{X}),\mathcal{Z}^{*}_{\underline{L}}(\underline{X}))^{*S}$
$\displaystyle=$
$\displaystyle\mathcal{Z}^{*}_{M}(\mathcal{Z}^{*}_{\underline{K}}(\underline{X}),\mathcal{Z}^{*}_{\underline{L}}(\underline{X})).$

∎

######  Theorem 5.4.

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 and their subcomplexes. Then we have

$\displaystyle\left|\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})\right|\cong\mathcal{Z}^{*}_{M}(|\underline{K}|,|\underline{L}|),$

where $|\underline{K}|=\\{|K_{i}|\\}_{i\in[m]}$,
$|\underline{L}|=\\{|L_{i}|\\}_{i\in[m]}$.

###### Proof.

Remark that for a simplicial complex $K$, we have

$\displaystyle|K|=\mathcal{Z}^{*}_{K}(\underline{\mathrm{pt}}),$

where $\underline{\mathrm{pt}}=\\{X_{v}\\}_{v\in V(K)}$, $X_{v}=\mathrm{pt}$
for any $v\in V(K)$. So, this theorem follows from Proposition 5.3 by

$\displaystyle\left|\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})\right|=\mathcal{Z}^{*}_{\mathcal{Z}^{*}_{M}(\underline{K},\underline{L})}(\underline{\mathrm{pt}})\cong\mathcal{Z}^{*}_{M}\left(\mathcal{Z}^{*}_{\underline{K}}(\underline{\mathrm{pt}}),\mathcal{Z}^{*}_{\underline{L}}(\underline{\mathrm{pt}})\right)=\mathcal{Z}^{*}_{M}(|\underline{K}|,|\underline{L}|).$

∎

The homeomorphism (1-1) in Section 1 is obtained from Proposition 5.2 and
Theorem 5.4 by

$\displaystyle|I({G}[{H}])|=|\mathcal{Z}^{*}_{I(G)}(I(H),\emptyset)|\cong\mathcal{Z}^{*}_{I(G)}(|I(H)|).$

Using this homeomorphism, we deduce Theorem 1.2 and Theorem 1.4 from Theorem
1.1 and Theorem 1.3, respectively.

###### Proof of Theorem 1.2.

Remark that $uv\in E(G)$ for any $v\in V(G)\setminus\\{u\\}$ means that $u$ is
isolated in $I(G)$. Therefore, by Theorem 3.2 and Proposition 3.4, the
assumption on $G$ implies that $I(G)$ is connected s-vertex-decomposable
simplicial complex. Thus, by Theorem 1.1 and the homeomorphism (1-1), we have

$\displaystyle|I({G}[{H}])|$
$\displaystyle\cong\mathcal{Z}^{*}_{I(G)}(|I(H)|)$
$\displaystyle\simeq\bigvee_{\alpha\in
A}\left(\Sigma^{r_{\alpha}}|I(H)|^{*k_{\alpha}}\right)$

for some family $\\{(r_{\alpha},k_{\alpha})\\}_{\alpha\in A}$ of pairs of non-
negative integers. If $|I(H)|$ is homotopy equivalent to a wedge sum of
spheres, then so is $\Sigma^{r_{\alpha}}|I(H)|^{*k_{\alpha}}$. This is the
desired conclusion. ∎

###### Proof of Theorem 1.4.

By Theorem 1.3 and the homeomorphism (1-1), we obtain

$\displaystyle|I({L_{m}}[{H}])|$
$\displaystyle\cong\mathcal{Z}^{*}_{I(L_{m})}(|I(H)|)$
$\displaystyle\simeq\left\\{\begin{aligned} &|I(H)|&&(m=1),\\\
&|I(H)|\sqcup|I(H)|&&(m=2),\\\ &|I(H)|^{*2}\sqcup|I(H)|&&(m=3),\\\
&\bigvee_{p,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{p+1}{m-2p-3r+1}\binom{p+r}{r}}\Sigma^{r}|I(H)|^{*p}\right)&&(m\geq
4).\end{aligned}\right.$

Here, we have

$\displaystyle|I(H)|$ $\displaystyle\simeq{\bigvee}_{n}S^{k},$
$\displaystyle|I(H)|\sqcup|I(H)|$
$\displaystyle\simeq\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}S^{k}\right),$
$\displaystyle|I(H)|^{*2}\sqcup|I(H)|$
$\displaystyle\simeq\left(\left({\bigvee}_{n}S^{k}\right)*\left({\bigvee}_{n}S^{k}\right)\right)\sqcup\left({\bigvee}_{n}S^{k}\right)$
$\displaystyle\simeq\left({\bigvee}_{n^{2}}S^{2k+1}\right)\sqcup\left({\bigvee}_{n}S^{k}\right),$
$\displaystyle\Sigma^{r}|I(H)|^{*p}$
$\displaystyle\simeq\Sigma^{r}\left({\bigvee}_{n}S^{k}\right)^{*p}$
$\displaystyle\simeq{\bigvee}_{n^{p}}S^{p(k+1)-1+r}.$

So, we get the desired formula for $m=1,2,3$. For $m\geq 4$, we get

$\displaystyle|I({L_{m}}[{H}])|$ $\displaystyle\simeq$
$\displaystyle\bigvee_{p,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{p+1}{m-2p-3r+1}\binom{p+r}{r}}\Sigma^{r}|I(H)|^{*p}\right)$
$\displaystyle\simeq$ $\displaystyle\bigvee_{p,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{\binom{p+1}{m-2p-3r+1}\binom{p+r}{r}}\left({\bigvee}_{n^{p}}S^{p(k+1)-1+r}\right)\right)$
$\displaystyle\simeq$ $\displaystyle\bigvee_{p,r\in\mathbb{N}_{\geq
0}}\left({\bigvee}_{n^{p}\binom{p+1}{m-2p-3r+1}\binom{p+r}{r}}S^{p(k+1)-1+r}\right)$
$\displaystyle\simeq$ $\displaystyle\bigvee_{p\in\mathbb{N}_{\geq
0}}\left(\bigvee_{d=p(k+1)-1+r\geq
0}\left({\bigvee}_{n^{p}\binom{p+1}{m-2p-3(d-p(k+1)+1)+1}\binom{p+(d-p(k+1)+1)}{p}}S^{d}\right)\right)$
$\displaystyle\simeq$ $\displaystyle\bigvee_{d\geq
0}\left({\bigvee}_{\sum_{p\geq
0}n^{p}\binom{p+1}{3(d-pk+1)-m}\binom{d-pk+1}{p}}S^{d}\right)$

as desired. ∎

######  Example 5.5.

Kozlov [14, Proposition 5.2] proved that

$\displaystyle|I(C_{n})|$ $\displaystyle\simeq\left\\{\begin{aligned}
&S^{k-1}\vee S^{k-1}&&(n=3k),\\\ &S^{k-1}&&(n=3k+1),\\\
&S^{k}&&(n=3k+2).\end{aligned}\right.$

So, we can determine the homotopy types of $|I({L_{m}}[{C_{n}}])|$ for any
$m\geq 1$ and $n\geq 3$ by Theorem 1.4.

## References

  * [1] Michał Adamaszek,  Splittings of independence complexes and the powers of cycles,  Journal of Combinatorial Theory, Series A, 119:1031–1047, 2012\.
  * [2] A. A. Ayzenberg,  Substitutions of polytopes and of simplicial complexes, and multigraded Betti numbers,  Transactions of the Moscow Mathematical Society, 74:175–202, 2013\.
  * [3] A. Bahri, M. Bendersky, F.R. Cohen, and S. Gitler,  The polyhedral product functor: A method of decomposition for moment-angle complexes, arrangements and related spaces,  Advances in Mathematics, 225:1634–1668, 2010.
  * [4] Jonathan Ariel Barmak,  Star clusters in independence complexes of graphs,  Advances in Mathematics, 241:33–57, 2013.
  * [5] Anders Björner and Michelle L. Wachs,  Shellable nonpure complexes and posets. II,  Transactions of the American Mathematical Society, 349(10):3945–3975, 1997.
  * [6] Mireille Bousquet-Mélou, Svante Linusson, and Eran Nevo,  On the independence complex of square grids,  Journal of Algebraic Combinatorics, 27:423–450, 2008.
  * [7] Manoj K. Chari,  On discrete Morse functions and combinatorial decompositions,  Discrete Mathematics, 217:101–113, 2000.
  * [8] Alexander Engström,  Complexes of directed trees and independence complexes,  Discrete Mathematics, 309:3299–3309, 2009.
  * [9] Robin Forman,  Morse theory for cell complexes,  Advances in Mathematics, 134:90–145, 1998.
  * [10] Frank Harary,  Graph Theory,  Addison-Wesley Publishing Company, 1969.
  * [11] Allen Hatcher,  Algebraic Topology,  Cambridge University Press, 2001.
  * [12] Kouyemon Iriye,  On the homotopy types of the independence complexes of grid graphs with cylindrical identification,  Kyoto Journal of Mathematics, 52(3):479–501, 2012.
  * [13] Kazuhiro Kawamura,  Independence complexes of chordal graphs,  Discrete Mathematics, 310:2204–2211, 2010.
  * [14] Dmitry N. Kozlov,  Complexes of directed trees,  Journal of Combinatorial Theory, Series A, 88:112–122, 1999.
  * [15] Kengo Okura,  Shellability of polyhedral joins of simplicial complexes and its application to graph theory,  The Electronic Journal of Combinatorics, 29(3):#P3.53, 2022.
  * [16] Johan Thapper,  Independence complexes of cylinders constructed from square and hexagonal grid graphs,  arXiv e-prints, arXiv:0812.1165, 2008.
  * [17] 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.
  * [18] 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.
  * [19] Russ Woodroofe,  Vertex decomposable graphs and obstructions to shellability,  Proceedings of the American Mathematical Society, 137(10):3235–3246, 2009.


# Most probable escape paths in perturbed gradient systems

Katherine Slyman Division of Applied Mathematics, Brown University,
Providence, RI 02912, USA Mackenzie Simper School of Medicine, Washington
University in St. Louis, St. Louis, MO 63130, USA John A. Gemmer Department of
Mathematics, Wake Forest University, Winston-Salem, NC 27109, USA Björn
Sandstede11footnotemark: 1

##  1 Introduction

Many natural processes can be modeled by deterministic differential equations
that are subjected to small stochastic noise, in which this small noise can
cause large deviations from the deterministic flow; these include climate,
biological, ecological, and epidemiological systems [7]. The goal of
understanding these phenomena demonstrate the demand for developing methods
that quantify the impacts of noise in complex systems. A prototype model is
given by

$\mathrm{d}x=f(x)\,\mathrm{d}t+\epsilon\,\mathrm{d}W_{t},$ (1.1)

where $x\in\mathbb{R}^{n}$ describes the state of the system, the smooth
nonlinearity $f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ drives the
deterministic dynamics, and $W_{t}$ is a standard $n$-dimensional Brownian
motion that reflects stochastic noise with amplitude $0<\epsilon\ll 1$.
Without noise, trajectories of the deterministic system

$\dot{x}=f(x)$ (1.2)

will typically approach stable attractors. We are especially interested in the
scenario where stable attractors consist of a finite set of asymptotically
stable equilibria. In this situation, it is known that small noise can lead to
large deviations from the deterministic dynamics: for instance, a solution
that lies in the domain of attraction $\mathcal{A}$ of the stable equilibrium
$a$ may no longer converge or stay close to the equilibrium $a$ and instead
approach a different stable equilibrium. Starting with solutions
$X^{\epsilon}(t)$ of (1.1) with $X^{\epsilon}(0)=a$, we are then interested in
the expected exit time $\tau^{\epsilon}$ at which $X^{\epsilon}(t)$ leaves the
domain of attraction $\mathcal{A}$, the exit location
$X^{\epsilon}(\tau^{\epsilon})\in\partial\mathcal{A}$ through which the
solution leaves $\mathcal{A}$, and the optimal (that is, most probable) escape
paths that $X^{\epsilon}(t)$ will follow in $\mathcal{A}$ for $0\leq
t\leq\tau^{\epsilon}$. These questions have been investigated thoroughly in
many works, and we refer to [8, 2, 7] for results and references.

Our focus will be on optimal escape paths. These can be found as minimizers of
appropriate functionals on bounded or unbounded time intervals or,
equivalently, as solutions to the corresponding Euler–Lagrange equations. More
concrete information about the optimal paths is available if the deterministic
system (1.2) is a gradient system so that $f(x)=-\nabla V(x)$ for an
appropriate potential $V\colon\mathbb{R}^{n}\to\mathbb{R}$. In this case,
trajectories $X^{\epsilon}(t)$ of (1.1) will typically leave the deterministic
domain of attraction $\mathcal{A}$ of a stable equilibrium $a$ of (1.2)
through the saddle equilibrium $b\in\partial\mathcal{A}$ with
$b=\arg\min\\{V(z)\colon z\in\partial\mathcal{A}\\}$. Moreover,
$X^{\epsilon}(t)$ will follow the time-reversal of the heteroclinic orbit
$h(t)$ of (1.2) that connects $x=b$ at $t=-\infty$ with $x=a$ at $t=\infty$ so
that $X^{\epsilon}(t)\simeq h(-t)$ [8, 2, 7].

For non-gradient systems, it is expected that the optimal escape path will be
different from the time-reversed connecting orbit $h(-t)$. In this paper we
study the case

$\dot{x}=-\nabla V(x)+\mu g(x),$

where $\mu\in\mathbb{R}$ allows for a perturbation to a gradient system, and
prove the following statements.

  1. (i)

For symmetric perturbations $g(x)$ for which $g_{x}(x)=g_{x}(x)^{*}$ for all
$x$, optimal escape paths are still given by the time-reversals of
heteroclinic orbits connecting saddles and attractors.

  2. (ii)

For non-symmetric perturbations $g(x)$ (and, more precisely, when
$[g_{x}(h(t))-g_{x}(h(t))^{*}]\dot{h}(t)$ does not vanish identically), the
time-reversed heteroclinic saddle-attractor connection and the optimal escape
path will differ at order $\mu$.

The remainder of this paper is organized as follows. In §2, we briefly review
the relevant large-deviations results for exit problems. Section 3 contains a
discussion of the Euler–Lagrange equations for symmetric deterministic
nonlinearities, and we prove our main result on optimal escape paths for non-
gradient perturbations in §4. We illustrate our results with an example system
in §5 and finish with a discussion in §6.

##  2 Review: Large deviations for the exit problem

We review results on large deviations for a deterministic dynamical system
$\dot{x}=f(x)$ perturbed by small noise. Consider the stochastic differential
equation

$\mathrm{d}x=f(x)\,\mathrm{d}t+\epsilon\,\mathrm{d}W_{t},$ (2.1)

where $x\in\mathbb{R}^{n}$, $f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$
is smooth, $W_{t}$ is a standard $n$-dimensional Brownian motion, and
$0<\epsilon\ll 1$. We assume that $x=a$ is an asymptotically stable
equilibrium of the deterministic system

$\dot{x}=f(x)$ (2.2)

with domain of attraction $\mathcal{A}:=\\{x(0)\colon x(t)\mbox{ satisfies
\eqref{e:ode0}, }\lim_{t\rightarrow\infty}x(t)=a\\}$. We are interested in
trajectories of (2.1) that start at $x=a$ and leave $\mathcal{A}$ in finite
time for $\epsilon>0$. To describe these solutions, we define the function
space

$\Gamma_{[T_{0},T_{1}]}:=\left\\{u\in
C^{0}([T_{0},T_{1}],\mathbb{R}^{n})\colon
u(T_{0})=a,\,u(t)\in\mathcal{A}\mbox{ for }T_{0}\leq t\leq T_{1}\mbox{, and
}u\mbox{ is absolutely continuous}\right\\},$

the functional

$\mathcal{I}\colon\quad\Gamma_{T_{0},T_{1}]}\longrightarrow\mathbb{R},\quad
u\longmapsto\mathcal{I}(u):=\frac{1}{2}\int_{T_{0}}^{T_{1}}|\dot{u}(s)-f(u(s))|^{2}\,\mathrm{d}s$
(2.3)

on $\Gamma_{[T_{0},T_{1}]}$, and the associated quasi-potential

$\mathcal{V}(z):=\inf\left\\{\mathcal{I}(u)\colon
u\in\Gamma_{T_{0},T_{1}]},\,u(T_{1})=z,\,T_{0}<T_{1}\right\\}$ (2.4)

defined for $z\in\overline{\mathcal{A}}$. We set
$\mathcal{V}_{\partial\mathcal{A}}:=\inf\\{\mathcal{V}(z)\colon
z\in\partial\mathcal{A}\\}>0$ and consider solutions $X^{\epsilon}(t)$ with
$X^{\epsilon}(0)=a$ of (2.1). The following statements are then true for these
solutions under appropriate regularity assumptions on $\mathcal{A}$:

  1. Exit time:

Let $\tau^{\epsilon}_{\mathcal{A}}=\inf\\{t>0\colon
X^{\epsilon}(t)\in\partial\mathcal{A}\\}$ be the exit time from $\mathcal{A}$,
then the expectation of the exit time satisfies $\lim_{\epsilon\to
0}\epsilon\log
E(\tau^{\epsilon}_{\mathcal{A}})=\mathcal{V}_{\partial\mathcal{A}}$ (see [6,
Theorem 4.2]). In particular, the expected exit time is finite for finite
$\epsilon$ and approaches $\infty$ as $\epsilon\to 0$.

  2. Exit location:

If $b:=\arg\min_{z\in\partial\mathcal{A}}\mathcal{V}(z)$ is unique, then
$\lim_{\epsilon\to
0}P(\\{|X^{\epsilon}(\tau^{\varepsilon}_{\mathcal{A}})-b|<\delta\\})=1$ for
each $\delta>0$ (see [6, Theorem 3.1 and §5]). In particular, the most
probable exit location on the boundary of the domain of attraction is the
minimizer of the quasi-potential on the boundary.

  3. Exit path:

Assume $b:=\arg\min_{z\in\partial\mathcal{A}}\mathcal{V}(z)$ is unique, then
for each $\eta>0$ we have

$\lim_{\epsilon\to 0}P\left(\left\\{\max_{\tau^{\epsilon}_{\eta}\leq
t\leq\tau^{\epsilon}_{\mathcal{A}}}|X^{\epsilon}(t)-u_{*}(t-\tau^{\epsilon}_{\eta}+\tau_{\eta})|<\delta\right\\}\right)=1$
(2.5)

for each $\delta>0$, where $\tau^{\epsilon}_{\eta}$ and $\tau_{\eta}$ are the
largest times with $|X^{\epsilon}(\tau^{\epsilon}_{\eta})-a|=\eta$ and
$|u_{*}(\tau_{\eta})-a|=\eta$, respectively, and $u_{*}$ minimizes
$\mathcal{I}$ on $(-\infty,T]$ with $u_{*}(-\infty)=a$ and
$u_{*}(T)\in\partial\mathcal{A}$ (see [8, Theorem 2.3 in Chapter 4] and [12,
Lemma 3.3]). In particular, the most probable exit path through the boundary
is given by the minimizer of the functional $\mathcal{I}$ on $(-\infty,T]$.

We can characterize the most probable exit path $u_{*}$ as a solution to the
Euler-Lagrange equation associated with the functional $\mathcal{I}(u)$.
Assume that $u_{*}$ is a minimizer of the functional, then taking the Gateaux
derivative of the functional at $u_{*}$ and setting the derivative to zero
leads to the Euler–Lagrange equation

$\ddot{u}=f_{u}(u)\dot{u}-f_{u}(u)^{*}(\dot{u}-f(u))$ (2.6)

that $u=u_{*}$ must satisfy. Following [7], we use the Legendre transform
$w=\dot{u}-f(u)$ to obtain the equivalent first-order Hamiltonian system

$\displaystyle\dot{u}$ $\displaystyle=f(u)+w$ (2.7) $\displaystyle\dot{w}$
$\displaystyle=-f_{u}(u)^{*}w$

with corresponding Hamiltonian

$H(u,w)=\frac{|w|^{2}}{2}+\langle f(u),w\rangle.$ (2.8)

The theory of large deviations yields concrete information when the
nonlinearity $f$ is the gradient of a smooth potential
$V\colon\mathbb{R}^{n}\rightarrow\mathbb{R}$ so that $f(x)=-\nabla V(x)$. In
this case, if $u\in\Gamma_{T_{0},T_{1}]}$ satisfies
$u(T_{1})=b\in\partial\mathcal{A}$, then we have

$\displaystyle\mathcal{I}(u)$
$\displaystyle=\frac{1}{2}\int_{T_{0}}^{T_{1}}|\dot{u}(t)+\nabla
V(u(t))|^{2}\,\mathrm{d}t=\frac{1}{2}\int_{T_{0}}^{T_{1}}|\dot{u}(t)-\nabla
V(u(t))|^{2}\,\mathrm{d}t+2\int_{T_{0}}^{T_{1}}\left\langle\dot{u}(t),\nabla
V(u(t))\right\rangle\,\mathrm{d}t$
$\displaystyle=\frac{1}{2}\int_{T_{0}}^{T_{1}}|\dot{u}(t)-\nabla
V(u(t))|^{2}\,\mathrm{d}t+2(V(b)-V(a))\geq 2(V(b)-V(a)).$

The lower bound is attained if and only if $\dot{u}(t)=\nabla
V(u(t))=-f(u(t))$, that is, if $u(t)$ is a solution of the time-reversed
deterministic dynamical system $\dot{y}=-f(y)$ with $u(T_{0})=a$ and
$u(T_{1})=b$. This result can be extended to the case
$[T_{0},T_{1}]=\mathbb{R}$ to establish the following lemma.

######  Lemma 1 ([8, Theorem 3.1 in Chapter 4]).

Assume that $f(x)=-\nabla V(x)$ is a gradient and that
$b=\arg\min_{z\in\partial\mathcal{A}}V(z)$ is unique and a saddle equilibrium
of $\dot{x}=f(x)$. Then there is a unique heteroclinic orbit $h(t)\in
W^{\mathrm{u}}(b)\cap W^{\mathrm{s}}(a)$ of $\dot{x}=f(x)$ connecting $x=b$
and $x=a$, and the function $u_{*}(t):=h(-t)$ satisfies
$u_{*}=\arg\min\\{\mathcal{I}(u)\colon u\in\Gamma_{\mathbb{R}}\\}$.

In particular, the most probable exit path is given by the time-reversal of
the heteroclinic orbit of (2.2) that connect the saddle $b$ to the attractor
$a$.

##  3 Euler–Lagrange dynamics for symmetric vector fields

Consider the Euler–Lagrange equations (2.7) given by

$\displaystyle\dot{u}$ $\displaystyle=f(u)+w$ (3.1) $\displaystyle\dot{w}$
$\displaystyle=-f_{u}(u)^{*}w.$

Equilibria of (3.1) are of the form $(u,w)=(e,0)$ with $f(e)=0$ or
$(u,w)=(e,-f(e))$ with $f_{u}(e)^{*}f(e)=0$. We are interested in the
equilibria of the form $(u,w)=(e,0)$, which are the equilibria $x=e$ of the
deterministic system

$\dot{x}=f(x),\qquad x\in\mathbb{R}^{n}.$ (3.2)

If $x=e$ is a hyperbolic equilibrium of (3.2), then $(u,w)=(e,0)$ is a
hyperbolic equilibrium of (3.1) with $n$ stable and $n$ unstable eigenvalues.
Note also that the set $w=0$ is invariant under (3.1) and that (3.1)
restricted to $w=0$ becomes the deterministic system (3.2).

We introduce the new variable $v=w+2f(u)$ for which (3.1) becomes

$\displaystyle\dot{u}$ $\displaystyle=-f(u)+v$ (3.3) $\displaystyle\dot{v}$
$\displaystyle=2(f_{u}(u)^{*}-f_{u}(u))f(u)+(2f_{u}(u)-f_{u}(u)^{*})v$

with conserved quantity

$C(u,v)=\frac{1}{2}|v|^{2}-\langle f(u),v\rangle.$ (3.4)

We first focus on nonlinearities $f$ with a symmetric Jacobian.

######  Hypothesis (H1).

The nonlinearity $f(x)$ satisfies $f_{x}(x)=f_{x}(x)^{*}$ for all $x$.

Note that gradient vector fields of the form $f(x)=-\nabla V(x)$ automatically
satisfy (H1), since the Hessian of the potential $V$ is always symmetric. From
now on, we assume that (H1) is met so that (3.3) reduces to

$\displaystyle\dot{u}$ $\displaystyle=-f(u)+v$ (3.5) $\displaystyle\dot{v}$
$\displaystyle=f_{u}(u)^{*}v.$

Note that (3.5) admits solutions of the form $(u,v)(t)=(y(t),0)$ for each
solution $y(t)$ of the time-reversed differential equation

$\dot{y}=-f(y).$ (3.6)

In other words, each solution $x(t)$ of the deterministic system (3.2)
provides a solution $(u,v)(t):=(x(-t),0)$ of (3.5). Equation (3.5) has the
Hamiltonian $H(u,v)$ defined by

$H(u,v)=\frac{|v|^{2}}{2}-\langle f(u),v\rangle,\qquad\nabla
H(u,v)=\begin{pmatrix}-f_{u}(u)v\\\ v-f(u)\end{pmatrix}.$ (3.7)

We will focus on transverse heteroclinic orbits $x(t)=h(t)$ of (3.2) that
connect a saddle $x=b$ at $t=-\infty$ to an attractor $x=a$ at $t=\infty$ as
encoded in the following hypothesis.

######  Hypothesis (H2).

Assume that $x=a$ and $x=b$ are two hyperbolic equilibria of (3.2) with $\dim
W^{\mathrm{s}}(a)=n$ and $\dim W^{\mathrm{u}}(b)=1$, and that $h(t)$ is a
solution of $\dot{x}=f(x)$ with $h(0)\in
W^{\mathrm{u}}(b)\mathrel{\text{\vbox{\halign{#\cr\smash{$-$}\crcr$\pitchfork$\crcr}}}}W^{\mathrm{s}}(a)$.

Our first result shows that the associated solution
$(u_{*},v_{*})(t)=(h(-t),0)$ is then a heteroclinic orbit of (3.5) that
connects the saddle $(a,0)$ to the saddle $(b,0)$ and is transverse inside the
Hamiltonian level set $H^{-1}(0)$.

######  Lemma 2.

Assume that Hypotheses (H1) and (H2) are met, then $(u_{1},v_{1})=(a,0)$ and
$(u_{2},v_{2})=(b,0)$ are hyperbolic saddle equilibria of (3.5) with unstable
and stable dimension equal to $n$, and the solution
$(u_{*},v_{*})(t):=(h(-t),0)$ of (3.5) satisfies $(u_{*},v_{*})(0)\in
W^{\mathrm{u}}(a,0)\mathrel{\text{\vbox{\halign{#\cr\smash{$-$}\crcr$\pitchfork$\crcr}}}}W^{\mathrm{s}}(b,0)$
inside $H^{-1}(0)$.

###### Proof.

The linearization of (3.5) around
$(u_{*},v_{*})(t)=(h(-t),0)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ is given by

$\displaystyle\dot{u}$ $\displaystyle=-f_{u}(u_{*}(t))u+v$ (3.8)
$\displaystyle\dot{v}$ $\displaystyle=f_{u}(u_{*}(t))^{*}v.$

Using the block-diagonal structure of (3.8), we see that $(a,0)$ and $(b,0)$
are hyperbolic saddle equilibria of (3.5) with $\dim W^{\mathrm{u}}(a,0)=\dim
W^{\mathrm{s}}(b,0)=n$, $W^{\mathrm{u}}(a,0)\cup\dim
W^{\mathrm{s}}(b,0)\subset H^{-1}(0)$, and $(u_{*},v_{*})(0)\in
W^{\mathrm{u}}(a,0)\cap\dim W^{\mathrm{s}}(b,0)$. Note that $H^{-1}(0)$ is
manifold of dimension $2n-1$ along the solution $(u_{*}(t),0)$ since the
gradient $\nabla H(u_{*}(t),0)=(0,-f(u_{*}(t)))^{*}$ does not vanish. To
establish transversality, it therefore suffices to prove that
$(u_{*},v_{*})(t)=(\dot{u}_{*}(t),0)$ is, up to constant scalar multiples, the
only bounded solution of (3.8). We focus first on the second, decoupled
equation $\dot{v}=f_{u}(u_{*}(t))^{*}v$ in (3.8): since
$f_{u}(u_{*}(t))=f_{x}(h(-t))\rightarrow f_{x}(a)$ as $t\to-\infty$, and the
eigenvalues of $f_{x}(a)$ lie in the open left half-plane, we find that
$v(t)\equiv 0$ is the only solution of $\dot{v}=f_{u}(u_{*}(t))^{*}v$ that is
bounded uniformly in $t\in\mathbb{R}$. Hence, we necessarily have $v=0$ in
(3.8), and it suffices to identify bounded solutions of
$\dot{u}=-f_{u}(u_{*}(t))u=-f_{u}(h(-t))u$ or, equivalently, of
$\dot{x}=f_{u}(h(t))x$ after reversing time. The latter equation agrees with
the linearization of (3.2) around $h(t)$, and (H2) ensures that
$x(t)=\dot{h}(t)$ is the only solution, up to constant scalar multiples, that
is bounded uniformly in $t$. This completes the proof of the lemma. ∎

##  4 Euler–Lagrange dynamics under non-symmetric perturbations

In this section, we investigate whether the most probable escape path is
always given by the heteroclinic orbit $y(t)=h(-t)$ of (3.6) that connects the
attractor $x=a$ to the saddle equilibrium $x=b$. To do so, we start with a
nonlinearity $f(x)$ that satisfies Hypotheses (H1)-(H2) and add a small non-
symmetric perturbation to understand how the heteroclinic orbit $y(t)=h(-t)$
of (3.6) and the most probable path $u(t)$, obtained as a heteroclinic orbit
of the Euler–Lagrange equation (3.3) change and whether they differ. Thus,
consider the time-reversed system

$\dot{y}=-f(y)-\mu g(y)$ (4.1)

and the Euler–Lagrange equation

$\displaystyle\dot{u}$ $\displaystyle=-f(u)-\mu g(u)+v$ (4.2)
$\displaystyle\dot{v}$
$\displaystyle=f_{u}(u)^{*}v+\mu\Big{[}2(g_{u}(u)^{*}-g_{u}(u))(f(u)+\mu
g(u))+(2g_{u}(u)-g_{u}(u)^{*})v\Big{]}$

for $\mu$ with $|\mu|\ll 1$. Lemma 2 and the existence of a conserved quantity
of (4.2) based on (3.3) and (3.4) imply that the transverse heteroclinic
orbits $y_{0}(t)=h(-t)$ and $(u_{0},v_{0})(t)=(h(-t),0)$ of (3.6) and (3.5)
persist as unique heteroclinic solutions $y_{*}(t;\mu)$ and
$(u_{*},v_{*})(t;\mu)$ of (4.1) and (4.2), respectively, for all small $\mu$
and are smooth in $\mu$.

######  Theorem 1.

Assume that Hypotheses (H1) and (H2) are met and that there is an
$s\in\mathbb{R}$ so that

$\Big{[}g_{u}(y_{0}(s))^{*}-g_{u}(y_{0}(s))\Big{]}f(y_{0}(s))\neq 0,$ (4.3)

then there is a constant $\delta>0$ so that
$\sup_{t\in\mathbb{R}}|y_{*}(t;\mu)-u_{*}(t;\mu)|\geq\delta|\mu|$ for all
$0<|\mu|\ll 1$.

In particular, this result implies that the most probable escape path
$u_{*}(t;\mu)$ will not be given by the heteroclinic connection $y_{*}(t;\mu)$
for each $\mu$ with $0<|\mu|\ll 1$.

###### Proof.

Using smoothness in $\mu$, we expand the solutions $y_{*}(t;\mu)$ and
$(u_{*},v_{*})(t;\mu)$ as

$y_{*}(t;\mu)=h(-t)+\mu
y_{1}(t)+\mathrm{O}(|\mu|^{2}),\qquad(u_{*},v_{*})(t;\mu)=(h(-t),0)+\mu(u_{1},v_{1})(t)+\mathrm{O}(|\mu|^{2})$

and note that the $\mathrm{O}(|\mu|^{2})$ terms are bounded by $|\mu|^{2}$
uniformly in $t\in\mathbb{R}$. Using the notation $y_{0}(t)=h(-t)$, the
leading-order contributions $y_{1}(t)$ and $(u_{1},v_{1})(t)$ are bounded
solutions of the linear differential equations

$\dot{y}_{1}=-f_{u}(y_{0}(t))y_{1}-g(y_{0}(t))$ (4.4)

and

$\displaystyle\dot{u}_{1}$
$\displaystyle=-f_{u}(y_{0}(t))u_{1}+v_{1}-g(y_{0}(t))$ (4.5)
$\displaystyle\dot{v}_{1}$
$\displaystyle=f_{u}(y_{0}(t))^{*}v_{1}+2(g_{u}(y_{0}(t))^{*}-g_{u}(y_{0}(t)))f(y_{0}(t)),$

respectively. The linear equation

$\dot{y}=-f_{u}(y_{0}(t))y$ (4.6)

has exponential dichotomies $\Phi_{+}^{\mathrm{s,u}}(t,s)$ for $t,s\geq 0$ and
$\Phi_{-}^{\mathrm{u}}(t,s)$ for $t,s\leq 0$, and the unique bounded solution
of

$\dot{y}=-f_{u}(y_{0}(t))y+g(t),\qquad g\in C^{0}(\mathbb{R},\mathbb{R}^{n})$
(4.7)

is therefore given by

$y(t)=\begin{cases}\displaystyle\int_{0}^{t}\Phi_{+}^{\mathrm{s}}(t,s)g(s)\,\mathrm{d}s+\int_{\infty}^{t}\Phi_{+}^{\mathrm{u}}(t,s)g(s)\,\mathrm{d}s&t\geq
0\\\
\displaystyle\Phi_{-}^{\mathrm{u}}(t,0)\int_{\infty}^{0}\Phi_{+}^{\mathrm{u}}(0,s)g(s)\,\mathrm{d}s+\int_{0}^{t}\Phi_{-}^{\mathrm{u}}(t,s)g(s)\,\mathrm{d}s&t\leq
0.\end{cases}$ (4.8)

We conclude that

$y_{1}(t)=\begin{cases}\displaystyle-\int_{0}^{t}\Phi_{+}^{\mathrm{s}}(t,s)g(y_{0}(s))\,\mathrm{d}s-\int_{\infty}^{t}\Phi_{+}^{\mathrm{u}}(t,s)g(y_{0}(s))\,\mathrm{d}s&t\geq
0\\\
\displaystyle-\Phi_{-}^{\mathrm{u}}(t,0)\int_{\infty}^{0}\Phi_{+}^{\mathrm{u}}(0,s)g(y_{0}(s))\,\mathrm{d}s-\int_{0}^{t}\Phi_{-}^{\mathrm{u}}(t,s)g(y_{0}(s))\,\mathrm{d}s&t\leq
0\end{cases}$ (4.9)

is the unique bounded solution of (4.4). We consider (4.5) next and define

$g_{1}(s):=2\Big{[}g_{u}(y_{0}(t))^{*}-g_{u}(y_{0}(t))\Big{]}f(y_{0}(t))$

so that we can write the equation for $v_{1}$ as

$\mathcal{L}v_{1}=\left[\frac{\mathrm{d}}{\mathrm{d}t}-f_{u}(y_{0}(\cdot))^{*}\right]v_{1}=g_{1}.$
(4.10)

It follows from [11, Lemma 4.2] that $\mathcal{L}\colon
C^{1}(\mathbb{R},\mathbb{R}^{n})\rightarrow C^{0}(\mathbb{R},\mathbb{R}^{n})$
is a bounded Fredholm operator with index $-1$, null space
$\mathrm{N}(\mathcal{L})=\\{0\\}$, and range
$\mathrm{Rg}(\mathcal{L})^{\perp}=\mathbb{R}f(y_{0})$, and that
$\mathcal{L}v_{1}=g_{1}$ has a solution if and only if $\langle
f(y_{0}),g_{1}\rangle_{L^{2}}=0$. We use the latter condition to check
solvability of (4.10): for each $t\in\mathbb{R}$, we have

$\displaystyle\frac{1}{2}\langle f(y_{0}(t)),g_{1}(t)\rangle$
$\displaystyle=\langle
f(y_{0}(t)),(g_{x}(y_{0}(t))^{*}-g_{x}(y_{0}(t))f(y_{0}(t))\rangle$
$\displaystyle=\langle g_{x}(y_{0}(t))f(y_{0}(t)),f(y_{0}(t))\rangle-\langle
f(y_{0}(t)),g_{x}(y_{0}(t))f(y_{0}(t))\rangle$ $\displaystyle=0.$

Hence, $\langle f(y_{0}),g_{1}\rangle_{L^{2}}=0$, and we conclude that there
exists a unique $v_{1}\in C^{1}(\mathbb{R},\mathbb{R}^{n})$ with
$\mathcal{L}v_{1}=g_{1}$, and $g_{1}\not\equiv 0$ implies $v_{1}\not\equiv 0$.
It remains to solve the remaining equation

$\dot{u}_{1}=-f_{x}(y_{0}(t))u_{1}+v_{1}(t)-g(y_{0}(t))$ (4.11)

where $v_{1}=\mathcal{L}^{-1}g_{1}$ as above. This equation is of the form
(4.7) and its unique bounded solution $u_{1}(t)$ is therefore of the form
(4.8). Comparing (4.4) and (4.11), we see that

$\displaystyle u_{1}(t)$
$\displaystyle=y_{1}(t)+\begin{cases}\displaystyle\int_{0}^{t}\Phi_{+}^{\mathrm{s}}(t,s)v_{1}(s)\,\mathrm{d}s+\int_{\infty}^{t}\Phi_{+}^{\mathrm{u}}(t,s)v_{1}(s)\,\mathrm{d}s&t\geq
0\\\
\displaystyle\Phi_{-}^{\mathrm{u}}(t,0)\int_{\infty}^{0}\Phi_{+}^{\mathrm{u}}(0,s)v_{1}(s)\,\mathrm{d}s+\int_{0}^{t}\Phi_{-}^{\mathrm{u}}(t,s)v_{1}(s)\,\mathrm{d}s&t\leq
0\end{cases}$ (4.12) $\displaystyle=:y_{1}(t)+\Delta_{1}(t).$

We conclude that $u_{1}(t)-y_{1}(t)=\Delta_{1}(t)$, and (4.12) shows that
$\Delta_{1}\equiv 0$ if and only if $v_{1}\equiv 0$. We argued above that the
latter holds if and only if $g_{1}\equiv 0$. Thus, whenever there is a
$t\in\mathbb{R}$ for which

$(g_{u}(y_{0}(t))^{*}-g_{u}(y_{0}(t)))f(y_{0}(t))\neq 0,$

we conclude that $u_{*}(t)$ will differ from the heteroclinic connection
$y_{*}(t)$ for each $\mu$ with $0<|\mu|\ll 1$. This completes the proof of the
lemma. ∎

We note that [5] similarly used Melnikov calculations to investigate noisy
transitions in a one-dimensional system perturbed by weak periodic forcing.
While we do not focus on periodic states, our calculations are more general
and apply to systems in arbitrary dimensions.

##  5 Numerical illustration

To illustrate how numerically computed optimal paths compare with our
theoretical results, and to demonstrate Theorem 1, we consider the planar
system

$\dot{x}=f(x)+\mu g(x)=-\nabla V(x)+\mu g(x),\qquad
x=(x_{1},x_{2})\in\mathbb{R}^{2},$ (5.1)

where $V$ and the non-gradient perturbation $g$ are given by

$\nabla V(x)=\begin{pmatrix}x_{1}(x_{1}^{2}-1)\\\ x_{2}\end{pmatrix},\qquad
g(x)=\begin{pmatrix}-x_{2}\\\ 0\end{pmatrix}.$ (5.2)

The system (5.1) has two stable equilibria at $a:=(-1,0)$ and $(1,0)$ that are
separated by the saddle $b:=(0,0)$. We consider the most probable escape path
from the attractor $a$. The heteroclinic orbit $h(t)$ of (5.1) that connects
$x=b$ at $t=-\infty$ to $x=a$ at $t=\infty$ does not depend on $\mu$ and is
given by

$h(t)=\begin{pmatrix}\frac{-1}{\sqrt{\mathrm{e}^{-2t}+1}}\\\ 0\end{pmatrix}.$

Lemma 2 implies that the corresponding solution
$(u_{0},v_{0})(t)\in\mathbb{R}^{4}$ of the associated Euler–Lagrange equation
at $\mu=0$ is therefore given by

$\begin{pmatrix}u_{0}(t)\\\ v_{0}(t)\end{pmatrix}=\begin{pmatrix}h(-t)\\\
0\end{pmatrix}.$

To apply Theorem 1, we need to check condition (4.3) for our example. Since
the quantity

$\left[g_{x}(h(-t))^{*}-g_{x}(h(-t))\right]f(h(-t))=\begin{pmatrix}0\\\
2\dot{h}_{1}(-t)\end{pmatrix}$

never vanishes, it follows from Theorem 1 that the most probable exit path
$u_{\mathrm{exit}}(t;\mu)$ will differ from the time-reversed heteroclinic
orbit $h(-t)$ for $0<|\mu|\ll 1$. We can explicitly solve the equation (4.11)
for $u_{1}(t)\in\mathbb{R}^{2}$ to get

$u_{1}(t)=\begin{pmatrix}0\\\
-\mathrm{e}^{t}+\sqrt{\mathrm{e}^{2t}+1}-\mathrm{e}^{-t}\sinh^{-1}(\mathrm{e}^{t})\end{pmatrix},$

and the most probable exit path $u_{\mathrm{exit}}(t;\mu)$ is therefore given
by

$u_{\mathrm{exit}}(t;\mu)=u_{0}(t)+\mu
u_{1}(t)+\mathrm{O}(|\mu|^{2})=\begin{pmatrix}\frac{-1}{\sqrt{\mathrm{e}^{2t}+1}}\\\
0\end{pmatrix}+\mu\begin{pmatrix}0\\\
\sqrt{\mathrm{e}^{2t}+1}-\mathrm{e}^{t}-\mathrm{e}^{-t}\sinh^{-1}(\mathrm{e}^{t})\end{pmatrix}+\mathrm{O}(|\mu|^{2}).$
(5.3)

In Figure 1, we compare the first-order approximation
$u_{\mathrm{approx}}(t;\mu):=u_{0}(t)+\mu u_{1}(t)$ of
$u_{\mathrm{exit}}(t;\mu)$ with its numerical approximation
$u_{\mathrm{num}}(t;\mu)$, which we compute by finding the heteroclinic
connection of the associated Euler–Lagrange system (4.2) using auto07p. This
figure demonstrates that the most probable exit path
$u_{\mathrm{exit}}(t;\mu)$ differs from the $\mu$-independent time-reversed
heteroclinic orbit $h(t)$ of (5.1) for $0<|\mu|\ll 1$.

(a)

(b)

Figure 1: Panel (a): Shown are the numerical approximation
$u_{\mathrm{approx}}(t;\mu)$ from the attractor $(-1,0)$ to the saddle $(0,0)$
of the most probable exit paths $u_{\mathrm{exit}}(t;\mu)$ for $\mu=0$ (blue),
$\mu=0.0005$ (orange), and $\mu=0.001$ (green) together with the analytical
approximations $u_{\mathrm{approx}}(t;\mu)$ in black (note that the
$\mu$-independent time-reversed heteroclinic orbit lies on the line
$x_{2}=0$). Panel (b): Shown is the log-log plot of the $L^{2}$-difference
$R:=\|u_{\mathrm{approx}}(\cdot;\mu)-u_{\mathrm{num}}(\cdot;\mu)\|_{L^{2}}$ of
the first-order analytical approximation $u_{\mathrm{approx}}$ and the
numerical approximation $u_{\mathrm{num}}$ of the exit path
$u_{\mathrm{exit}}$ against $\mu$. As expected, the linear fit has slope $2$.

##  6 Discussion

The dynamics of stochastic models can differ significantly from the dynamics
of an underlying deterministic system. Noise can affect the dynamics on a
variety of scales and can induce rare transitions away from deterministic
attractors [7]; these are often referred to as noise-induced tipping points
[1]. There are three objects relevant to noise-induced rare transitions: the
probability distribution of escape points on a basin boundary, the most
probable escape path from an attractor, and the expected time of this escape.
For gradient systems, it is well known that the most probable escape path is
given by the time-reversed heteroclinic connection between a saddle and the
attractor of the deterministic system in the limit of vanishing noise
amplitude. In this case, it is also known that an approximation of the
expected time $\tau$ to tip from an attractor $a$ to a different attractor
that is separated by a saddle $b$ is given by

$\mathbb{E}[\tau]\approx C\mathrm{e}^{\frac{2(V(b)-V(a))}{\varepsilon^{2}}},$

where $V$ is the potential of the gradient system and $\varepsilon$ the noise
amplitude. For gradient systems, the prefactor $C$ can be explicitly computed
to O($\sqrt{\epsilon}$) and, in the one-dimensional case, it can be found
using Laplace’s method. While not the focus of this work, we believe it is
possible to follow the techniques of [9, 3] to compute an asymptotic expansion
of $C$ for the expected escape time for $\mathrm{O}(\mu)$ perturbations of a
gradient system.

The focus of our work was to characterize the most probable escape paths for
non-gradient perturbations of gradient systems and to understand whether, and
by how much, these escape paths would differ from the time-reversed
heteroclinic attractor-saddle connection. We accomplished this as follows.
First, we identified the most probable escape path with an appropriate
heteroclinic saddle-saddle connection of the Euler–Lagrange equation
associated with the large-deviations functional (2.3). Next, we used Melnikov
theory to compute the displacements of the time-reversed attractor-saddle
connection of the deterministic model and of the heteroclinic saddle-saddle
connection of the Euler–Lagrange equation.

Our result shows that if the Jacobian of the perturbation of the deterministic
model is not symmetric along the unperturbed heteroclinic attractor-saddle
connection, then the most probable escape path will differ from the
deterministic attractor-saddle connection. We also showed more generally that
for any system with symmetric Jacobian, whether with gradient structure or
not, the most probable escape paths will coincide with the deterministic
attractor-saddle connections.

One advantage of the characterization we used here is that it avoids the
computation of quasi-potentials or the use of Monte–Carlo simulations. In
particular, calculating the quasipotential in higher dimensions is a
numerically challenging task since it involves solving the static
Hamilton–Jacobi equations [10, 4].

##  7 Acknowledgements

This material is based upon work supported by the National Science Foundation.
K. Slyman was supported by the NSF under grant RTG: DMS-2038039. B. Sandstede
was partially supported by the NSF through grants RTG: DMS-2038039 and
DMS-2106566.

## References

  * [1] P. Ashwin, S. Wieczorek, R. Vitolo, and P. Cox, Tipping points in open systems: bifurcation, noise-induced and rate-dependent examples in the climate system, Philosophical Transactions of the Royal Society A, 370 (2012), pp. 1166–1184.
  * [2] N. Berglund, Kramers’ law: validity, derivations and generalisations, Markov Processes and Related Fields, 19 (2011).
  * [3] F. Bouchet and J. Reygner, Path integral derivation and numerical computation of large deviation prefactors for non-equilibrium dynamics through matrix riccati equations, Journal of Statistical Physics, 189 (2022), p. 21.
  * [4] M. Cameron, Finding the quasipotential for nongradient sdes, Physica D: Nonlinear Phenomena, 241 (2012), pp. 1532–1550.
  * [5] Y. Chao, J. Duan, and P. Wei, Small-noise-induced metastable transition of periodically perturbed systems, SIAM Journal on Applied Dynamical Systems, 23 (2024), pp. 961–981.
  * [6] M. V. Day, Large deviations results for the exit problem with characteristic boundary, Journal of Mathematical Analysis and Applications, 147 (1990), pp. 134–153.
  * [7] E. Forgoston and R. O. Moore, A primer on noise-induced transitions in applied dynamical systems, SIAM Review, 60 (2018), pp. 969–1009.
  * [8] M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, vol. 260 of Grundlehren der mathematischen Wissenschaften, Springer, Berlin, Heidelberg, 2012.
  * [9] T. Grafke, T. Schäfer, and E. Vanden-Eijnden, Sharp asymptotic estimates for expectations, probabilities, and mean first passage times in stochastic systems with small noise, Communications on Pure and Applied Mathematics, 77 (2024), pp. 2268–2330.
  * [10] B. C. Nolting and K. C. Abbott, Balls, cups, and quasi-potentials: quantifying stability in stochastic systems, Ecology, 97 (2016), pp. 850–864.
  * [11] K. J. PALMER, Exponential dichotomies and transversal homoclinic points, Journal of Differential Equations, 55 (1984), pp. 225 – 256.
  * [12] A. D. Ventsel and M. I. Freidlin, On small random perturbations of dynamical systems, Russian Mathematical Surveys, 25 (1970), pp. 1–55.