\input amstex
\documentstyle{amsppt}
\NoBlackBoxes
\magnification=1200
\hcorrection{.25in}
\advance\vsize-.75in
\topmatter
\title\nofrills OBSTRUCTIONS TO SHELLABILITY
\endtitle
\author Michelle L. Wachs
\endauthor
%\affil Department of Mathematics \\ University of Miami\\ Coral
%Gables, FL 33124\endaffil
\address Department of Mathematics, University of Miami, Coral Gables,
FL 33124
\endaddress
\email wachs\@math.miami.edu \endemail
\thanks Research supported in part by  NSF
grant DMS 9311805 at the University of Miami and by NSF grant DMS-9022140
at MSRI.
\endthanks
%\date  June 1, 1997
%\enddate
\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.

\endabstract
\endtopmatter
\document
\def \pure{\operatorname{pure}}
\def \lk{\operatorname{lk}}


A recent result of Billera and Meyers \cite{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
\cite {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
\cite{BW2} \cite{BW3}.  All notation and terminology used here is defined in
\cite{BW2 }and \cite{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 an {\it 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 \cite{S}.

\proclaim{Proposition 1} For every positive integer $d$ there is an
obstruction to shellability of dimension $d$.
\endproclaim

\demo{Proof}  Let $K$ be the
$(d-1)$-skeleton  of the simplex on vertex set $[d+3]=
\{1,2,\dots,d+3\}$ together with  two
$d$-dimensional faces
$\{1,2,\dots,d+1\}$ and $
\{3,4,\dots,d+3\}$.  We claim that $K$ is a $d$-dimensional
obstruction.  If
$K$ were shellable then by the Rearrangement Lemma of \cite {BW2}
there  would be a shelling order in which the maximal dimensional
facets come first; namely 
$\{1,2,\dots,d+1\}$ and
$\{3,4,\dots,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,\dots,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 \le \dots \le a_k\} \le \{b_1
\le
\dots
\le b_j
\}$ if the word $a_1 \cdots a_k$ is less than the word $b_1 \cdots
b_j$ in lexicographical order.) Therefore all proper induced
subcomplexes of $K$ are shellable.\hfill\qed
\enddemo

We now consider the following problem.

\proclaim{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.
\endproclaim 

% We now pose the question of
%whether the set of
%$d$-dimensional obstructions to shellability  is finite for each $d$.

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


\proclaim{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.  
\endproclaim

\demo{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 $1$-dimensional
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$. \hfill\qed
\enddemo

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 \in V$, the link of $v$ in $K$ is denoted
$\lk_K(v)$ and is defined to be $\{F \in K \mid F \cup \{v\} \in K
\text{ and } v \notin F\}$.  For any $v \in
V$ and subcomplex $J$ of $\lk_K(v)$,  the join of $v$ and $J$ is
denoted
$v*J$ and is defined to be
$\{F \in K \mid v \in F \text{ and } F \setminus \{v\} \in J\}$.
The ith reduced simplicial homology of $K$ over the ring of integers is
denoted by $\tilde H_i(K)$. 


\proclaim{Theorem 3} There are no 2-dimensional obstructions with more
than 7 vertices.
\endproclaim

\demo{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\setminus\{v\})).$$  Since the pure part of a shellable
complex is shellable (by the Rearrangement Lemma of \cite{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 \in V \setminus
\{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
\cite{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 \cup K_2.$$    Let $$A =
K_1
\cap K_2.$$

  We shall show that $A$ is connected and 1-dimensional.
Suppose it isn't.  Then either (1) $A = \{\emptyset\}$, (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\} \in \pure(\lk_K(v))$ and $\{c,d,e\} \in 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 \notin F$ because otherwise one of the other
vertices of $F$ would be in $A$.  So $F \in 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 \cap K_2$.  Hence $A$ cannot be $\{\emptyset\}$.  

For the second  case, let $a$ be the isolated point.  Then
$K_1$ and
$K_2$ contain 2-faces 
$\{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
\in V
\setminus \{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))) \cap
\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
$\tilde H_0(B) \ne 0$.  Since $v*\pure(\lk_J(v))$ is
contractible, we also have $\tilde H_i(v*\pure(\lk_J(v))) = 0$
for all $i$.  By the Rearrangement Lemma of
\cite{BW2}, $\pure(K(\{a,b,c,d,x,y\})$  is shellable since the
induced subcomplex $K(\{a,b,c,d,x,y\})$ is. Hence $\tilde
H_i(\pure(K(\{a,b,c,d,x,y\}))) = 0$ for $i \le 1$.  Since 
$$\pure(J) = (v*\pure(\lk_J(v))) \cup
\pure(K(\{a,b,c,d,x,y\})),$$
 by  Mayer-Vietoris 
we have that $\tilde H_1(\pure(J)) =\tilde H_0(B) \ne 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,\dots,F_n$ be the resulting ordered list of facets of
$\pure(K)$. 

 If
$F_i \in K_1$ then it is clear that  $(\bar F_1 \cup \bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$ is   pure
1-dimensional.  If
$F_i =
\{v,a,b\}$ where $\{a,b\} \in A$ then it is easy to see that  
$\{a,b\}$ is a facet of $(\bar F_1 \cup \bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$ and that for all but
the first $F_i$ in $v*A$, $\{v,a\}$ or $\{v,b\}$ is also a facet 
of $(\bar F_1 \cup \bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$. Hence $(\bar F_1 \cup
\bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$ is pure 1-dimensional
for all $F_i \in v*A$.  

Now suppose $F_i = \{v,a,b\}$ where
$\{a,b\}
\notin A$.  Clearly either $\{v,a\}$ or $\{v,b\}$ is  a facet of $
(\bar F_1
\cup
\bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$; assume without loss
of generality that $\{v,a\}$ is the facet.  If
$\{b\}$ is a facet of $ (\bar F_1 \cup
\bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar 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\} \notin 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\} \in (\bar F_1 \cup
\bar F_2 
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$ which contradicts the
assumption that $\{b\}$ is a facet.  Hence $\{b\}$ is not a facet of $
(\bar F_1 \cup
\bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i $ which implies that 
$ (\bar F_1 \cup
\bar F_2
\cup
\dots \cup \bar F_{i-1}) \cap \bar F_i$ is pure
1-dimensional. Therefore $F_1,F_2,\dots,F_n$ is indeed a shelling of
$\pure(K)$.
\hfill\qed
\enddemo

\proclaim{Corollary 4} Every nonshellable $2$-dimensional simplicial
complex  has a nonshellable induced subcomplex with $n$ vertices
where $4 \le n \le 7$.\hfill \qed
\endproclaim

\proclaim{Theorem 5} For each $n=5,6,7$,  there is a $2$-dimensional
obstruction with $n$ vertices. 
\endproclaim

\demo{Proof}  Let $M_n$ be the simplicial  complex on vertex set
$\{1,\dots ,n\}$ with facets $\{1,2,3\}$, $\{2,3,4\}$, $\dots$,
$\{n-2,n-1,n\}$, $\{n-1,n,1\}$, $ \{n,1,2\}$.  For  $n \ge 5$,
$M_n$ triangulates a cylinder when $n$ is even and a M\"obius 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 \le 7$.\hfill\qed
\enddemo

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.

\proclaim{Lemma 6} Let $K$ be a simplicial complex on vertex
set $V$.  Suppose that $v \in V$ is such that $K(V \setminus \{v\})$
and $\lk_K(v)$ are shellable and no facet of $\lk_K(v)$ is a
 facet of $K(V \setminus \{v\})$. Then $K$ is shellable.
\endproclaim

\demo{Proof}  First list the facets of $K(V \setminus \{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$.\hfill\qed
\enddemo

\proclaim{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). 
\endproclaim

\demo{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 \in V$.  Then
$K(V\setminus
\{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\setminus
\{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 \subsetneq V \setminus\{v\}$. We
have that 
$K(U\cup\{v\})$ is shellable since it is a  proper induced subcomplex
of $K$.  Since
$ \lk_K(v)(U)=\lk_{K(U\cup\{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.\hfill\qed
\enddemo

A ``pure'' version of Lemma~6 is used implicitly in Provan and Billera's
proof of shellability of matroid complexes \cite{PB}.  A {\it 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.



\proclaim{Proposition 8} If every proper induced subcomplex of a simplicial
complex $K$ is pure then $K$ is shellable.
\endproclaim
\demo{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 \in V \setminus
F$.   Clearly $K(V \setminus \{v\})$ is pure
$d$-dimensional since it contains $F$.  It follows that no facet of 
$\lk_K(v)$ is a facet of  
$K(V
\setminus \{v\})$.  

By induction,
$K(V
\setminus
\{v\})$ is  shellable.  To apply Lemma~6, we need only show that  $\lk_K(v)$
is also shellable.   For  any $U \subsetneq V\setminus \{v\}$, $K(U \cup
\{v\})$ is pure.  Since 
$\lk_K(v)(U) =
\lk_{K(U
\cup \{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.\hfil\qed
\enddemo

\demo {Remark}  Provan and Billera \cite{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 \cite{BW 3}.
\enddemo


Define an {\it 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.

\proclaim{Proposition 9} For each $d \ge 1$, every $d$-dimensional
obstruction to purity has exactly $d+2$ vertices.  Moreover there exists a
$d$-dimensional obstruction to purity for each $d$.
\endproclaim 

\demo{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 \in V\setminus F$, where $F$ is any $d$-dimensional face of $K$.  It
follows that $K(V\setminus\{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\setminus\{v\})$ is pure 
$d$-dimensional, $G$ is contained in some $d$-dimensional facet $H$ of
$K(V\setminus\{v\})$.  Since $H \cup \{v\} \ne V$, it follows that  $K(H \cup
\{v\})$ is pure
$d$-dimensional.  Since $G \cup \{v\} \in K(H \cup
\{v\})$, it follows that $G
\cup \{v\}$ is contained in a facet of dimension $d$ in $K(H \cup
\{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]$.
\hfill\qed
\enddemo

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
$\hat 0$ and a maximum element $\hat 1$. If $P$ is a bounded poset then
$\bar P$ denotes the induced subposet $P\setminus \{\hat 0, \hat 1\}$.  The
length of bounded poset
$P$ is the length of the longest chain from $\hat 0$ to $\hat 1$.   For any
$a
\le b$ in $P$, the open interval
$\{x \in P \mid a < x < b\}$ is denoted by $(a,b)$ and the closed interval
$\{x \in P \mid a \le x \le b\}$ is denoted by $[a,b]$.  The order
complex of $P$ is the simplicial complex of chains of $P$
and is denoted by $\Delta(P)$.

\proclaim{Proposition 10} (Billera and Meyers)  Every interval order is
shellable. 
\endproclaim

\demo{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_{\Delta(\bar P)}(a) = \Delta((a,\hat 1))$,
this implies that no facet of
$\lk_{\Delta(\bar P)}(a)
$ is a facet of $\Delta(\bar P\setminus \{a\})$.  Also the interval
$(a,\hat 1)$  and the induced subposet $\bar P\setminus \{a\}$ both
inherit the property of not containing $Q$ as an induced subposet. 
Hence by induction they are shellable.  We conclude that
$\Delta(\bar P)$ and hence
$P$ are shellable by Lemma 6. \hfill\qed 
\enddemo


\demo{Remark} Bj\"orner \cite{B} has independently used the same idea
to prove more generally that all interval orders are vertex decomposable.
\enddemo

Another   proof that interval orders are shellable can be
obtained using the technique of lexicographical shellability, cf. \cite
{BW2}.

\proclaim{Theorem 11} Every bounded interval order is CL-shellable.
\endproclaim

\demo{Proof} Let $P$ be a bounded interval order. 
Partially order the atoms of $P$ by letting $a \prec 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 $\preceq$ is a recursive atom ordering of $P$ by
induction on $|P|$.  Therefore $P$ is CL-shellable. \hfill\qed
\enddemo

For any bounded poset $P$ let $\beta_i(P)$ be the ith reduced Betti number of
$\Delta(\bar 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 {\it
smallest} atom.

\proclaim {Corollary 12} Let $P$ be bounded  interval order of length $\ge
2$, let
$A$ be its set of atoms and let $a_0$ be its smallest atom.  Then for $i
\ge 0$,
$$\beta_i(P) = \sum_{a \in A\setminus \{a_0\}} \beta_{i-1}([a,\hat
1]).$$
\endproclaim

\demo{Proof}   By \cite{BW2, Theorem~5.9}, $\beta_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 $\hat 0$ to $\hat 1$ of length $i+2$  is of the form $\{\hat
0\}
\cup c$ where
$c$ is a falling chain of length $i+1$ from $a$ to $\hat 1$ for some
atom
$a$.  We need to determine which atoms $a$ and falling chains $c$
from $a$ to $\hat 1$ are such that $\{\hat 0\} \cup c$ is falling.
The proof of \cite{BW1, Theorem 3.2} produces a CL-labeling from a
recursive atom ordering (although it's done in the pure case in
\cite{BW1}, it easily carries over to general case, cf. \cite{BW2}).   A
maximal chain has a descent on the subchain $\hat 0 \to a \to 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
\ne a_0$ and for no maximal chain through $a_0$.  Hence the
maximal chains of the form $\{a\} \cup c$, where $a \ne a_0$ and $c$ is
a falling chain of
$[a,\hat 1]$, are the falling chains of $P$.\hfill\qed
\enddemo

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\"orner
\cite{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.  

\medspace

\heading Acknowledgment \endheading

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

\Refs
\widestnumber\key{BW3}

\ref \key BM \by L. Billera and A. Meyers \paper Shellability of interval
orders \paperinfo in preparation \endref

\ref \key B \by A. Bj\"orner \paperinfo personal communication \endref



\ref \key BW1 \by A. Bj\"orner and M.L. Wachs \paper On lexicographically
shellable posets 
\jour Trans. AMS
\vol 277 \yr 1983 \pages 323--341 \endref

\ref \key BW2 \by A. Bj\"orner and M.L. Wachs \paper Nonpure shellable
complexes and posets I \jour Trans. AMS \vol 348 \yr 1996 \pages
1299--1327 \endref

\ref \key BW3 \by A. Bj\"orner and M.L. Wachs \paper Nonpure shellable
complexes and posets II \jour Trans. AMS \toappear
\paperinfo preprint 1994 \endref

\ref \key PB \by J.S. Provan and L.J. Billera \paper Decompositions of
simplicial complexes related to diameters of convex polyhedra \jour Math.
Op. Res. \vol 5 \yr 1980 \pages 576--594 \endref

\ref \key S \by R.P. Stanley \paperinfo personal communication \endref

\endRefs
 



 





\enddocument






