Testing Simplicial Complexes for Shellability – Combinatorial Topology

co.combinatoricscombinatorial-topologysimplicial-stuff

Question

Are there efficient algorithms to check if a finite simplicial complex defined in terms of its maximal facets is shellable?

By efficient here I am willing to consider anything with smaller expected complexity than the exponential mess one gets by naively testing all possible orderings of maximal facets.

Background

Let $\Delta$ be a simplicial complex and for each simplex $\sigma \in \Delta$ let $\bar{\sigma}$ denote the subcomplex generated by $\sigma$ and all its faces. Fix an ordering of its maximal facets $F_1,\ldots,F_K$, pick some $k \in \lbrace 1,\ldots,K\rbrace$ and define $\Delta_k$ to be the subcomplex generated by $\bigcup_{1\leq j \leq k} F_j$, i.e., all facets up to and incluing the $k$-th one.

Definition: We call this ordering of maximal facets a shelling if the intersection $\overline{F_{k+1}} \cap \Delta_k$ is a simplicial complex of dimension $\dim (F_{k+1}) – 1$ for each $k \in \lbrace 1,\ldots,K-1\rbrace$.

In general, the complex $\Delta$ need not be a combinatorial manifold or have a uniform top dimension for its maximal facets. It is known that if $\Delta$ is shellable then there exists a shelling by maximal facets ordered so that the dimension is decreasing along the order. So one method to simplify the computational burden is to test only those orderings $F_1,\ldots,F_K$ of maximal facets so that $\dim F_i \geq \dim F_j$ whenever $i \leq j$, but of course in the worst case all these facets could have the same dimension.

Motivation

Shellability is an extremely useful notion in topological combinatorics: many interesting simplicial complexes and posets in this field turn out to be shellable. I refer you to the works of Anders Bjorner and others for details, see here or here or… Since every shellable complex is a wedge of spheres, establishing shellability leads to all sorts of interesting conclusions. Among other things, shellable complexes must lack torsion in homology of all dimensions.

Best Answer

As you point out (relayed from Frank Lutz), it seems likely that checking shellability is NP-hard.

But all is not lost:

  1. A complex that is shellable usually has lots of shellings, and it's often quick to find them by recursively trying to extend a partial shelling. The above-mentioned answer mentions some ways that this can be made more efficient.

  2. A (pure) complex that is not shellable often has a negative component in its $h$-vector, a certain re-encoding of the $f$-vector. See
    http://en.wikipedia.org/wiki/H-vector
    For non-pure complexes, you can check the so-called $h$-triangle -- see Björner and Wachs, "Shellable nonpure complexes and posets I".
    Since shellable complexes (more generally sequentially Cohen-Macaulay complexes) have positive $h$-triangles, this gives a quick way of eliminating some complexes that are not shellable.

You could get a little more involved with (2), and check for positive $h$-triangles of every link in the complex, since a link in a shellable complex is shellable.

In practice, when I've had complexes that I've wanted to computationally check shellability on, I've generally found the combination of the two approaches to give me an answer. You can either first check for obvious non-shellability with (2), and if everything is positive apply (1); or else first check shellability with (1), and if the computation appears to hang, then look for a negative entry in the $h$-triangle.
(But this works for me partly because the complexes I look at usually arise from some kind of "nice" combinatorial object or process.)

Related Question