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

Datum objave: 31. 10. 2019
Seminar za diskretno matematiko
Torek, 5. 11. 2019, od 10h do 12h, Plemljev seminar, Jadranska 19
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.