Shellability is hard even for balls
| Autor: | Paták, Pavel, Tancer, Martin |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d is at least 3. This extends our earlier work with Goaoc, Pat\'akov\'a and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamar\'ia-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in the 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in the 3-space, answering another question of Santamar\'ia-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result). Comment: 66 pages, 51 figures (The figures take nontrivial portion of the space thus in reality the paper is a bit shorter.) |
| Databáze: | arXiv |
| Externí odkaz: |
|