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](http://en.wikipedia.org/wiki/Shelling_(topology)) 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](http://www.jstor.org/stable/1999359) or [here](http://www.combinatorics.org/Volume_16/PDF/v16i2r1.pdf) 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.



Testing simplicial complexes for shellability
Since there were no answers for a few months, I asked this question to my colleague and triangulation expert [Frank Lutz](http://page.math.tu-berlin.de/~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](http://www.polymake.org/release_docs/2.12/topaz.html) package:



```
--> Follow the links:

  Objects
    + SimplicialComplex
       + Combinatorics
           + Shellable

```

As far as I remember, the polymake implementation is based on the [Shellability checker](http://infoshako.sk.tsukuba.ac.jp/~hachi/math/rsshell/index.html) of [Masahiro Hachimori](http://infoshako.sk.tsukuba.ac.jp/~hachi/). 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](http://www.eg-models.de/models/Simplicial_Manifolds/2003.05.004/_direct_link.html). 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.

```

