Séminaire Lotharingien de Combinatoire, 85B.88 (2021), 12 pp.

Michaela Coleman, Anton Dochtermann, Nathan Geist and Suho Oh

Completing and Extending Shellings of Vertex Decomposable Complexes

Abstract. We say that a pure d-dimensional simplicial complex Δ on n vertices is shelling completable if Δ can be realized as the initial sequence of some shelling of Δ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. We prove that vertex decomposable complexes are shelling completable. In fact we show that if Δ 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, shifted complexes, as well as k-vertex decomposable complexes. We also show that if Δ 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.

Received: December 1, 2020. Accepted: March 1, 2021. Final version: April 29, 2021.

The following versions are available: