Definition of vertex decomposable

Question

Let $\Delta$ be a simplicial complex.

$$\operatorname{lk}\Delta(F ) = \{H \in \Delta \mid H \cap F = \emptyset~ \& ~H \cup F \in ∆\},$$

$\operatorname{del} \Delta(F ) = \{H \in \Delta \mid H \cap F = \emptyset\}$.

See Definition 2.1

Let $\Delta$ be a simplicial complex on the vertex set $V = \{x _1 ,\ldots,x _n \}$. Then $\Delta$ is vertex decomposable if either:

1. The only facet of $\Delta$ is $\{x _1,\ldots,x_n\}$, i.e., $\Delta$ is a simplex, or $\Delta = \emptyset.$
2. There exists an $x \in V$ such that $\operatorname{del} \Delta (x)$ and $\operatorname{lk} \Delta (x)$ are vertex decomposable, and such that every facet of $\operatorname{del} \Delta (x)$ is a facet of $\Delta$.

What does $\operatorname{del} \Delta (x)$ and $\operatorname{lk} \Delta (x)$ mean by vertex decomposable ?

Give some non trivial examples.

Answer 1

The definition is by induction on $n$, the number of vertices of $\Delta$. The simplicial complexes $\operatorname{del}_\Delta(x)$ and $\operatorname{lk}_\Delta(x)$ have fewer than $n$ vertices (because they do not contain $x$), so by induction it is already defined what it means for them to be vertex-decomposable.

Let's look at a couple examples. Suppose $V=\{a,b,c,d,e\}$ and $\Delta$ is generated by $\{a,b\}$, $\{b,c,d\}$, and $\{c,d,e\}$. Since $\Delta$ is neither empty nor a simplex, for $\Delta$ to be vertex-decomposable we have to find a vertex $x$ which satisfies (2). Let's try $x=a$. We see that $\operatorname{lk}_\Delta(a)$ is just $b$, and $\operatorname{del}_\Delta(x)$ is generated by $\{b,c,d\}$ and $\{c,d,e\}$. Since $\operatorname{lk}_\Delta(a)$ is a simplex, it is vertex-decomposable by criterion (1). It is also clear that every facet of $\operatorname{del}_\Delta(a)$ is a facet of $\Delta$. So the only question is whether $\operatorname{del}_\Delta(a)$ is vertex-decomposable.

To test this, let's write $E=\operatorname{del}_\Delta(a)$. Since $E$ is not a simplex or empty, the only way for it to be vertex-decomposible is criterion (2). Let's try taking the vertex $x=b$. Then $\operatorname{lk}_E(b)$ is the edge on $c$ and $d$ and $\operatorname{del}_E(b)$ is the $2$-simplex on $c$, $d$, and $e$. Both of these are simplices, so they are vertex-decomposable by criterion (1). Also, every facet of $\operatorname{del}_E(b)$ is a facet of $E$.

Thus $E$ satisfies criterion (2) with $x=b$, and hence is vertex-decomposable. That is, $\operatorname{del}_\Delta(a)$ is vertex-decomposable, so $\Delta$ satisfies criterion (2) with $x=a$. Thus $\Delta$ is vertex-decomposable.

Now consider $V=\{a,b,c,d,e\}$ and let $\Delta$ be generated by $\{a,b,c\}$ and $\{c,d,e\}$. Since $\Delta$ is not a simplex or empty, it does not satisfy (1). Furthermore, you can check that for each $x\in V$, $\operatorname{del}_\Delta(x)$ has a facet which is not a facet of $\Delta$. Thus $\Delta$ cannot satisfy (2) for any $x$, and so it is not vertex-decomposable.