Andrés David Santamaría-Galvis: Shellings from relative shellings, with application to NP-completeness

Povzetek. 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 in several areas, 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 based on relative shellability to sketch a new proof for NP-completeness of shellability.