Flag complexes that are shellable but not vertex decomposable

Question

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/~avantuyl/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$).

Answer 1

I'm very slow to respond, but have finally found some time to put your complex into GAP and examine it.

Questions on $k$-decomposability on flag complexes

There were two questions about $k$-decomposability and flag complexes that seemed natural, and that I didn't know the answer to.

1. Is every flag complex that is shellable also vertex-decomposable? (Your example says that the answer is "no"!)
2. Is every flag complex that is shellable also 1-decomposable? I think this is still open.

The 1st question seemed interesting just because all of the main constructions (barycentric subdivision, CL-shellings) that give a shellable flag complex seemed to give a vertex-decomposable complex.

On the 2nd question: A complex $\Delta$ is 1-decomposable if we can find either a shedding vertices $v$ or shedding edges $e$ such that respectively ($\Delta \setminus v$ and $\operatorname{link}_\Delta v$) or ($\Delta \setminus e$ and $\operatorname{link}_\Delta e$) are both shellable. The conditions for a shedding edge are similar to those for a shedding vertex — see e.g. Provan and Billera [2] or Jonsson [1] or my own [3]. In a pure $d$-dimensional complex, it suffices that deleting the edge preserves pure $d$-dimensionality. There are also definitions of $k$-decomposability for higher $k$.
Since deleting either a vertex or an edge from $\Delta$ preserves the property of being flag, a positive answer to Question 2 would say that you can always shell flag complexes in the framework of $k$-decomposability, without needing to leave the world of flag complexes. (This would be some kind of partial dual result to the fact that every shellable pure $d$-dimensional complex is $d$-decomposable.)

Your complex

I found the details of how $\Delta = \Delta(C_{16}(1,4,8))$ failed to be vertex-decomposable somewhat surprising. Any vertex (and thus every vertex) is a shedding vertex, and of course links are shellable (and presumably vertex-decomposable). But deleting a vertex leaves a non-shellable complex.
Perhaps the easiest way to see the non-shellability of the deletion is to compute the $h$-vector, which (assuming I didn't make a mistake) is $[ 1, 11, 31, 18, -1 ]$. Since a Cohen-Macaulay complex must have a positive $h$-vector (and since $\Delta \setminus v$ is pure), this gives that $\Delta \setminus v$ is not shellable.

The same doesn't immediately give a proof that $\Delta = \Delta(C_{16}(1,4,8))$ isn't 1-decomposable. Indeed, deleting the edge $\{0,3\}$ from $\Delta$ (or equivalently adding the edge $\{0,3\}$ to $C_{16}(1,4,8)$ and taking the independence complex) preserves pure 3-dimensionality, and leaves a shellable complex. You can continue this process with edges $\{3,6\}$ and $\{6,9\}$, but once you've deleted these 3 edges, $\{9,12\}$ is not a shedding edge. I suspect that you can continue this process somehow to show the complex is 1-decomposable, but I haven't checked it and don't know for sure. (I hear you have an undergraduate working on this, and it might be an interesting project for her/him to check this carefully).

[1] Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008.
[2] J. Scott Provan and Louis J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), no. 4, 576–594.
[3] Russ Woodroofe, Chordal and sequentially Cohen-Macaulay clutters, Electron. J. Combin. 18 (2011), no. 1, Paper 208, 20 pages, arXiv:0911.4697.

Answer 2

Not an answer; just a "public service," because I wanted to see Adam's example explicitly.

Here is $C_{16}(1,4,8)$ [if I computed this correctly]. So $1$ is connected to $(13,9,5,2)$ because $$16-|1{-}13|=4$$ $$16-|1{-}9|=8$$ $$|1{-}9|=8$$ $$|1{-}5|=4$$ $$|1{-}2|=1$$ Etc.:

---

 

---