OBSTRUCTIONS TO SHELLABILITY

Michelle L. Wachs

Abstract. We consider a simplicial complex generaliztion of a result of Billera and Meyers that every nonshellable poset contains the smallest nonshellable poset as an induced subposet. We prove that every nonshellable 2-dimensional simplicial complex contains a nonshellable induced subcomplex with less than 8 vertices. We also establish CL-shellability of interval orders and as a consequence obtain a formula for the Betti numbers of any interval order.

A recent result of Billera and Meyers [BM] implies that every nonshellable poset contains as an induced subposet the 4 element poset Q consisting of two disjoint 2 element chains. (Throughout this paper shellability refers to the general notion of nonpure shellability introduced in [BW2].) Note that Q is the nonshellable poset with the fewest number of elements. Of course a shellable poset can also contain Q; eg., the lattice of subsets of a 3 element set. So the condition of not containing Q as an induced subposet is only sufficient for shellability; it does not characterize shellability. It is however a well-known characterization of a class of posets called interval orders and the question of whether all interval orders are shellable is what Billera and Meyers were considering in the first place.

In this note we suggest a way to generalize the poset result to general simplicial complexes. We also give a simple proof of the poset result and prove the stronger result that any poset that does not contain Q as an induced subposet is CL-shellable. This yields a recursive formula for the Betti numbers of the poset.

We assume familiarity with the general theory of shellability [BW2] [BW3]. All notation and terminology used here is defined in [BW2 ]and [BW3].

The most simple minded conjecture one could make is that every nonshellable simplicial complex contains the induced subcomplex consisting of edges {a, b} and {c, d}, where a, b, c, d are distinct vertices. A simple counterexample is given by the 5 vertex simplicial complex consisting of facets {a, b, c}, {c, d, e}, {a, d}. Indeed the situation for simplicial complexes turns out to be much more complicated than it is for posets.

The most natural thing to do next is to look for other “obstructions” to simplicial complex shellability. Is there a finite list? Below we see that the answer is no. Define

Typeset by AMS-TEX

Research supported in part by NSF grant DMS 9311805 at the University of Miami and by NSF grant DMS-9022140 at MSRI.

an obstruction to shellability to be a nonshellable simplicial complex all of whose proper induced subcomplexes are shellable. The 4 and 5 vertex simplicial complexes given above are examples of one and two dimensional obstructions, respectively. The following observation was made by Stanley [S].

Proposition 1. For every positive integer d there is an obstruction to shellability of dimension d.

Proof. Let K be the (d − 1)-skeleton of the simplex on vertex set [d + 3] = {1, 2, …, d+3} together with two d-dimensional faces {1, 2, …, d+1} and {3, 4, …, d+ 3}. We claim that K is a d-dimensional obstruction. If K were shellable then by the Rearrangement Lemma of [BW2] there would be a shelling order in which the maximal dimensional facets come first; namely {1, 2, …, d+1} and {3, 4, …, d+3} come first. But this is impossible because these two facets intersect in a face of dimension d − 2. Hence K is not shellable.

Every proper induced subcomplex of K is either a simplex or consists of a single d-face in a (d + 1)-simplex together with the (d − 1) skeleton of the (d + 1)-simplex. Certainly the simplex is shellable. Let J be the (d − 1)-skeleton of the simplex on vertex set [d + 2] together with the face {1, 2, …, d + 1}. It is easy to see that lexicographical order on the facets of J is a shelling of J. (Lexicographical order on subsets of [d + 2] is defined by {a_{1} ≤ ⋯ ≤ a_{k}} ≤ {b_{1} ≤ ⋯ ≤ b_{j}} if the word a_{1} ⋯ a_{k} is less than the word b_{1} ⋯ b_{j} in lexicographical order.) Therefore all proper induced subcomplexes of K are shellable. □

We now consider the following problem.

Problem. Determine whether or not there is a finite number of d-dimensional obstructions to shellability for each d. If so, find bounds on the number of vertices that a d-dimensional obstruction can have.

In this paper we solve this problem only for dimensions d = 1, 2 and we leave open the problem for general d.

Proposition 2. The only 1-dimensional obstruction to shellability is the complex J generated by facets {a, b}, {c, d} where a, b, c, d are distinct.

Proof. A 1-dimensional simplicial complex is shellable if and only if it has at most one connected component with more than 1 vertex. If K is a nonshellable 1dimensional simplicial complex then let {a, b} be an edge in one component of K and let {c, d} be an edge in another component. The subcomplex induced by a, b, c, d is J. Hence K is an obstruction if and only if K = J. □

Already in dimension 2 the situation is much more complicated. We use the following notation: For any subset U of V and simplicial complex K on vertex set V, let K(U) be the subcomplex of K induced by U. Also let the pure part of K, denoted pure(K), be the subcomplex of K generated by the facets of maximum dimension. For v ∈ V, the link of v in K is denoted lk_{K}(v) and is defined to be {F ∈ K | F ∪{v} ∈ K and v ∉ F }. For any v ∈ V and subcomplex J of lk_{K}(v), the join of v and J is denoted v∗J and is defined to be {F ∈ K | v ∈ F and F \{v} ∈ J}. The ith reduced simplicial homology of K over the ring of integers is denoted by H̃_{i}(K).

Theorem 3. There are no 2-dimensional obstructions with more than 7 vertices.

Proof. Let K be a 2-dimensional simplicial complex on vertex set V where |V | > 7. Assume all induced proper subcomplexes are shellable. We shall show that K is shellable by showing that pure(K) is shellable and the 1-skeleton of K is connected (except for isolated points). That the 1-skeleton is connected follows immediately from the fact that no induced subcomplex consists only of a pair of disjoint edges.

To prove that pure(K) is shellable, choose any vertex v of pure(K). Let

K_{1} = pure(K(V \ {v})).

Since the pure part of a shellable complex is shellable (by the Rearrangement Lemma of [BW2]), K_{1} is shellable. Let

K_{2} = v ∗ pure(lk_{K}(v)).

We claim that pure(lk_{K}(v)) is a connected 1-dimensional complex. If not there would be distinct vertices a, b, c, d ∈ V \ {v} such that edges {a, b} and {c, d} are in different components of pure(lk_{K}(v)). Since |V | > 5, the induced subcomplex K({v, a, b, c, d}) would be shellable which would imply that lk_{K({v,a,b,c,d})}(v) is shellable since the link of any vertex in a shellable complex is shellable [BW3]. But this is impossible since lk_{K({v,a,b,c,d})}(v) has only two facets {a, b} and {c, d}. It follows from this claim that K_{2} is shellable and 2-dimensional.

Next we dispose of the special cases that K_{1} is 0 or 1-dimensional. Clearly K_{1} can’t be 0-dimensional since v belongs to a 2-face. If K_{1} is 1-dimensional then pure(K) = K_{2} which is shellable.

Now we can assume that K_{1} and K_{2} are both shellable and 2-dimensional. Note that then

pure(K) = K_{1} ∪ K_{2}.

Let

A = K_{1} ∩ K_{2}.

We shall show that A is connected and 1-dimensional. Suppose it isn’t. Then either (1) A = {∅}, (2) A contains an isolated point or (3) there are edges in different components of A. For the first case, choose any a, , b, c, d, e such that {a, b} ∈ pure(lk_{K}(v)) and {c, d, e} ∈ K_{1}. Since |V | > 6, K({v, a, b, c, d, e}) is shellable. It follows that {v, a, b} and {c, d, e} cannot be the only 2-faces of K({v, a, b, c, d, e}). Hence there is a third 2-face F. Note v ∉ F because otherwise one of the other vertices of F would be in A. So F ∈ K_{1}. Since either a or b is a vertex of F as well as of pure(lk_{K}(v)), a or b is a vertex of K_{1} ∩ K_{2}. Hence A cannot be {∅}.

For the second case, let a be the isolated point. Then K_{1} and K_{2} contain 2faces {a, c, d} and {v, a, b}, respectively, which intersect only at a. Since |V | > 5, K({v, a, b, c, d}) is shellable. This means that there is a third 2-face in the induced subcomplex that intersects each of the 2-faces along edges that contain a. If the third 2-face contains v then it is either {v, a, c} or {v, a, d}. This implies that either {a, c} or {a, d} is in A, which contradicts the fact that {a} is a facet of A. Hence the third 2-face must be {a, b, c} or {a, b, d}. It follows that {a, b} is a facet of A, which is still a contradiction.

For the third case, suppose that {a, b} and {c, d} are edges in different components of A. Let x, y ∈ V \ {v} be such that {a, b, x} and {c, d, y} are facets of K_{1}. Since |V | > 7, J = K({v, a, b, c, d, x, y}) is shellable. Let

B = (v ∗ pure(lk_{J}(v))) ∩ pure(K({a, b, c, d, x, y})).

Since B is a subcomplex of A, {a, b} and {c, d} are in different components of B. It follows that H̃_{0}(B) ≠ 0. Since v ∗ pure(lk_{J}(v)) is contractible, we also have H̃_{i}(v ∗ pure(lk_{J}(v))) = 0 for all i. By the Rearrangement Lemma of [BW2], pure(K({a, b, c, d, x, y}) is shellable since the induced subcomplex K({a, b, c, d, x, y}) is. Hence H̃_{i}(pure(K({a, b, c, d, x, y}))) = 0 for i ≤ 1. Since

pure(J) = (v ∗ pure(lk_{J}(v))) ∪ pure(K({a, b, c, d, x, y})),

by Mayer-Vietoris we have that H̃_{1}(pure(J)) = H̃_{0}(B) ≠ 0. This contradicts the fact that J is shellable and 2-dimensional. Hence we may conclude that A is connected and 1-dimensional.

Since A and pure(lk_{K}(v)) are connected we can get a shelling of pure(lk_{K}(v)) by first listing the edges of A and then listing the remaining edges of pure(lk_{K}(v)) so that each edge is connected to the previous ones. We claim that we can obtain a shelling of pure(K) by first listing the facets of K_{1} in the order given by the shelling of K_{1} and then listing the facets of K_{2} = v ∗ pure(lk_{K}(v)) in the order indicated by the shelling of pure(lk_{K}(v)) in which the edges of A come first. Let F_{1}, F_{2}, …, F_{n} be the resulting ordered list of facets of pure(K).

If F_{i} ∈ K_{1} then it is clear that (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i} is pure 1-dimensional. If F_{i} = {v, a, b} where {a, b} ∈ A then it is easy to see that {a, b} is a facet of (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i} and that for all but the first F_{i} in v ∗ A, {v, a} or {v, b} is also a facet of (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i}. Hence (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i} is pure 1-dimensional for all F_{i} ∈ v ∗ A.

Now suppose F_{i} = {v, a, b} where {a, b} ∉ A. Clearly either {v, a} or {v, b} is a facet of (F̄_{1}∪F̄_{2}∪⋯∪F̄_{i−1})∩F̄_{i}; assume without loss of generality that {v, a} is the facet. If {b} is a facet of (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i}, then b is in some 2-face {b, c, d} of K_{1}. Consider the induced subcomplex L = K({v, a, b, c, d}). Since pure(L) is shellable, L contains one of the following 2-faces: {a, b, c}, {a, b, d}, {v, b, c} or {v, b, d}. The first two are impossible since {a, b} ∉ A. The last two facets have to precede {v, a, b} in the shelling because {b, c} and {b, d} are in A. It follows that {v, b} ∈ (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i} which contradicts the assumption that {b} is a facet. Hence {b} is not a facet of (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i} which implies that (F̄_{1} ∪ F̄_{2} ∪ ⋯ ∪ F̄_{i−1}) ∩ F̄_{i} is pure 1-dimensional. Therefore F_{1}, F_{2}, …, F_{n} is indeed a shelling of pure(K). □

Corollary 4. Every nonshellable 2-dimensional simplicial complex has a nonshellable induced subcomplex with n vertices where 4 ≤ n ≤ 7. □

Theorem 5. For each n = 5, 6, 7, there is a 2-dimensional obstruction with n vertices.

Proof. Let M_{n} be the simplicial complex on vertex set {1, …, n} with facets {1, 2, 3}, {2, 3, 4}, …, {n − 2, n − 1, n}, {n − 1, n, 1}, {n, 1, 2}. For n ≥ 5, M_{n} triangulates a cylinder when n is even and a Möbius strip when n is odd. Hence M_{n} is not shellable. We leave it to the reader to check that every induced proper subcomplex of M_{n} is shellable when n ≤ 7. □

The obstructions given in the proof of Theorem 5 are pseudomanifolds with boundary. We show next that a pseudomanifold without boundary cannot be an obstruction in any dimension.

Lemma 6. Let K be a simplicial complex on vertex set V. Suppose that v ∈ V is such that K(V \ {v}) and lk_{K}(v) are shellable and no facet of lk_{K}(v) is a facet of K(V \ {v}). Then K is shellable.

Proof. First list the facets of K(V \ {v}) in any shelling order and then list the facets of v ∗ lk_{K}(v) in the order indicated by the shelling of lk_{K}(v). It is easy to see that this is a shelling of K. □

Theorem 7. Let K be a simplicial complex for which every nonfacet face is contained in at least two facets. Then K is not an obstruction. Consequently, there are no obstructions that are pseudomanifolds (without boundary) or triangulations of manifolds (without boundary).

Proof. The proof is by induction on dim K. When dim K = 1 the result follows immediately from Proposition 2. Suppose dim K > 1 and every proper induced subcomplex of K is shellable. We will show that K must also be shellable. Let V be the vertex set of K and choose any v ∈ V. Then K(V \ {v}) is shellable. It follows from the fact that every nonfacet face is in at least two facets of K that no facet of lk_{K}(v) is a facet of K(V \ {v}).

To apply Lemma 6 we need only show that lk_{K}(v) is shellable. Note that the property that every nonfacet face is contained in at least two facets, is inherited by lk_{K}(v). Hence if lk_{K}(v) is not shellable then by induction it contains an obstruction lk_{K}(v)(U), where U ⊊ V \ {v}. We have that K(U ∪ {v}) is shellable since it is a proper induced subcomplex of K. Since lk_{K}(v)(U) = lk_{K(U∪{v})}(v) and any link in a shellable complex is shellable, we have that lk_{K}(v)(U) is also shellable, contradicting the fact that lk_{K}(v)(U) is an obstruction. Therefore lk_{K}(v) is shellable and by Lemma 6, K is shellable. So K is not an obstruction. □

A “pure” version of Lemma 6 is used implicitly in Provan and Billera’s proof of shellability of matroid complexes [PB]. A matroid complex is a simplicial complex for which all induced subcomplexes are pure. Lemma 6 can, in fact, be used to prove the following stronger result.

Proposition 8. If every proper induced subcomplex of a simplicial complex K is pure then K is shellable.

Proof. The proof is by induction on the size of the vertex set V. Suppose that K is not a simplex. Let F be any d-dimensional facet of K where d = dim K. Choose v ∈ V \ F. Clearly K(V \ {v}) is pure d-dimensional since it contains F. It follows that no facet of lk_{K}(v) is a facet of K(V \ {v}).

By induction, K(V \ {v}) is shellable. To apply Lemma 6, we need only show that lk_{K}(v) is also shellable. For any U ⊊ V \ {v}, K(U ∪ {v}) is pure. Since lk_{K}(v)(U) = lk_{K(U∪{v})}(v) and any link in a pure complex is pure, we have that lk_{K}(v)(U) is pure. Hence every proper induced subcomplex of lk_{K}(v) is pure. It follows by induction that lk_{K}(v) is shellable. □

Remark. Provan and Billera [PB] prove that matroid complexes are shellable by showing that they are vertex decomposible. The proof of Proposition 8 given here is a slight modification of the Provan-Billera proof and also yields the conclusion that K is vertex decomposible, but in the nonpure sense described in [BW 3].

Define an obstruction to purity to be a nonpure simplicial complex for which all proper induced subcomplexes are pure. Proposition 8 extends the Provan-Billera result from matroid complexes to obstructions to purity. It turns out that there are really very few obstructions to purity in each dimension.

Proposition 9. For each d ≥ 1, every d-dimensional obstruction to purity has exactly d + 2 vertices. Moreover there exists a d-dimensional obstruction to purity for each d.

Proof. Let K be a d-dimensional simplicial complex with vertex set V. Suppose |V | > d + 2 and all proper induced subcomplexes of K are pure. We will show that K is also pure.

Let v ∈ V \F, where F is any d-dimensional face of K. It follows that K(V \{v}) is pure d-dimensional. To show that K is pure we need only show that lk_{K}(v) is pure (d − 1)-dimensional. Let G be a face of lk_{K}(v). Then since K(V \ {v}) is pure d-dimensional, G is contained in some d-dimensional facet H of K(V \ {v}). Since H ∪ {v} ≠ V, it follows that K(H ∪ {v}) is pure d-dimensional. Since G ∪ {v} ∈ K(H ∪ {v}), it follows that G ∪ {v} is contained in a facet of dimension d in K(H ∪ {v}). This implies that G is contained in a (d − 1)-dimensional face of lk_{K}(v), which means that lk_{K}(v) is pure and (d − 1)-dimensional.

An example of a d-dimensional obstruction to purity is given by the (d − 1)- skeleton of the simplex on vertex set [d + 2] together with the d-dimensional face [d + 1]. □

Lemma 6 also yields a simple proof of the shellability of interval orders which we give below. Recall that a bounded poset is a poset that has a minimum element ˆ0 and a maximum element ˆ1. If P is a bounded poset then P̄ denotes the induced subposet P \ {ˆ0, ˆ1}. The length of bounded poset P is the length of the longest chain from ˆ0 to ˆ1. For any a ≤ b in P, the open interval {x ∈ P | a < x < b} is denoted by (a, b) and the closed interval {x ∈ P | a ≤ x ≤ b} is denoted by [a, b]. The order complex of P is the simplicial complex of chains of P and is denoted by Δ(P).

Proposition 10. (Billera and Meyers) Every interval order is shellable.

Proof. Let P be an interval order. By the well-known characterization of interval orders, P does not contain Q (the poset with two disjoint 2 element chains) as an induced subposet. We may assume without loss of generality that P is bounded and that P has more than one atom.

The fact that P does not contain Q enables us to choose an atom a such that each of the covers of a is greater than some other atom. Since lk_{Δ(P̄)}(a) = Δ((a, ˆ1)), this implies that no facet of lk_{Δ(P̄)}(a) is a facet of Δ(P̄ \ {a}). Also the interval (a, ˆ1) and the induced subposet P̄ \ {a} both inherit the property of not containing Q as an induced subposet. Hence by induction they are shellable. We conclude that Δ(P̄) and hence P are shellable by Lemma 6. □

Remark. Björner [B] has independently used the same idea to prove more generally that all interval orders are vertex decomposable.

Another proof that interval orders are shellable can be obtained using the technique of lexicographical shellability, cf. [BW2].

Theorem 11. Every bounded interval order is CL-shellable.

Proof. Let P be a bounded interval order. Partially order the atoms of P by letting a ≺ b if a has a cover that is not greater than b. Antisymmetry and transitivity follow readily from the forbidden induced subposet characterization of interval order. It is straight forward to verify that any linear extension of ⪯ is a recursive atom ordering of P by induction on |P |. Therefore P is CL-shellable. □

For any bounded poset P let β_{i}(P) be the ith reduced Betti number of Δ(P̄). It is easy to see that in the partial order on atoms given in the proof of Theorem 11 there is a unique minimum atom. We shall refer to this atom as the smallest atom.

Corollary 12. Let P be bounded interval order of length ≥ 2, let A be its set of atoms and let a_{0} be its smallest atom. Then for i ≥ 0,

β_{i}(P) = ∑_{a∈A\{a_{0}}} β_{i−1}([a, ˆ1]).

Proof. By [BW2, Theorem 5.9], β_{i}(P) is the number of falling maximal chains of length i + 2 with respect to the CL-labeling induced by the recursive atom ordering given in Theorem 11. So we need to describe these falling chains. Each falling chain from ˆ0 to ˆ1 of length i + 2 is of the form {ˆ0} ∪ c where c is a falling chain of length i + 1 from a to ˆ1 for some atom a. We need to determine which atoms a and falling chains c from a to ˆ1 are such that {ˆ0} ∪ c is falling. The proof of [BW1, Theorem 3.2] produces a CL-labeling from a recursive atom ordering (although it’s done in the pure case in [BW1], it easily carries over to general case, cf. [BW2]). A maximal chain has a descent on the subchain ˆ0 → a → b if and only if b is greater than an atom that precedes a in the recursive atom ordering. This happens for every maximal chain through a ≠ a_{0} and for no maximal chain through a_{0}. Hence the maximal chains of the form {a} ∪ c, where a ≠ a_{0} and c is a falling chain of [a, ˆ1], are the falling chains of P. □

The problem of studying obstructions could conceivably be made easier by considering special classes of simplicial complexes that are closed under taking induced subcomplexes. A natural class, suggested by Björner [B], is the class of flag complexes. One might ask whether the pair of disjoint edges is the only obstruction for flag complexes. It turns out that this is not the case. The obstruction M_{7} given in the proof of Theorem 5 is a flag complex. However obstructions M_{5} and M_{6} are not flag complexes. Also the obstructions given in the proof of Proposition 1 are not flag complexes. So there might still be something interesting to say about flag complex obstructions.

Acknowledgment

I am grateful to Richard Stanley for stimulating discussions which initiated this study of obstructions.

References

[BM] L. Billera and A. Meyers, Shellability of interval orders, in preparation.

[B] A. Björner, personal communication.

[BW1] A. Björner and M.L. Wachs, On lexicographically shellable posets, Trans. AMS 277 (1983), 323–341.

[BW2] A. Björner and M.L. Wachs, Nonpure shellable complexes and posets I, Trans. AMS 348 (1996), 1299–1327.

[BW3] A. Björner and M.L. Wachs, Nonpure shellable complexes and posets II, preprint 1994, Trans. AMS (to appear).

[PB] J.S. Provan and L.J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Op. Res. 5 (1980), 576–594.

[S] R.P. Stanley, personal communication.

Department of Mathematics, University of Miami, Coral Gables, FL 33124

   E-mail address: wachs@math.miami.edu