Skip to main content
3 of 3
Fixed spelling mistake

Flag complexes that are shellable but not vertex decomposable

As the title suggests, I was wondering if anyone can point me to any examples in the literature to flag complexes that are shellable but not vertex decomposable.

It is well-known that if a simplicial complex $\Delta$ is vertex decomposable, then $\Delta$ is also shellable. There are examples where the converse fails, but in all the examples I have seen, $\Delta$ is not a flag complex, i.e., its maximal non-faces all have cardinality two. (A flag complex is sometimes called an independence complex of a graph, since the faces of the complex correspond to the independent sets of the graph).

Some context: I've been looking at the independence complexes of circulant graphs, and as part of this project, my co-authors and I discovered that the independence complex of $C_{16}(1,4,8)$ is shellable but not vertex decomposable. (This is the graph with the vertex set $\{0,1,...,15\}$ where there is an edge between $i$ and $j$ if and only if $|i-j|$ or $16-|i-j|$ is in $\{1,4,8\}$.) We are not aware of any other examples of flag complexes with this property. Even if such examples do exist, we were curious how the size of our example compared with the known examples.

EDITED TO ADD: Since there has been some interest in what this graph looks like, here is another way to draw it:

Graph C_16(1,4,8) http://flash.lakeheadu.ca/%7Eavantuyl/images/c16148.jpg

An easy way to construct the circulant graph $C_n(a_1,\ldots,a_t)$ is to arrange the $n$ vertices in a circle, join the vertex $0$ to the vertices $a_1,\ldots,a_t$, join the vertex $1$ to the vertices $a_1+1,\ldots,a_t+1$, and so on (of course, the addition is modulo $n$).