13
$\begingroup$

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$).

$\endgroup$
  • 1
    $\begingroup$ The term "clique complex" is also used in the literature, see en.wikipedia.org/wiki/Clique_complex. $\endgroup$ – Christian Stump Sep 12 '14 at 4:55
  • 2
    $\begingroup$ Note that this graph is a sort of "Möbius strip over the $K_4$ with 4 stages" (see the right picture below). I suppose that if you replace numbers 4 and 4 by bigger ones (maybe not necessarily equal), the resulting graphs will have the same property. $\endgroup$ – Wolfgang Sep 12 '14 at 11:07
  • $\begingroup$ Proposition 6.8(i) of arxiv.org/pdf/1303.2070.pdf gives an example of a nonshellable triangulation of a 3-ball whose barycentric subdivision is vertex-decomposable. This suggests that there might be a nonshellable triangulation of a 3-ball whose barycentric subdivision is shellable but not vertex-decomposable. $\endgroup$ – Richard Stanley Sep 13 '14 at 0:08
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ After checking the literature, we came to the conclusion that there did not seem to be a known example of a flag complex that was shellable but not vertex decomposable. The example I posted in the original question appears to be the first such example. The example appears in this preprint (arxiv.org/abs/1505.02837). We were also able to turn this example into an infinite family in the preprint (arxiv.org/abs/1505.02838) $\endgroup$ – Adam Van Tuyl May 14 '15 at 23:24
2
$\begingroup$

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.:


 


$\endgroup$
  • $\begingroup$ May you move vertices 0 and 15 a bit? e.g. 0-7 is not an edge, nor is 2-15. $\endgroup$ – Wolfgang Sep 12 '14 at 9:47
  • 2
    $\begingroup$ Most intuitive would be to display the four $K_4$'s as squares, labeled cyclically 0-4-8-12 etc., then clockwise rotate each square by $\pi/8$ w.r.t. the previous one, and link the "almost corresponding" vertices of neighboring squares: 0-1-...-15-0. $\endgroup$ – Wolfgang Sep 12 '14 at 10:03
  • $\begingroup$ @Wolfgang: Thanks for your remarks. I was using embedding algorithms and couldn't adjust node positions. I replaced the second image. $\endgroup$ – Joseph O'Rourke Sep 12 '14 at 11:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.