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