Testing simplicial complexes for shellability

Question

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.

Answer 1

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.)

Answer 2

In a very recent work (https://arxiv.org/abs/1711.08436) it was shown that deciding shellability is NP-complete.

Answer 3

Since there were no answers for a few months, I asked this question to my colleague and triangulation expert Frank Lutz. Since his response was wonderful and exhaustive, I am reproducing it here for the benefit of others who find such matters interesting.

Spoiler alert: it is very hard to test for shellability.

---

Testing shellability is a mess. The complexity status is open, but believed to be NP complete. There is an implementation in the polymake package:

--> Follow the links:

  Objects
    + SimplicialComplex
       + Combinatorics
           + Shellable

As far as I remember, the polymake implementation is based on the Shellability checker of Masahiro Hachimori. The bad news is that the procedure uses backtracking/reverse search and thus basically goes through all possible permutations. The good news is that local conditions on homology vectors are checked, which allows one to cut the search tree and speed up computations.

In the special case of triangulated 3-balls/3-spheres, I wrote backtracking code for testing shellability myself:

 # vertices     # triangulated 3-balls   # non-shellable 3-balls
      4                     1                       -
      5                     3                       -
      6                    12                       -
      7                   167                       -
      8                 10211                       -
      9               2451305                      29
     10            1831363502                  277479

See http://arxiv.org/pdf/math/0604018 and http://arxiv.org/abs/math/0610022

I had a look at the 29 non-shellable 9-vertex 3-balls, the smallest of these is described here. Among these, there are rather different types. In particular, for being "shellable" or "non-shellable" it really can matter in which way some tetrahedron is attached to what has been built before, which makes testing difficult.

My guess would be that there is no way arround backtracking, although local conditions can help to achieve some speed up. For testing explicit examples (of dimension at least 3), the following will happen:

- If some example is shellable, there is a good chance
  to find a shelling sequence with backtracking.

- If some example is non-shellable (and has, say, 20 or more vertices),
  it will be hopeless to complete the backtrack search.

Answer 4

You might also be interested in vertex decomposability; a relevant package written by David Cook (for Macaulay 2) is described in this paper: http://j-sag.org/Volume2/jsag-5-2010.pdf.

Answer 5

This unpublished article (collaboration welcome) presents a systematic approach to decide shellability, which goes beyond extending partial shellings (that can confirm but hardly disprove shellability). Furthermore, our method (unlike Moriyama's algorithm) does not need the face-numbers. Instead of the $n!$ permutations of the $n$ facets we deal with certain admissible chains in certain posets of cardinality at most $n \cdot 2^n$ (which is $<< n!$). The shellability status of some matroid and some chessboard complexes with up to 24 facets is determined, or redetermined. Moreover the total number of shellings can be calculated. For instance the simplicial complex of all trees of the complete graph $K_4$ has exactly 722965625856 shellings. The previously known lower bound to the number of shellings was $6!=720$.