Shellability is NP-complete
Zuzana Patáková (Charles University, Prague)
03-Nov-2020, 18:15-18:45 (3 years ago)
Abstract: Shellability is an important notion that lead to such mathematical discoveries as the Dehn-Sommerville relations, the Upper Bound Theorem, and characterization of topology of the Bruhat order. Roughly speaking, a simplicial complex is shellable if it can be build inductively while controlling its topological properties. In this talk we show that starting from dimension two, deciding shellability is NP-complete.
Joint work with Xavier Goaoc, Pavel Paták, Martin Tancer, and Uli Wagner.
discrete mathematicscombinatoricsgeometric topology
Audience: researchers in the discipline
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
| Organizers: | Igor Pak*, Greta Panova |
| *contact for this listing |
Export talk to