Shellings from relative shellings, with application to NP-completeness

A simplicial complex is shellable if it exhibits a well-behaved ordering of its maximal faces (a shelling) constructed in some precise way.Shellings have been proven useful, but they are generally not easy to construct. It is natural to ask whether shellings may be efficiently found computationally. However, it was recently proved by Goaoc, Paták, Patáková, Tancer and Wagner that deciding whether a simplicial complex is shellable is an NP-complete problem. In this talk, we use a different approach (relative shellability) to sketch a new proof for NP-completeness of shellability.