check
Combinatorics Seminar: Uli Wagner | Einstein Institute of Mathematics

Combinatorics Seminar: Uli Wagner

Date: 
Mon, 22/01/201811:00-12:30
Location: 
Room 130, Feldman Building

Title: Shellability is NP-complete
Abstract: Consider a pure 2-dimensional simplicial complex X (in other words, a 3-uniform hypergraph). A shelling of X is an inductive procedure of building X by adding the triangles of X one at a time, in such a way that each new triangle (except the first one) intersects the previously constructed complex in a connected 1-dimensional piece (consisting of one, two, or all three edges on the boundary of the triangle); X is called shellable if has a shelling. The definition naturally generalizes to higher-dimensional complexes.
Shellings and shellability are fundamental concepts in a variety of areas including polytope theory (the boundary of every convex polytope is shellable, by a theorem of Brugesser and Mani), piecewise-linear topology, topological combinatorics, and others. One reason for its importance is that shellability – a purely combinatorial property – has strong topological consequences. For instance if a d-dimensional complex X is shellable and moreover a pseudomanifold (i.e., if every (d-1)-simplex of X contained in exactly two d-simplices, which is easily checked) then X is homeomorphic to a d-dimensional sphere – a property that is algorithmically undecidable for d\geq 5.
From a computational viewpoint, it is a natural question (raised at least as early as in the 1970’s by Danaraj ad Klee) whether one can decide efficiently whether a given complex is shellable. We settle this in the negative (modulo P
eq NP) and show that shellability of d-dimensional complexes is NP-complete for every d\geq 2.
Joint work with Xavier Goaoc, Pavel Paták, Zuzana Patáková, and Martin Tancer