Completing and extending shellings of vertex decomposable complexes
| Autor: | Coleman, Michaela, Dochtermann, Anton, Geist, Nathan, Oh, Suho |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | SIAM J. Discrete Math. 36, Iss. 2 (2022) |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 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 |
| Databáze: | arXiv |
| Externí odkaz: |
|