Completing and extending shellings of vertex decomposable complexes

Abstract

We say that a pure $d$-dimensional simplicial complex $\Delta$ on $n$ vertices is \emph{shelling completable} if $\Delta$ can be realized as the initial sequence of some shelling of ${\Delta }_{n-1}^{(d)}$, the $d$-skeleton of the $(n-1)$-dimensional simplex. A well-known conjecture of Simon posits that any shellable complex is shelling completable. In this note we prove that vertex decomposable complexes are shelling completable. In fact we show that if $\Delta$ is a vertex decomposable complex then there exists an ordering of its ground set $V$ such that adding the revlex smallest missing $(d+1)$-subset of $V$ results in a complex that is again vertex decomposable. We explore applications to matroids and shifted complexes, as well as connections to ridge-chordal complexes and $k$-decomposability. We also show that if $\Delta$ is a $d$-dimensional complex on at most $d+3$ vertices then the notions of shellable, vertex decomposable, shelling completable, and extendably shellable are all equivalent.

13 pages; v2: Fixed some typos and other minor revisions, expanded Remark 3.8; v3: added Section 2.1 connecting our work to ridge chordal complexes, other corrections and minor revisions incorporating comments from referees