\documentclass[12pt]{amsart}
\usepackage{verbatim}
\usepackage{amscd}
\usepackage{graphicx}

\numberwithin{equation}{section}
\topmargin = -.15in
\textheight = 8.0in
\textwidth = 6.in
\oddsidemargin=.20in
\evensidemargin=.20in
%\input epsf 

\def\lfigure#1#2#3{\bigbreak
        \centerline{\includegraphics[width=#3\textwidth]{#1}}\nobreak\medskip
        \centerline{#2}\bigbreak
        }



\renewcommand{\theequation}{\thesection.\arabic{equation}}
\setcounter{secnumdepth}{2}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{rmk}[thm]{Remark}
\newtheorem{rmks}[thm]{Remarks}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{exam}[thm]{Example}
\newtheorem{cor}[thm]{Corollary} 
\newtheorem{dfn}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{fig}[thm]{Figure}
\def\overdot{\dot}
\def\ker{\oper{Ker}}
\def\im{\oper{Im}}
\def\S{\Sigma}
\def\BE{\mathbb{E}}
\def\G{\Gamma}
\def\lm{\limits}
\def\tl{\tilde}
\def\d{{\delta}}
\def\oper{\operatorname}
\def\ind{\oper{Index}}
\def\ov{\overline}
\def\wt{\widetilde}
\def\lra{\longrightarrow}
\def\sub{\subheading}
\def\tor{\oper{tor}}
\def\tr{\oper{tr}}
\def\sbq{\subseteq}
\def\[{\left[}
\def\]{\right]}
\def\La{\Lambda}


\def\p{{\partial}}
\def\e{{\epsilon}}
\def\a{{\alpha}}
\def\b{{\beta}}
\def\s{{\sigma}}
\def\g{{\gamma}}
\def\z{{\zeta}}
\def\st{{\,\,\mbox{s.t.}\,\,}}
\def\SN{{\mathcal N}}
\def\SK{{\mathcal K}}
\def\SP{{\mathcal P}}
\def\SR{{\mathcal R}}
\def\SM{{\mathcal M}}
\def\SC{{\mathcal C}}
\def\SD{{\mathcal D}}
\def\SX{{\mathcal X}}
\def\SY{{\mathcal Y}}
\def\SZ{{\mathcal Z}}
\def\SG{{\mathcal G}}
\def\BC{{\mathbf C}}
\def\BO{{\mathbf O}}
\def\BP{{\mathbb P}}
\def\BQ{{\mathbf Q}}
\def\BR{{\mathbb R}}
\def\BS{{\mathbf S}}
\def\BF{{\mathbb F}}
\def\BZ{{\mathbb Z}}


\begin{document}

\title[A User's Guide to Discrete Morse Theory]
{A User's Guide to Discrete Morse Theory}

\author[Robin Forman]{Robin Forman}
\address
{Department of Mathematics, Rice University, Houston,
TX  77251}
\thanks{This work was partially supported by the National Science
Foundation}
\begin{abstract}
A number of questions from a variety of
areas of mathematics lead one
to the problem of analyzing the topology of a simplicial complex.
However, there are few general techniques available to aid us in this study.
On the other hand, some very general theories have been developed for the
study of smooth manifolds. One of the most powerful, and useful, of
these theories is Morse Theory.  In this paper we present a
combinatorial adaptation of
Morse Theory, which we call discrete Morse Theory,
that may be applied to any simplicial complex
(or more general cell complex).
The goal of this paper is to present an overview of the subject of
discrete Morse Theory that is sufficient both to understand the major
applications of the theory to combinatorics, and to apply the
the theory to new problems. We will not be presenting theorems in
their most recent or most general form, and simple examples will
often take the place of proofs. We hope to convey the fact that
the theory is really very simple, and
there is not much that one needs to know before one can become a
``user''.
\end{abstract}

\maketitle


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 48 \rms (2002), Article~B48c\hfill}
\def\thepage{}
%
%


\setcounter{section}{-1}
\section{Introduction}\label{s0}
\setcounter{equation}{0}

A number of questions from a variety of areas of mathematics lead one
to the problem of analyzing the topology of a simplicial complex.
We will see some examples in these notes.
However, there are few general techniques available to aid us in this study.
On the other hand, some very general theories have been developed for the
study of smooth manifolds. One of the most powerful, and useful, of
these theories is Morse Theory. 

There is a very close relationship between the topology of a smooth
manifold $M$ and the critical points of a smooth function $f$ on $M$.
For example, if $f$ is compact, then $M$ must achieve a maximum and a
minimum.  Morse Theory is a far-reaching extension of this fact.
Milnor's beautiful book \cite{Mi1} is the standard reference on
this subject. In this paper we present an adaptation of 
Morse Theory
that may be applied to any simplicial complex (or more general
cell complex).  There have been other adaptations of Morse Theory
that can be applied to combinatorial spaces. For example, a Morse
theory of piecewise linear functions appears in 
\cite{K} and the very powerful
``Stratified Morse Theory'' was developed by Goresky and MacPherson
\cite{GoM1}, \cite{GoM2}.   
These theories, especially the latter, have each been 
successfully applied to prove some
very striking results.  

We take a slightly different approach than that taken in these references.
Rather than choosing a suitable class of continuous functions
on our spaces to play the role of Morse functions,
we will be assigning a single number to each cell
of our complex, and all associated processes will be discrete.
Hence, we have chosen the name {\it discrete Morse Theory} for the
ideas we will describe. 

Of course, these different approaches to combinatorial Morse Theory
 are not distinct.  One can sometimes translate results from one of these
theories to another by ``smoothing out'' a discrete Morse function, 
or by carefully replacing a continuous function
by a discrete set of its values.  However, that is not the path we
will follow in this paper. Instead, we show that even without
introducing any continuity, one can recreate, in the category of
combinatorial spaces, a complete theory that captures many of 
the intricacies of the smooth theory, and can be used as an
effective tool for a wide variety of combinatorial and topological
problems. 

The goal of this paper is to present an overview of the subject of
discrete Morse Theory that is sufficient both to understand the major
applications of the theory to combinatorics, and to apply 
the theory to new problems. We will not be presenting theorems in
their most recent or most general form, and simple examples will 
often take
the place of proofs. We hope to convey the fact that
the theory is really very simple, and
there is not much that one needs to know before one can become a
``user''. Those interested in a more complete presentation of the
theory can consult the reference \cite{F2}. Earlier surveys of this 
work have appeared in \cite{F1} and \cite{F5}.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ROBIN FORMAN}{\SMALL A USER'S GUIDE TO
DISCRETE MORSE THEORY}
%
%

\section{CW Complexes}

The main theorems of discrete (and smooth) Morse Theory are best stated in
the language of CW complexes, so we begin with an overview of the
basics of such complexes.  J.H.C. Whitehead introduced CW complexes
in his foundational work on homotopy theory, and all of the results in
this section are due to him. 
The reader should consult \cite{LW} for 
a very complete introduction to this topic. In this paper we will
consider only finite CW complexes, so many of the 
subtleties of the subject will not appear. 

The building blocks of CW complexes are cells.  Let $B^d$ denote the
closed unit ball in $d$-dimensional Euclidean space.  That is,
$B^d = \{ x \in \BE^d: |x| \le 1 \}$. The boundary of
$B^d$  is the unit $(d-1)$-sphere
$ S^{(d-1)}= \{ x \in \BE^d: |x| = 1 \}$.
A $d$-{\it cell} is a
topological space which is homeomorphic to $B^d$.  
If $\s$ is  $d$-cell, then we denote by $\overdot{\s}$ the subset of
$\s$ corresponding to $S^{(d-1)} \subset B^d$ under any homeomorphism
between $B^d$ and $\s$. A {\it cell} is a topological space which is a
$d$-cell for some $d$.

The basic operation of CW complexes is the notion of {\it attaching a
cell}. Let $X$ be a topological space, $\s$ a $d$-cell and $f:
\overdot{\s} \to X$ a continuous map. We let $X \cup_f \s$ denote the 
disjoint union of $X$ and $\s$ quotiented out by the equivalence
relation that each point $s \in \overdot{\s}$ is identified with $f(s)
\in X$. We refer to this operation by saying 
that $X \cup_f \s$ is the result of
attaching the cell $\s$ to $X$.  The map $f$ is called {\it the
attaching map}. 

We emphasize that the attaching map must be defined on all of $\overdot{\s}$.  
That is, the entire boundary of $\s$ must be ``glued" to $X$.
For example, if $X$ is a circle, then
Figure~\ref{attach}(i) shows one possible result of attaching a 
1-cell to $X$.
Attaching a 1-cell to $X$ cannot lead to the space  illustrated in 
Figure~\ref{attach}(ii)
since the entire boundary of the 1-cell has not been ``glued"to $X$.


\begin{fig}
\lfigure{user1.pdf}{(i). A 1-cell
attached to a circle. (ii). This is {\em not} a 
1-cell attached to a circle}{0.7}
\label{attach}
\end{fig}


We are now ready for our main definition.
A {\it finite CW complex} is any topological space $X$ such that there
exists a finite nested sequence
\begin{equation}
\emptyset \subset X_0 \subset X_1 \subset \dots \subset X_n = X
\label{decomp}
\end{equation}
such that for each $i=0,1,2, \dots,n$, $X_i$ is the result of
attaching a cell to $X_{(i-1)}$.

Note that this definition requires that $X_0$ be a 0-cell.
\noindent If $X$ is a CW complex, we refer to any sequence of spaces as
in (\ref{decomp}) as a {\it CW decomposition of $X$}. Suppose that in the
CW decomposition (\ref{decomp}), of the $n+1$ cells that are attached,
exactly $c_d$ are $d$-cells. Then we say that the CW complex $X$ 
has a CW decomposition consisting of $c_d$ $d$-cells for every $d$.

We note that a (closed) $d$-simplex is a $d$-cell.
Thus a finite simplicial complex is a CW complex, and has a CW 
decomposition in which the cells are precisely the closed simplices.

In Figure~\ref{torus} we demonstrate a CW decomposition of 
a 2-dimensional torus
which, beginning with the 0-cell, requires attaching two 1-cells and
then one 2-cell. Here we can see one of the most compelling reasons for 
considering CW complexes rather than just simplicial complexes.  Every
simplicial decomposition of the 2-torus has at least 7 vertices, 21
edges and 14 triangles. 

\begin{fig}
\lfigure{user2.pdf}{A CW decomposition of a 2-torus}{0.9}
\label{torus}
\end{fig}


It may seem that quite a bit has been lost in the transition from
simplicial complexes to general CW complexes.  After all, a simplicial
complex is completely described by a finite amount of combinatorial
data.  On the other hand, the construction of a CW decomposition
requires the choice of a number of continuous maps. However, if one is
only concerned with the homotopy type of the resulting CW complex,
then things begin to look a bit more manageable. Namely, the homotopy
type of $X \cup_f \s$ depends only on the homotopy type of $X$ and the 
homotopy class of $f$.

\begin{thm} Let $h: X \to X'$ denote a homotopy equivalence, $\s$ a cell,
and $f_1: \overdot{\s} \to X$, $f_2: \overdot{\s} \to X'$ two
continuous maps.  If $h \circ f_1$ is homotopic to $f_2$,
then $X\cup_{f_1} \s$ and $X'\cup_{f_2} \s$ are homotopy
equivalent.
\label{he}
\end{thm}

\noindent An important special case is when $h$ is the identity map.
We state this case separately for future reference.

\begin{cor} Let $X$ be a topological space, $\s$ a cell, and
$f_1,f_2:\overdot{\s} \to X$ two continuous maps. If $f_1$ and $f_2$
are homotopic, then $X\cup_{f_1} \s$ and $X\cup_{f_2} \s$ are homotopy
equivalent.
\label{hecor}
\end{cor}

\noindent (See Theorem~2.3 on page 120 of \cite{LW}.)
Therefore, the homotopy type of a CW complex is determined by the
homotopy classes of the attaching maps.  Since homotopy classes are
discrete objects, we have now recaptured a bit of the combinatorial
atmosphere that we seemingly lost when generalizing from simplicial 
complexes to CW complexes.  

Let us now present some examples.

1) Suppose $X$ is a topological space which has a CW decomposition
consisting of exactly one 0-cell and one $d$-cell. Then $X$ has a CW
decomposition $\emptyset \subset X_0 \subset X_1 = X$. 
The space $X_0$ must be the 0-cell, and $X=X_1$ is the result  
of attaching the $d$-cell to $X_0$. Since $X_0$ consists of a single
point, the only possible attaching map is the constant map. 
Thus $X$ is constructed from taking a closed $d$-ball and identifying
all of the points on its boundary. One can easily see that this
implies that the resulting space is a 
$d$-sphere.

2) Suppose $X$ is a topological space which has a CW decomposition
consisting of exactly one 0-cell and $n$ $d$-cells.
Then $X$ has a CW decomposition as in (\ref{decomp}) such that $X_0$ is
the 0-cell, and for each $i=1,2,\dots, n$ the space $X_i$ is the result of
attaching a $d$-cell to $X_{(i-1)}$. From the previous example,
we know that $X_1$ is a $d$-sphere. The space $X_2$ is constructed by
attaching a $d$-cell to $X_1$. The attaching map is a continuous map
from a $(d-1)$-sphere to $X_1$. Every map of the
$(d-1)$-sphere into $X_1$ is homotopic to a constant map
(since $\pi_{(d-1)}(X_1) \cong\pi_{(d-1)}(S^d) \cong 0$).
If the attaching map is actually a constant map,
then it is easy to see that the space $X_2$ is the wedge of two
$d$-spheres, denoted by $S^d \wedge S^d$. (The wedge of a collection
of topological spaces is the space resulting from choosing a point in
each space, taking the disjoint union of the spaces, and identifying
all of the chosen points.)  Since the attaching map must be homotopic
to a constant map, Corollary~\ref{hecor} implies 
that $X_2$ is homotopy equivalent to a
wedge of two $d$-spheres.

When constructing $X_3$ by attaching a $d$-cell to $X_2$, the relevant 
information is a map from $S^{d-1}$ to $X_2$, and the homotopy type of 
the resulting space is determined by the homotopy class of this map.
All such maps are homotopic to a constant map (since $\pi_{d-1}(X_2) \cong 
\pi_{d-1}(S^d \wedge S^d) \cong 0) $. Since $X_2$ is homotopy
equivalent
to a wedge of two $d$-spheres, and the attaching map is homotopic to
a constant map, it follows from Theorem~\ref{he} that $X_3$ is
homotopy equivalent to the space that would result from attaching a
$d$-cell
to $S^d \wedge S^d$ via a constant map, 
i.e., $X_3$ is homotopy equivalent 
to a wedge of three $d$-spheres.

Continuing in this fashion, we can see that $X$
must be homotopy equivalent to a wedge of $n$ $d$-spheres.    

The reader should not get the impression that the homotopy type of
a CW complex is determined by the number of cells of each dimension.
This is true only for very few spaces 
(and the reader might enjoy coming up with
some other examples).  The fact that wedges of spheres can, in fact, 
be identified by this numerical data partly explains why the 
main theorem of many papers in
combinatorial topology is that a certain simplicial complex is homotopy
equivalent to a wedge of spheres. Namely such complexes are the easiest
to recognize.  However, that does not explain why so many simplicial 
complexes that arise in
combinatorics are homotopy equivalent to a wedge of spheres.
I have often wondered if perhaps there is some deeper explanation for this.


3) Suppose that $X$ is a CW complex which has a CW decomposition
consisting of exactly one 0-cell, one 1-cell and one 2-cell. 
Let us consider a CW decomposition for $X$ with these cells: $\emptyset \subset X_0
\subset X_1 \subset X_2 = X.$ We know that $X_0$ is the
0-cell. Suppose that $X_1$ is the result of attaching the 1-cell to
$X_0$. Then $X_1$ must be a circle, and $X_2$ arises from attaching a
2-cell to $X_1$. The attaching map is a map from the boundary of the
2-cell, i.e., a circle, to $X_1$ which is also a circle.  Up to
homotopy, such a map is determined by its winding number, which can be
taken to be a nonnegative integer. If the winding number is 0, then
without altering the homotopy type of $X$ we may assume that the
attaching map is a constant map, which yields that $X \sim S^1 \wedge
S^2$ (where $\sim$ denotes homotopy equivalence). If the winding number 
is 1 then without altering the homotopy type of $X$ we may assume that the
attaching map is a homeomorphism, in which case $X$ is a 2-dimensional
disc. If the winding number is 2, then without altering the homotopy
type 
of $X$ we may assume that the
attaching map is a standard degree 2 mapping (i.e., that wraps one
circle around the other twice, with no backtracking).  
The reader should convince him/herself that the result in this case
is that $X$ is the 2-dimensional projective space $\BP^2$. In fact, each
winding number results in a homotopically distinct space. These spaces can be
distinguished by their homology, since $H_1(X,\BZ)$  
for the space $X$ resulting
from an attaching map with winding number $n$ is isomorphic to
$\BZ / n \BZ$.

It seems that we are not quite done with this example, because we
assumed that the 1-cell was attached before the 2-cell, and we must
consider the alternative order, in which $X_1$ is the result of
attaching a 2-cell to $X_0$. In this case, $X_1$ is a 2-sphere, and
$X=X_2$ is the result of attaching a 1-cell to $X_1$. The attaching
map is a map of $S^0$ into $S^2$. Since $S^2$ is connected
(i.e., $\pi_0(S^2) = 0$) all such maps are homotopic to a constant
map. Taking the attaching map to be a constant map yields that $X=S^1
\wedge S^2$. Thus adding the cells in this order merely resulted in
fewer possibilities for the homotopy type of $X$.  This is a general
phenomenon.  Generalizing the argument we just presented, using the
fact
that $\pi_i(S^d)=0$ for $i<d$,  yields
the following statement.

\begin{thm} Let 
\begin{equation}
\emptyset \subset X_0 \subset X_2 \subset \dots
\subset X_n =X
\label{orig}
\end{equation}
be a CW decomposition of a finite CW complex $X$. Then
$X$ is homotopy equivalent to a finite CW decomposition with precisely
the same number of cells of each dimension as in (\ref{orig}), 
and with the cells
attached so that their dimensions form a nondecreasing sequence.  
\end{thm}

I first learned of simplicial complexes in an algebraic
topology course. They were introduced as a category of 
topological spaces for which it
was rather easy to define homology and cohomology, i.e.,
in terms the simplicial chain- and
cochain-complexes. One might be concerned that in the transition from
simplicial complexes to CW complexes we have lost this ability to
easily compute the homology. In fact, much of this computability
remains. Let $X$ be a CW complex with a fixed CW
decomposition. Suppose that in this decomposition $X$ is constructed
from exactly $c_d$ cells of dimension $d$ for each $d=0,1,2, \dots,
n=\dim (K)$,
and let $C_d(X,\BZ)$ denote the space $\BZ^{c_d}$ (more precisely,
$C_d(X,\BZ)$ denotes the free abelian group generated by the $d$-cells
of $X$, each endowed with an orientation). The following is one 
of the fundamental results in the theory
of CW complexes.
 
\begin{thm} There are boundary maps $\p_d:  C_d(X,\BZ) \to
C_{d-1}(X,\BZ)$,
for each $d$, so that 
$$
\p_{d-1} \circ \p_d = 0
$$
and such that the resulting differential complex
$$
0\lra C_n(X,\BZ)\overset{\p_n}\lra
C_{n-1}(X,\BZ)\overset{\p_{n-1}}\lra
\cdots\overset{\p_1}\lra
C_0(X,\BZ)\lra 0
$$
calculates the homology of $X$.  That is, if we define 
$$
H_d(C,\p) = \frac{\ker(\p_d)}{\im(\p_{d+1})}
$$
then for each $d$ 
$$
H_d(C,\p) \cong H_d(X,\BZ)
$$
where $H_d(X,\BZ)$ denotes the singular homology of $X$.
\label{hom}
\end{thm}

\noindent The actual definition of the boundary map $\p$ is slightly 
nontrivial
and we 
will not go into it here (see Ch.~V Sec.~2 of \cite{LW} for the details). 
At first it may seem that without knowing
this boundary map, there is little to be gained from Theorem~\ref{hom}.
In fact, much can be learned from just knowing of the existence
of such a boundary map.  For example, let us choose a coefficient
field $\BF$, and tensor everything with $\BF$ to get a differential
complex
$$
0\lra C_n(X,\BF)\overset{\p_n}\lra C_{n-1}(X,\BF)\overset{\p_{n-1}}\lra
\cdots\overset{\p_1}\lra
C_0(X,\BF)\lra 0
$$
which calculates $H_*(X,\BF)$, where now $C_d(X,\BF) \cong \BF^{c_d}$.  
{}From  basic linear algebra. we can deduce the following inequalities.

\begin{thm}Let $X$ be a CW complex with
a fixed CW decomposition with $c_d$ cells of dimension $d$ for each
$d$. Fix a coefficient field $\BF$ and let $b_*$ denote the Betti
numbers of $X$ with respect to $\BF$, i.e., $b_d = \dim(H_d(X,\BF))$.

\noindent (i) (The Weak Morse Inequalities) For each $d$ 
$$
c_d \ge b_d.
$$  

\noindent (ii) Let $\chi(X)$ denote the Euler characteristic of $X$, 
i.e.,
$$
\chi(X) = b_0 - b_1 + b_2 - \dots.
$$
then we also have 
$$
\chi(X)= c_0 - c_1 + c_2 -\dots .
$$
\label{wmi}
\end{thm}

As the name ``Weak Morse Inequalities'' implies, this
theorem can be strengthened.  The following inequalities, known as the
``Strong Morse Inequalities'' also
follow from standard linear algebra.

\begin{thm}[The Strong Morse Inequalities]  With all notation as in
Theorem~\ref{wmi}, for each $d=0,1,2,\dots$
$$
c_d - c_{d-1} + c_{d-2} - \dots  + (-1)^{d}c_0 \ge b_d - b_{d-1} +
b_{d-2} - \dots  + (-1)^{d}b_0.
$$
\label{smi}
\end{thm}

\noindent 
Comparing Strong Morse Inequalities for consecutive values of $d$, and
using the fact that $b_i=0$ for $i$ larger than the dimension
of $K$, 
yields Theorem~\ref{wmi}.

We mentioned earlier that a great benefit of 
passing from simplicial complexes
to the more general CW complexes is that one often can use many fewer
cells. Let us take another look at this phenomenon in light of the
Morse inequalities.  Consider the case where $X$ is a
two-dimensional torus, so that with respect to any coefficient field
$b_0=1,b_1=2,b_2=1$. From the weak Morse inequalities, 
we have that for any CW decomposition,
$$
c_0 \ge b_0 = 1
$$
$$
c_1 \ge b_1 = 2
$$
$$
c_2 \ge b_2 =1. 
$$
A simplicial decomposition is a special case of a CW decomposition, so
these inequalities are satisfied when $c_d$ denotes the number 
of $d$-simplices in
a fixed simplicial decomposition.
However, every simplicial decomposition has at least 7 0-simplices, 
21 1-simplices and 14 2-simplices, so these inequalities are
far from  equality. It is generally the case that for a simplicial
decomposition these inequalities are very far from optimal, and hence are
generally of little interest.
On the other hand, earlier we demonstrated a CW decomposition of the
two-torus with exactly one 0-cell, two 1-cells and one 2-cell. The
inequalities tell us, in particular, that one cannot build a 
two-torus using fewer
cells. 
 
\section{The Basics of Discrete Morse Theory}
\label{main}

The discussion in the previous section leads us to an important
question. Suppose one is given a finite simplicial complex $X$. Typically, we
can expect that $X$ has a CW decomposition with many fewer cells 
than in the original simplicial decomposition. How can one go
about finding such an ``efficient'' CW decomposition for $X$?  In this
section we present a technique, discrete Morse Theory, 
which can be useful in such an investigation. (We note that the ideas
we will describe can be applied with no modification at all to any
finite regular CW complex, and with only minor modifications to 
a general finite CW complex. However, for simplicity, in this paper
we will restrict
attention to simplicial complexes.)

We begin by recalling that a finite simplicial complex is a 
finite set of vertices
$V$, 
along with a set of
subsets $K$ of $V$. The set $K$ satisfies two main properties:

\noindent 1) $V \subseteq K$

\noindent 2) If $\a \in K$ and $\b \subseteq \a$ then $\b \in K$.

\noindent By a slight abuse of notation, we will refer to the
simplicial complex simply as $K$. The elements of $K$ are called
simplices. If $\a \in K$,
and $\a$ contains $p+1$ vertices, then we say that the dimension of $\a$
is $p$, and we will sometimes denote this by $\a^{(p)}$.  For
simplices $\a$ and $\b$ we will use the notation $\a < \b$ or $\b > \a$
to indicate that $\a$ is a proper subset of $\b$ (thinking of $\a$ and $\b$
as subsets of $V$), and say that {\it $\a$ is a face of $\b$}.
We emphasize that at this point we will not be placing 
any restrictions
on the finite simplicial complexes under investigation.
In particular, the complexes need not be manifolds (even
though many of our examples will be).  In Section~9 we
will briefly indicate how some of our conclusions can 
be strengthened in the case that the complexes are assumed
to have additional structure.

A discrete Morse function
on $K$ is a function which, roughly speaking, assigns higher numbers
to higher dimensional simplices, with at most one exception, locally,
at each simplex. More precisely,

\begin{dfn} A function
$$
f: K\lra\BR
$$
is a discrete Morse function if for every $\a^{(p)}\in K$
$$
(1) \;\;\; \#\{\beta^{(p+1)}>\a\mid f(\beta)\le f(\a)\}\le 1, 
$$
and
$$
(2) \;\;\; \#\{\gamma^{(p-1)}<\a\mid f(\gamma)\ge f(\a)\}\le1.
$$
\end{dfn}

A simple example will serve to illustrate the definition.  Consider
the two complexes shown in Figure~\ref{circle}.  Here we indicate 
functions by
writing next to each simplex the value of the function on that
simplex. The function (i) is not a discrete
Morse function as the edge $f^{-1}(0)$ violates rule (2), since it has 2
lower dimensional ``neighbors'' on which $f$ takes on higher values,  and the
vertex $f^{-1}(5)$ violates rule (1), since it has 2 higher
dimensional ``neighbors'' on which $f$ takes on lower values. 
The function (ii) is a Morse function.  Note that a discrete Morse
function is not a continuous function on $K$.  Rather, it is an
assignment of a single number to each simplex.

\begin{fig}
\lfigure{user11.pdf}{(i). This is {\em not} a discrete Morse
function. (ii). This is a discrete Morse function.}{0.7}
\label{circle}
\end{fig}

The other main ingredient in Morse Theory is the notion of a critical point.
\begin{dfn} A simplex $\a^{(p)}$ is critical 
if
$$
(1) \;\;\;\#\{\beta^{(p+1)}>\a\mid f(\beta)\le f(\a)\}=0, 
$$
and
$$
(2)\;\;\;\#\{\gamma^{(p-1)}<\a\mid f(\gamma)\ge f(\a)\}=0.
$$
\end{dfn}

\noindent For example, 
Figure~\ref{circle}(ii), the vertex $f^{-1}(0)$ and 
the edge $f^{-1}(5)$ are critical, and there are no other
critical simplices.

We mention for later use that it follows from the axioms that 
a simplex cannot simultaneously fail both conditions in the 
test for criticality.

\begin{lem}  If $K$ is a simplicial complex with a Morse function $f$,
then for any simplex $\a$, either
$$
(1) \;\;\;\#\{\beta^{(p+1)}>\a\mid f(\beta)\le f(\a)\}=0, 
$$
or
$$
(2)\;\;\;\#\{\gamma^{(p-1)}<\a\mid f(\gamma)\ge f(\a)\}=0.
$$
\label{and}
\end{lem}

\noindent (See Lemma 2.5 of \cite{F2}.)
This lemma will play a crucial role in Section~\ref{gradient}. 

We can now state the main theorem of discrete Morse Theory.
 
\begin{thm} Suppose $K$ is a simplicial complex with a
discrete Morse function. Then $K$ is homotopy equivalent to a CW
complex with exactly one cell of dimension~$p$ for each critical
simplex of dimension~$p$.
\label{morse}
\end{thm}


Rather than present a proof of this theorem, we will content ourselves
here with a brief discussion of the main ideas.  
A discrete Morse function gives us a way to build the
simplicial complex by attaching the simplices in the order prescribed
by the function, i.e., adding first the simplices which are
assigned the smallest values.  More precisely, for any simplicial
complex $K$ with a discrete Morse function $f$, and any real number
$c$, define the level subcomplex $K(c)$ by
$$
K(c) = \cup_{f(\a) \le c} \cup_{\b \le \a} \b.
$$
That is, $K(c)$ is the subcomplex 
consisting of all simplices $\a$ of $K$ such that $f(\a)\le c$ along
with all of their faces.

Theorem~\ref{morse} follows from two basic lemmas.

\begin{lem} If there are no critical simplices $\a$ with $f(\a) \in
(a,b]$, then $K(b)$ is homotopy equivalent to $K(a)$. (In fact, $K(b)$
collapses to $K(a)$ --- this will be explained later.)
\label{coll}
\end{lem}

\begin{lem} If there is a single critical simplex $\a$ with $f(\a) \in 
(a,b]$ then there is a map $F: S^{(d-1)} \to K(a)$, where $d$ is the
dimension of $\a$, such that $K(b)$ is homotopy equivalent to 
$K(a) \cup_F B^d$. 
\label{critical}
\end{lem}


In Figure~\ref{sub} we illustrate all of the level subcomplexes in the
case 
that $K$ is the circle triangulated with 3 edges and 3 vertices, and
$f$ is  
the
Morse function shown in Figure~\ref{circle} (ii).  Here we can see why
these lemmas are true.  


\begin{fig}
\lfigure{user4.pdf}{The level subcomplexes of the discrete
Morse function shown in Figure~\ref{circle}(ii)}{0.9}
\label{sub}
\end{fig}

Let us begin with Lemma~\ref{coll}.
Consider the transition from $K(0)$ to $K(1)$. 
We have not added any critical simplices, and, just as the lemma 
predicts, $K(0)$ and $K(1)$ are homotopy equivalent.
Let us try to understand why the homotopy type did not change.
To construct $K(1)$ from $K(0)$, we first have to add the edge $f^{-1}(1)$.
This edge is not critical  because it has a codimension-one face which 
is assigned a higher value, namely the vertex $f^{-1}(2)$. In order to have
$K(1)$ be a subcomplex, we must also add this vertex. Thus we see that
the edge $f^{-1}(1)$
in $K(1)$ has a {\it free face}, i.e., a face which is not the face of any
other 
simplex in $K(1)$.  We can deformation retract $K(1)$ to $K(0)$ by ``pushing in"
the edge $f^{-1}(1)$ starting at the vertex $f^{-1}(2)$.

This is a very general phenomenon.  That is,
it follows from the axioms for a discrete Morse function that for
any simplicial complex with any discrete Morse function, when passing from
one level subcomplex to the next the noncritical simplices are added
in pairs, each
of which consists of a simplex and a free face.  Suppose that  
$K_2 \subset K_1$
are simplicial complexes, and $K_1$ has exactly two simplices $\a$ and $\b$
that are not in $K_2$, where $\b$ is a free face of $\a$. Then it is easy 
to see that $K_2$ is a deformation retract of $K_1$, and hence $K_1$
and $K_2$ are
homotopy equivalent (see Figure~\ref{collapse}). This special sort of 
combinatorial deformation retract
is called a {\it simplicial collapse}. If one can transform a
simplicial complex $K_1$ 
into a subcomplex $K_2$ by simplicial collapses, then we say that 
{\it $K_1$ collapses to $K_2$}, and we indicate this by $K_1
\searrow K_2$.
Figure~\ref{simplex} 
shows a 2-dimensional simplex collapsing to one of its vertices.


\begin{fig}
\lfigure{user9.pdf}{A simplicial collapse.}{0.8}
\label{collapse}
\end{fig}


\begin{fig}
\lfigure{user10.pdf}{A 2-simplex collapsing to a vertex.}{0.7}
\label{simplex}
\end{fig}

The process of simplicial collapse was studied by J.H.C. Whitehead, 
and he defined {\it simple homotopy equivalence} to be the 
equivalence relation 
generated by simplicial collapse. This
indicates
that discrete Morse Theory may be particularly useful when working
in the category of simple homotopy equivalence.


Now let us turn to Lemma~\ref{critical} and 
investigate what happens when one adds a critical simplex,
for example when  making the transition from $K(4)$ to $K(5)$. In this case we
are adding a critical edge. We can see clearly from the illustration that
we pass from $K(4)$ to $K(5)$ by attaching a 1-cell,
just as predicted by Lemma~\ref{critical}.  To see why this works in
general,
consider a critical $d$-simplex $\a$.
It follows from the definition of a critical simplex that each face 
of $\a$ is assigned a smaller value than $\a$, which 
implies in turn that each face of $\a$  appears in a previous
level subcomplex.  Thus the entire boundary of $\a$ appears in an
earlier level subcomplex, so that when it comes time to add $\a$, we
must ``glue it in"
along its entire boundary. This is precisely the process of attaching 
a $d$-cell. 

This completes our discussion of the proof. 

Perhaps this is a good
time to point out that one can define a discrete Morse
function on any simplicial complex. 
Namely, one can simply let $f(\a) = \dim(\a)$ for each
simplex $\a$.  In this case, every simplex is critical, and Theorem
\ref{morse} is a rather uninteresting tautology.  However, as we will
see in examples, one can often construct discrete Morse functions with
many fewer critical simplices.


Let $K$ be a simplicial
complex with a discrete Morse function. Let $m_p$ denote the number of
critical simplices of dimension $p$.  Let $\BF$ be any field, and 
$b_p=\dim  H_p(K,\BF)$ the $p^{th}$ Betti number with
respect to $\BF$.  Combining Theorems \ref{morse}, \ref{wmi} and \ref{smi}, 
and the fact that homotopy equivalent spaces have isomorphic homology, 
we have the following inequalities.

\begin{thm} {\bf I. The Weak Morse Inequalities.} 

\noindent (i)For each $p=0,1,2,\dots,n$ (where $n$ is the dimension of
$K$)
$$
m_p \ge  b_p.
$$

\noindent (ii) $m_0 -m_1 +m_2 - \dots + (-1)^n m_n =
b_0-b_1+b_2 - \dots + (-1)^n b_n \;\;[= \chi (K)].$
\label{mi}
\smallskip 

\noindent {\bf II. The Strong Morse Inequalities.}

\noindent For each $p=0,1,2,\dots,n, n+1$,
$$
m_p-m_{p-1} + \dots +(-1)^p m_0 \ge b_p -b_{p-1}  + \dots +(-1)^p b_0.
$$
\end{thm}

\section{Gradient Vector Fields}
\label{gradient}

Any ambitious reader who has already started trying some examples
will have noticed that the theory as presented in the previous section
can be a bit unwieldy.  After all, how is one to go about assigning
numbers to each of the simplices of a simplicial complex so that they satisfy
the axioms of a discrete Morse function?  Fortunately, in practice one need not
actually find a discrete Morse function.  Finding the gradient vector
field of the Morse function is sufficient.  
This requires a bit of explanation.  

Let us now return to the example in Figure~\ref{circle}(ii). Noncritical 
simplices occur in pairs. For example, the edge $f^{-1}(1)$ is 
not critical because it has a ``lower dimensional neighbor" which 
is assigned a higher value, i.e., the vertex $f^{-1}(2)$. Similarly,
the vertex $f^{-1}(2)$ is not critical because it has a 
``higher dimensional neighbor" which is assigned a lower value, 
i.e., the edge $f^{-1}(1)$. We indicate this pairing by drawing
an arrow from the vertex $f^{-1}(2)$, pointing into
the edge $f^{-1}(1)$. Similarly, we draw an arrow from the vertex $f^{-1}(4)$
pointing into the edge $f^{-1}(3)$. (See Figure~\ref{gvf}.)  
One can think of 
these arrows as pictorially indicating the simplicial collapse that is 
referred to in the proof of Lemma~\ref{coll}.

\begin{fig}
\lfigure{user14.pdf}{The gradient vector field
of the Morse function shown in Figure~\ref{circle} (ii).}{0.3}
\label{gvf}
\end{fig}


We can apply this process to any simplicial complex with a discrete Morse 
function.
The arrows are drawn as follows.
Suppose $\a^{(p)}$ is a non-critical simplex with $\beta^{(p+1)}>\a$
satisfying $f(\beta)\le f(\a)$. We then draw an arrow from $\a$ to
$\beta$.  Figure~\ref{example} illustrates a more complicated example.
Note that the discrete Morse function drawn in this figure has one
critical
vertex, $f^{-1}(0)$, and one critical edge, $f^{-1}(11)$. 
Theorem
\ref{morse} implies this simplicial complex is homotopy equivalent
to a CW complex with exactly one 0-cell and one 1-cell, i.e., a circle.

It follows from Lemma~\ref{and} that that every simplex $\a$ satisfies 
exactly one of the following:

\noindent (i)  $\a$ is the tail of exactly one arrow.

\noindent (ii) $\a$ is the head of exactly one arrow.

 
\noindent (iii) $\a$ is neither the head nor the tail of an arrow.
 
\noindent Note that a simplex is 
critical if and only if it is neither the tail nor the head of any
arrow. These arrows can be viewed as the discrete analogue of the
gradient vector field of the Morse function. (To be precise, when we
say ``gradient vector field'' we are really referring to the negative
of the gradient vector field.)

\begin{fig}
\lfigure{user5.pdf}{Another example of a gradient 
vector field}{0.9}
\label{example}
\end{fig}
 
As we will see in examples later, these arrows are much easier to work
with than the original discrete Morse function.  In fact, this
gradient vector field contains all of the information that we will need
to know about the function for most applications.  
The upshot is that if one is given a
simplicial complex and one wishes to apply the theory of
the previous section, one need not find a discrete Morse
function. One ``only'' needs to find a gradient vector field. 

This leads us to the following question.  Suppose we attach arrows to
the simplices so that each simplex satisfies exactly one of properties
(i),(ii),(iii) above. Then how do we know if that set of arrows 
is the gradient vector field of a discrete Morse function? This is the
question we will answer in the remainder of this section.

Let $K$ be a simplicial complex with a discrete Morse function $f$. 
Then rather than thinking about the discrete gradient vector field $V$
of $f$ as a collection of arrows, we may equivalently
 describe $V$ as a
collection of pairs $\{ \a^{(p)} <\b^{(p+1)} \}$
of simplices of $K$, where $\{ \a^{(p)} <\b^{(p+1)} \}$ is in $V$ if
and only if $f(\b) \le f(\a)$.  In other words, 
$\{ \a^{(p)} <\b^{(p+1)} \}$ is in $V$ if
and only if we have drawn an arrow that has $\a$ as its tail, and $\b$
as its head. The properties of a discrete Morse function imply that
each simplex is in at most one pair of $V$.  This leads us to the
following definition.

\begin{dfn} A discrete vector field $V$ on $K$ is a collection of pairs
$\{ \a^{(p)} <\b^{(p+1)} \}$
of simplices of $K$ such that each simplex is in at most one pair of
$V$.
\end{dfn}

Such pairings were studied in
\cite{Sta} and \cite{Du} as a tool for investigating the possible
$f$-vectors for a simplicial complex. Here we take a different point of
view. If one has a smooth vector field on a smooth manifold, it is
quite
natural to study the dynamical system induced by flowing along the vector
field. One can begin the same sort of study for any discrete vector
field. In \cite{F4} we present a study of the dynamics
associated to a discrete vector field.  Here, we present just enough
to continue our discussion of discrete Morse Theory.

Given a discrete vector field
$V$ on a simplicial complex $K$, a $V-$path is a sequence of simplices
\begin{equation}
\a_0^{(p)}, \beta_0^{(p+1)}, \a_1^{(p)}, \beta_1^{(p+1)},
\a_2^{(p)},\dots ,\beta_r^{(p+1)}, \a_{r+1}^{(p)}
\label{path}
\end{equation}
such that for each $i=0,\dots r$, $\{\a<\b\} \in V$ and
$\beta_i>\a_{i+1} \ne \a_i$. We say such a path is a {\it non-trivial
closed path} 
if $r \ge 0$ and $\a_0 =\a_{r+1}$. If $V$ is the gradient vector field
of a discrete Morse function $f$, then we sometimes refer to a $V$-path as
a {\it gradient path of $f$}.

One idea behind this definition is the following result.

\begin{thm} Suppose $V$ is the gradient vector field of a discrete
Morse function $f$. Then a sequence of simplices as in (\ref{path})
is a $V$-path if and only if $\a_i < \b_i >  \a_{i+1}$ for each $i =
0,1,\dots,r$, and
$$
f(\a_0) \ge f(\b_0) > f(\a_1) \ge f(\b_1) > \dots \ge
f(\beta_r)>f(\a_{r+1}).
$$
\end{thm}

\noindent That is, the gradient paths of $f$ are precisely those
``continuous'' sequences of simplices along which $f$ is decreasing.
In particular, this theorem implies that if $V$ is a gradient vector field,
then there are no nontrivial closed $V$-paths. In fact, the main
result of this section is that the converse is true.

\begin{thm} A discrete vector field $V$ is the gradient
vector field of a discrete Morse function if and only if there are
no non-trivial closed $V$-paths.
\label{grad}
\end{thm}

We will not prove this theorem here. 
However, many readers may notice the similarity with the
following standard theorem from the subject of directed graphs.

\begin{thm} Let $G$ be a directed graph.  Then there is a real-valued
function of the vertices that is strictly decreasing along each
directed path if and only if there are no directed loops.
\label{dir}
\end{thm}

We will show in Section~\ref{comb} that, in fact, Theorem~\ref{dir} implies
Theorem~\ref{grad}.
The power of Theorem~\ref{grad} is indicated in the next two sections
in which we construct some discrete vector fields and use Theorem
\ref{grad}
to verify that they are gradient vector fields.

\section{Our First Example: The Real Projective Plane}
\label{rp2}

Figure~\ref{proj} (i) shows a triangulation of the real 
projective plane $\BP^2$.  
Note that the vertices along the boundary with the same labels are to be
identified, as are the edges whose endpoints have the same labels.
In Figure~5(ii) we illustrate a discrete vector field $V$ on this simplicial
complex. One can easily see that there are no closed $V$-paths
(since all $V$-paths go to the boundary of the figure and there are no
closed $V$-paths on the boundary), and hence is a gradient vector field.
The only simplices which are neither the head nor the tail of an arrow are
the vertex labelled 1, the edge $e$, and the triangle $t$. Thus, 
by Theorem~\ref{morse},  the projective plane is homotopy equivalent 
to a CW complex with exactly 
one 0-cell, one 1-cell and one 2-cell.  (Of course, we already knew
this from our discussion of
Example~3 in Section~2.)


\begin{fig}
\lfigure{user6.pdf}{(i) A triangulation of the real projective
 plane. (ii) A discrete gradient vector field on $\BP^2$.}{0.8}
\label{proj}
\end{fig}
 

This example gives rise to two potential concerns.  The first is that from
the main theorem we learn only a statement about  ``homotopy equivalence".
This is sufficient if one is only interested in calculating homology
or 
homotopy groups.
However, one might be interested in determining the (PL-)homeomorphism
type 
of the
complex.  This is possible, in some cases, using deep results of
J.H.C. 
Whitehead. We
revisit this topic in Section~\ref{sphere}.

The second potential point of concern is that as we saw in Section~2 
there are an 
infinite number of different homotopy types of CW complexes
which can be built from exactly one 0-cell, 
one 1-cell and one 2-cell. One might wonder if Morse
Theory can give us any additional information as to 
how the cells are attached.  In fact, one can deduce much of this information
if one has enough information about the gradient paths
of the Morse function. This point is discussed further in Section
\ref{complex}, where
we will return to this example of the triangulated projective plane.

\section{Our Second Example: The Complex of Not Connected Graphs}
\label{nconn}

A number of fascinating simplicial complexes arise from the study 
of monotone graph properties.  Let $K_n$ denote the complete graph
on $n$ vertices, and suppose we have labelled the vertices 1,2,\dots,$n$.
Let $\SG_n$ denote the spanning subgraphs of $K_n$, that is, the
subgraphs of 
$K_n$ 
that contain all $n$ vertices.  A subset $\SP \subset \SG_n$ is called a
{\it graph property} of graphs with $n$ vertices if inclusion in $\SP$
only 
depends 
on the isomorphism type of the graph.  That is, $\SP$ is a graph
property if 
for all 
pairs of graphs $G_1,G_2 \in \SG_n$, if $G_1$ and $G_2$ are isomorphic 
(ignoring the labellings on the vertices) then $G_1 \in \SP$ if and only if  
$G_2 \in \SP$.  A graph property $\SP$ of graphs with $n$ vertices is 
said to be {\it monotone decreasing} if for any graphs 
$G_1 \subset G_2 \in \SG_n$, if $G_2 \in \SP$ then $G_1 \in \SP$.

Monotone decreasing properties abound in the study of graph theory.
Here are some typical examples: graphs having no more than $k$ edges 
(for any fixed $k$),  graphs such that the degree of every vertex is
less that $\delta$ (for any fixed $\delta$), 
graphs which are not connected, graphs which are not $i$-connected
(for any fixed $i$), graphs which do not have a Hamiltonian cycle, 
graphs which do not 
contain a minor isomorphic to $H$ (for any fixed graph $H$), graphs 
which are $r$-colorable 
(for any fixed $r$), and bipartite graphs.

Any monotone decreasing graph property $\SP$ gives rise to a simplicial 
complex $\SK$ where the $d$-simplices of $\SK$ are the graphs $G \in \SP$ 
which have $d+1$ edges. In particular, if $G$ is a $d$-simplex in
$\SK$, 
then the
faces of $G$ are all of the nontrivial spanning subgraphs of $G$ (the
monotonicity of 
$\SP$
implies that each of these graphs is in $\SK$). Said in another way, if
$\SP$ 
is nonempty,
then the vertices of $\SK$ are the edges of $K_n$, and a collection of 
vertices in $\SK$ 
span a simplex if the spanning subgraph of $K_n$ consisting of  all
edges 
which 
correspond to these vertices lies in $\SP$.

The simplicial complexes induced by many of the above-mentioned
monotone 
decreasing 
graph properties have been studied using the techniques of this paper.
See for example \cite{C}, \cite{D}, \cite{J1}, \cite{J2}, \cite{LS}, \cite{S}. 
These papers contain some beautiful
mathematics
in which the authors construct, ``by hand", explicit discrete gradient 
vector fields, along the way illuminating some of the intricate finer 
structures
of the graph properties.

Some monotone graph properties have recently been the focus of
intense interest because of their relation to knot theory.
Unfortunately this is probably not a good time for an
in depth discussion of this fascinating topic.  We will 
mention only that
Vassiliev has shown how one can derive ``finite type knot 
invariants" from the study of the space of ``singular knots'' (i.e.,
maps from $S^1$ to $\BR^3$ which are not embeddings).
The homology of 
the simplicial complexes of not connected and not 
2-connected graphs show up in his spectral sequence calculation
of the homology of this space.  
This is explained in \cite{Va}, where
Vassiliev derives the homotopy type of the complex of not 
connected graphs.   In \cite{Tu} and \cite{BBLSW}, the topology
of the space of not 2-connected graphs is determined, with discrete
Morse Theory playing a minor role in the latter reference.
This topic is reexamined in \cite{S}, in which the entire 
investigation is framed in the language of discrete Morse Theory.
Discrete Morse Theory is used to determine the
topology of not 3-connected graphs in \cite{J1}.


In this section, we will provide an
introduction to this work by taking
a look at the simpler case of the complex of not connected
graphs.
We will show how the ideas of this paper may be used to determine 
the topology of $\SN_n$, the simplicial complex of not connected graphs 
on $n$ vertices. Let me begin by pointing out that this complex can be 
well studied 
by more classical methods, and the answer has also been found by Vassiliev in
\cite{Va}.  The only novelty of this section is our use of discrete Morse
Theory.  

Our goal is to construct a discrete gradient vector field $V$ on
$\SN_n$, 
the simplicial 
complex of all not-connected graphs with the vertex set 
$\{1,2,3,\dots,n\}$. 
The construction will be in steps.  Let $V_{12}$ denote the 
discrete vector field
consisting of all pairs $\{ G, G+(1,2) \}$, where $G$ is any graph in  $\SN_n$
which does not contain the edge $(1,2)$ and such that $G+(1,2)\in \SN_n$.
Another way of describing $V_{12}$ is that if 
$G$ is any graph in $\SN_n$ which 
contains the edge $(1,2)$, then $G-(1,2)$ and $G$ are paired in
$V_{12}$. Actually, there is one exception to this rule. Let $G^*$
denote
the graph consisting of only the single edge (1,2). Then $G^*-(1,2)$ is the
empty graph, which corresponds to the empty simplex in $\SN_n$, and 
may not be paired in a discrete vector field.  Thus, $G^*$ is
unpaired in $V_{12}$.

The graphs in $\SN_n$ other than $G^*$
which are unpaired in $V_{12}$ are those that do
not contain the
edge $(1,2)$ and have the property that $G+(1,2) \not\in \SN_n$. 
That is, those
disconnected graphs $G$ with the property that $G+(1,2)$ is connected.
Such a graph must have exactly two connected components, one of which 
contains the vertex labelled 1, and one which contains the vertex labelled 2.
We denote these connected components by $G_1$ and $G_2$, resp. See
Figure~\ref{12}. 

\begin{fig}
\lfigure{user7.pdf}{The graphs other than $G^*$ 
which are unpaired
in the vector field $V_{12}$.}{0.7}
\label{12}
\end{fig}

Let $G$ be a graph other than $G^*$ 
which is unpaired in $V_{12}$, and consider vertex 3. 
This vertex must either be in $G_1$ or $G_2$. Suppose that vertex 3 is
in 
$G_1$.
If $G$ does not contain the edge $(1,3)$ then $G+(1,3)$ is also
unpaired in $V_{12}$,  so we can
pair $G$ with $G+(1,3)$.  If  vertex 3 is in $G_1$, then the graph $G$ 
is still
unpaired if and only if $G$ contains the edge (1,3) and $G-(1,3)$ is 
the union of three connected components, one containing vertex 1, 
one containing
vertex 2, and one containing vertex 3.

Similarly, if vertex 3 is in $G_2$ and $G$ does not
contain the edge $(2,3)$, then pair $G$ with $G+(2,3)$. 
Let $V_3$ denote the resulting discrete vector field. 

The unpaired graphs in $V_3$ are $G^*$ and those that either 
contain
the edge (1,3) and have the property that $G-(1,3)$ is 
the union of three connected components, one containing vertex 1,
one containing vertex 2, and one containing vertex 3,
or contain the edge (2,3) and have the property that
$G-(2,3)$ is 
the union of three connected components, 
one containing vertex 1, one containing
vertex 2, and one containing vertex 3. 
We illustrate these graphs in Figure~\ref{3}. The circles in this
figure
indicate connected graphs.


\begin{fig}
\lfigure{user12.pdf}{The graphs other than $G^*$
which are unpaired
in the vector field $V_{3}$.}
{1.0}
\label{3}
\end{fig}

Now consider the location of the vertex labelled 4, 
and pair any graph $G$ which is unpaired in $V_3$ 
with $G+(1,4)$, $G+(2,4)$, or $G+(3,4)$ if possible (at most one of
these graphs is unpaired in $V_3$).  Call the resulting
discrete vector field $V_4$. We continue in this fashion, considering
in turn the vertices labelled
$5,6,\dots,n$.  Let $V_i$ denote the discrete vector field that has been 
constructed after the consideration of vertex $i$, and $V=V_n$ the 
final discrete vector field.
When we are done the only unpaired graphs in $V$ will be $G^*$ and 
those graphs that 
are the union
of two connected trees, one containing the vertex 1 and one containing
the vertex 2. In addition, both trees have the property that 
the vertex labels are increasing
along every ray starting from the vertex 1 or the vertex 2.  
There are precisely $(n-1)!$ 
such graphs,  and they each have $n-2$ edges, and 
hence correspond to an $(n-3)$-simplex in 
$\SN_n$.

It remains to see that the discrete vector field $V$ is 
a gradient vector field, i.e., that there are no closed $V$-paths.
We first check that $V_{12}$ is a gradient vector field. 
Let $\g = \a_0^{(p)},\b_0^{(p+1)},\a_1^{(p)}$ denote a 
$V_{12}$-path.  Then $\a_0$ must be the ``tail of an arrow", i.e., the smaller
graph of some pair in $V_{12}$, with $\b_0$ being the head of the arrow, i.e., 
$\b_0 = \a_0 + (1,2)$. The simplex $\a_1$ is a codimension-one face of $\b_0$ 
other than $\a_0$. Thus, $\a_1$ corresponds to a graph of the form 
$\a_0 +(1,2) -e$,
where $e$ is an edge of $\a_0$ other than (1,2).  
Since $\a_1$ contains the edge $(1,2)$ it is the 
``head of an arrow" in $V_{12}$, i.e., the larger graph of some pair in
$V_{12}$, which implies that $\g$ cannot be continued to a longer
$V_{12}$-path.
This certainly implies that there are no closed $V_{12}$-paths.

The same sort of argument  will work for $V$. Recall that 
$V$ is constructed
in stages, by first considering the edge (1,2) and then the vertices
3, 4, 5, \dots\ in order. 
Let $\g=\a_0,\b_0,\a_1$ denote a $V$-path. In particular,
$\a_0$ and $\b_0$ must be paired in $V$. The reader can check that 
if $\a_0$ and $\b_0$  are first paired in $V_i$, $i \ge 3$,
then either $\a_1$ is the head of an arrow in $V_i$, in which case
the $V$-path cannot be continued, or
$\a_1$ is paired in $V_{i-1}$.
It follows by induction that there can be no closed $V$-paths.

In summary, $V$ is a discrete gradient vector field on $\SN_n$ with
exactly one unpaired vertex, and $(n-1)!$ unpaired $(n-3)$-simplices. 
We can now apply Theorem~\ref{morse} to conclude
\begin{thm}[\cite{Va}] The complex $\SN_n$ of not 
connected graphs on $n$-vertices is 
homotopy  equivalent to the wedge of $(n-1)!$ spheres of dimension
$(n-3)$.
\end{thm}

\section{ A Combinatorial Point of View}
\label{comb}
The notion of a gradient vector field has a very nice 
purely combinatorial description due to
Chari \cite{C}, using
which we can recast the Morse Theory in an appealing form. We begin with the
Hasse diagram of $K$, that is, the partially ordered set of simplices
of $K$ ordered by the face relation. Consider the Hasse diagram as a
directed graph.  The vertices of the graph are in 1-1 correspondence
with the simplices of $K$, and there is a directed edge from $\beta$ to
$\a$ if and only if $\a$ is a codimension-one face of $\beta$. (See
Figure~\ref{has} (i).)  Now let
$V$ be a combinatorial vector field. We modify the directed graph as
follows. If $\{\a<\b\} \in V $ then reverse the orientation of the edge
between $\a$ and $\beta$, so that it now goes from $\a$ to $\beta$.
(See Figure~\ref{has}(ii).)
A $V$-path can be thought of as a directed path in this modified
graph.  There are some directed paths in this modified Hasse diagram 
which are not $V$-paths as we have defined them. However, the
following result is not hard to check.

\begin{fig}
\lfigure{user15.pdf}{From a discrete vector field to
a directed Hasse diagram.}{0.7}
\label{has}
\end{fig} 

\begin{thm} There are no nontrivial closed $V$-paths if and only
if there are no nontrivial closed directed paths in the corresponding
directed Hasse diagram.
\label{Hasse}
\end{thm}

Thus, in this combinatorial language, 
a discrete vector field is a
partial matching of the Hasse diagram, and a discrete vector field is
a gradient vector field if the partial matching is acyclic in the
above sense.  Note that using Theorem~\ref{Hasse}, we can see that
Theorem~\ref{grad} does follow from Theorem~\ref{dir}.

We can now restate some of our earlier theorems in this
language. There is a very minor complication in that one usually
includes the empty set as an element of the Hasse diagram (considered
as a simplex of dimension -1) while we have not considered the empty
set previously.  

\begin{thm} Let $V$ be an acyclic partial matching of the Hasse
diagram of $K$ (of the sort described above --- assume that
the empty set is not paired with another simplex). Let 
$u_p$ denote the number of unpaired $p$-simplices. Then $K$ is homotopy
equivalent to a CW-complex with exactly $u_p$ cells of dimension $p$,
for each $p\ge 0$.
\end{thm}


An important 
special case is when $V$ is a complete matching, 
that is,
every simplex (this time including the empty simplex) is paired with 
another simplex. In this case, Lemma~\ref{collapse} implies the
following result.

\begin{thm} Let $V$ be a complete acyclic matching of the Hasse
diagram of $K$, then $K$ collapses onto a vertex, so that, in
particular, $K$ is contractible.
\end{thm}

This result was used in a very interesting fashion in \cite{BBLSW}.


\section{The Morse Complex}
\label{complex}

In this section we will see how knowledge of 
the gradient paths of a discrete Morse function on a space $K$ can allow
one to strengthen the conclusions of the main theorems.
In particular, rather than just knowing the number of cells in 
a CW decomposition for $K$, one can calculate the homology exactly.

Let $K$ be a simplicial complex with a Morse function $f$.
Let $C_p(X,\BZ)$ denote the
space of $p$-simplicial chains, and $\SM_p\sbq C_p(X,\BZ)$ 
the span of the critical $p$-simplices. We refer to $\SM_*$ as the 
space of Morse chains.  If we let $m_p$ 
denote the 
number of critical $p$-simplices, then we obviously have
$$
\SM_p \cong \BZ^{m_p}.
$$
Since homotopy equivalent spaces have isomorphic homology,
the following theorem 
follows from Theorems \ref{morse} and \ref{hom}. 

\begin{thm}
There are boundary maps $\tl\p_d:  \SM_p \to
\SM_{d-1}$,
for each $d$, so that 
$$
\tl\p_{d-1} \circ \tl\p_d = 0
$$
and such that the resulting differential complex
\begin{equation}
0\lra \SM_n \overset{\tl\p_n}\lra \SM_{n-1}\overset{\tl\p_{n-1}}\lra
\cdots\overset{\tl\p_1}\lra
\SM_0\lra 0
\label{mc}
\end{equation}
calculates the homology of $X$.  That is, if we define 
$$
H_d(\SM,\tl\p) = \frac{\ker(\tl\p_d)}{\im(\tl\p_{d+1})}
$$
then for each $d$ 
$$
H_d(\SM,\tl\p) \cong H_d(X,\BZ).
$$
\end{thm}

In fact, this statement is equivalent to the Strong Morse
inequalities. The main goal of this section is to present 
an explicit formula for
the boundary operator $\tl\p$.
This requires a closer look at of the notion of a 
gradient path.  Let $\a$ and $\tl\a$ be $p$-simplices.
Recall from Section~7 that a {\it gradient path} from 
$\tl\a$ to $\a$ is a sequence of
simplices
$$
\tl\a=\a_0^{(p)}, \beta_0^{(p+1)}, \a_1^{(p)}, \beta_1^{(p+1)},
\a_2^{(p)},\dots ,\beta_r^{(p+1)}, \a_{r+1}^{(p)} = \a
$$
such that $\a_i < \b_i > \a_{i+1}$ for each $i=0,1,2,\dots,r$ and
$f(\a_0) \ge f(\b_0)>f(\a_1)\ge f(\b_1)>\dots\ge f(\b_r) > f(\a_{r+1})$.
Equivalently, if $V$ is the gradient vector field of $f$, we require 
that for each $i$, $\a_i$ and $\b_i$ be paired in $V$ and $\beta_i >
\a_{i+1} \ne \a_i$. In
Figure~\ref{gpath} we show a single gradient path from the boundary of a
critical 2-simplex $\beta$ to a critical edge $\a$, where the arrows
indicate the gradient vector field $V$.

Given a gradient path as shown in Figure~\ref{gpath}, an orientation on $\b$
induces an orientation on $\a$.  We will not state the precise
definition here.  The idea is that one ``slides'' the orientation from
$\b$ along the gradient path to $\a$. For example, for the gradient
path shown in Figure~\ref{gpath},
the  indicated orientation on $\b$ induces the indicated orientation on
$\a$. 

\begin{fig}
\lfigure{user8.pdf}{A gradient path from the boundary of
$\b$ to $\a$.}{0.7}
\label{gpath}
\end{fig}

We are now ready to state the desired formula. 
\begin{thm}
Choose an orientation for each simplex.  Then for any
critical $(p+1)$-simplex $\beta$ set 
\begin{equation}
\wt\p\beta\ = \sum\lm_{\text{critical}\,\,\a^{(p)}} 
c_{\a,\beta} \a
\label{dmc}
\end{equation}
where
$$
c_{\a,\beta} = 
\sum\lm_{\g\in\G(\b,\a)}m(\g)
$$
where $\G(\b,\a)$ is the set of gradient paths which go from
a maximal face of $\b$ to $\a$.  The multiplicity $m(\g)$ of any 
gradient path $\g$ is equal to $\pm1$, depending on 
whether, given $\g$, the orientation on $\beta$ induces the 
chosen orientation on
$\a$, or the opposite orientation.  With this differential, the
complex (\ref{mc}) computes the homology of $K$.
\label{mc2}
\end{thm}

\noindent A proof of this theorem appears in Section~8 of \cite{F2}.
We refer to the complex (\ref{mc}) with the differential (\ref{dmc})
as the Morse complex (it goes by many different names in the
literature).
An extensive study of the Morse complex in the 
smooth category appears in \cite{Sc}.

We end this section with a demonstration of how the ideas
of this section may be applied to the example of the
real projective plane $\BP^2$ as illustrated in Figure~\ref{proj}(ii).
We saw in Section~\ref{main} how discrete Morse Theory can help us see that
$\BP^2$ has a CW decomposition with exactly one 0-cell, one 1-cell and 
one 2-cell.  Here we will see how Morse Theory can distinguish between
the spaces which have such a CW decomposition.
In Figure~\ref{proj2} we redraw the gradient vector field,
and indicate a chosen orientation on the critical edge $e$
and the critical triangle $t$. Let us now calculate the boundary
map in the Morse complex.  To calculate $\tl\p (e)$, we must
count all of the gradient paths from the boundary of $e$ to $v$.
There are precisely two such paths.  Namely, following the unique
gradient path beginning at each endpoint of $e$ leads us to $v$.  
(The gradient path beginning at the head of $e$ is 
the trivial path of 0 steps.)  
Since the orientation of $e$ induces a $+$ orientation 
on the head of $e$,  and a $-$ orientation on the tail of $e$, 
adding these two paths with their corresponding signs
leads us to the formula that $\tl\p (e) = 0$.
It can be seen from the illustration that there are precisely two 
gradient paths from the boundary of $t$ to $e$, and, with the
illustrated orientation for $t$, both 
induce the chosen orientation on $e$, so that $\tl\p (t) = 2 e$.
Therefore the homology of the real projective plane can be calculated from 
the following differential complex.
$$
\BZ \overset{\times 2}\lra \BZ \overset{0}\lra \BZ \lra 0.
$$
Thus we see that 
$$
H_0 (\BP^2,\BZ) \cong \BZ, \;\;
H_1(\BP^2,\BZ)\cong \BZ/ 2 \BZ, \;\;
H_2 (\BP^2 ,\BZ) \cong 0.
$$

\begin{fig}
\lfigure{user13.pdf}{A gradient vector field on the real
projective plane.}{0.4}
\label{proj2}
\end{fig}

\section {Sphere Theorems}
\label{sphere}

As mentioned in our discussion at the end of Section~\ref{rp2}, 
one can sometimes 
use discrete Morse Theory to make statements about more than just the
homotopy type of the simplicial complex.  One can sometimes
classify the complex up to homeomorphism
or combinatorial equivalence.   This will be a very short section, 
as this topic seems a bit far from the
main thrust of this paper. In addition, some terms will unfortunately 
have to be defined only cursorily or not at all.   
So far, we have not placed any restrictions
on the simplicial complexes under consideration.
The main idea  of this section is that if our simplicial
complex has some additional structure, then one may be able to strengthen
the conclusion.
This idea rests on some very deep work of J.H.C. Whitehead \cite{Wh}. 

Recall that a simplicial complex $K$ 
is a {\it combinatorial $d$-ball} if $K$ and the standard $d$-simplex $\S_d$
have isomorphic subdivisions.  A simplicial complex $K$ 
is a {\it combinatorial $(d-1)$-sphere}, if $K$ and $\dot{\S_d}$ 
have isomorphic subdivisions (where $\dot{\S_d}$ denotes
the boundary of $\S_d$ with its induced simplicial structure). 
A simplicial complex $K$ is a {\it combinatorial $d$-manifold with
boundary} if the link of every vertex is either a combinatorial 
$(d-1)$-sphere or a combinatorial $(d-1)$-ball.  The following
is a special case of the main theorem of \cite{Wh}.

\begin{thm} Let $K$ be a combinatorial $d$-manifold with
boundary which simplicially 
collapses to a vertex.  Then $K$ is a combinatorial $d$-ball.
\label{JHC}
\end{thm}

It is with this theorem (and its generalizations)
that one can strengthen the conclusion of Theorem~\ref{morse} beyond
homotopy equivalence. We present just one example. 
 
\begin{thm} Let $X$ be a combinatorial $d$-manifold with a discrete Morse
function with exactly two critical simplices.  Then $X$ is a 
combinatorial $d$-sphere.
\end{thm}

The proof is quite simple (given Theorem~\ref{JHC}). 
If  $X$ is a combinatorial $d$-manifold with a discrete Morse
function $f$ with exactly two critical simplices, then the critical simplices must 
be the minimum of $f$, which must occur at a vertex $v$,
and the maximum of $f$, which must occur at a $d$-simplex $\a$.
Then $X-\a$ is a combinatorial $d$-manifold with boundary with
a discrete Morse function with only a single critical simplex, namely 
the vertex $v$.
It follows from Lemma~\ref{coll} that
$X-\a$ collapses to $v$.  Whitehead's theorem now implies that 
$X-\a$ is a combinatorial $d$-ball, which implies that $X$ is
a combinatorial $d$-sphere.

\section{Cancelling Critical Points}

One of the main problems in Morse Theory, whether in the 
combinatorial or smooth setting, is to find a Morse function
for a given space with the fewest possible critical points 
(much of the book \cite{Sh} is devoted to this topic).
In general this is a very difficult problem, since, in particular, it 
contains the Poincar\'e conjecture --- spheres can be recognized as 
those spaces
which have a Morse function with precisely 2 critical points.  
In \cite{Mi2}, Milnor
presents  Smale's proof \cite{Sm2} of the higher dimensional 
Poincar\'e conjecture
(in fact, a proof is presented of the more general $h$-cobordism
theorem) 
completely in the 
language of Morse Theory.  Drastically oversimplifying matters,
the proof of
the higher Poincar\'e conjecture can be described as follows. 
Let $M$ be a smooth manifold
of dimension $\ge 5$ which is homotopy equivalent to a sphere.  
Endow $M$ with 
a (smooth) Morse function $f$.  One then proceeds to show that the 
critical points of
$f$ can be cancelled out in pairs until one is left with a Morse 
function with exactly
two critical points, which implies that $M$ is a (topological) sphere.

A key step in this proof is the ``cancellation theorem" which provides
a sufficient condition for two critical points to be cancelled
(see Theorem~5.4 in \cite{Mi2}, which Milnor calls ``The First 
Cancellation Theorem", or the original proof in \cite{Mo2}).
In this section we will see that the analogous theorem holds for 
discrete Morse functions.  Moreover, in the combinatorial setting the proof is 
much simpler.  The main result is that if
$\a^{(p)}$ and $\beta^{(p+1)}$ are 2 critical simplices, and if there
is exactly 1 gradient path from the boundary of 
$\beta$ to $\a$, then $\a$ and
$\beta$ can be cancelled. More precisely, 

\begin{thm} Suppose $f$ is a discrete Morse function on $M$
such that $\beta^{(p+1)}$ and $\a^{(p)}$ are critical, and there is
exactly one gradient path from the boundary 
$\beta$ to $\a$.  Then there is
another Morse function $g$ on $M$ with the same critical simplices
except that $\a$ and $\beta$ are no longer critical.  Moreover, the
gradient vector field associated to $g$ is equal to the gradient
vector field associated to $f$ except along the unique gradient path
from the boundary $\beta$ to $\a$.
\end{thm}

In the smooth case, the proof, either as presented
originally by Morse in \cite{Mo2} or as presented in \cite{Mi2}, is
rather technical. In our discrete case the proof is simple. If, in
the top drawing in Figure~\ref{modgpath}, 
the indicated gradient path is the only gradient path
from the boundary of 
$\beta$ to $\a$, then we can reverse the gradient vector field
along this path, replacing the figure by the vector field shown in
the bottom drawing in Figure~\ref{modgpath}.

\begin{fig}
\lfigure{user16.pdf}{Cancelling critical points.}
{0.7}
\label{modgpath}
\end{fig}

The uniqueness of the gradient path implies that the resulting
discrete vector field has no closed orbits, and hence, by Theorem~\ref{grad},
is the gradient vector field of some Morse function.
Moreover, $\a$ and $\beta$ are not critical for this new Morse
function, while the criticality of all other simplices is unchanged. 
This completes the proof. 

The proof in the smooth case proceeds along the same lines. However,
in addition to turning around those vectors along the unique
gradient path from $\beta$ to $\a$, one must also adjust all nearby
vectors so that the resulting vector field is smooth. Moreover, one
must check that the new vector field is the gradient of a
function, so that, in particular, modifying the vectors
did not result in the creation of a closed orbit.  This is an
example of the sort of complications which arise in the smooth
setting, but which do not make an appearance in the discrete theory.

This theorem was recently put to very good use in \cite{BH}, in which 
discrete Morse Theory is used to determine the homotopy type of some
simplicial complexes arising in the study of partitions. It is fascinating, and 
quite pleasing, to see the same  idea play a central role in two subjects, 
the Poincar\'e conjecture and the study of partitions, which seem to have
so little to do with one another.

\section{Morse Theory and Evasiveness}

So far, we have indicated some applications of discrete
Morse Theory to combinatorics and topology.
We now present an application 
to computer science. The reader should see the reference \cite{F6} for 
a more complete treatment of the content of this section.

The problem we study is a topological version of a standard type of
``search problem''.  The generalized version that we will present first
appeared in \cite{RV}. Let $S$ be an $n$-dimensional simplex, with 
vertices
$v_0,v_1,\dots,v_n$, and $K$ a subcomplex of $S$ which is known to
you.  Let $\s$ be a face of $S$ which is not known to you. Your goal is
to determine if $\s$ is in $K$.  In particular, you need not determine
the face $\s$, just whether or not it is in $K$.  
You are permitted to ask questions of
the form ``Is $v_i$ in $\s$?''. You may use the answers to the
questions you have already asked in determining which vertex to ask
about next. Of course, you can determine if $\s$ is in $K$ by asking
$n+1$ questions, since by asking about all $n+1$ vertices you can
completely determine $\s$.  You win this game if you answer the given
question after asking fewer than $n+1$ questions. 

Say that $K$ is {\it nonevasive} if there is a winning strategy for this
game, i.e there is a question algorithm that determines whether or not
$\s \in K$ in fewer than $n+1$ questions, no matter what $\s$ is.  Say
$K$ is 
{\it evasive} otherwise. 

Kahn, Saks and Sturtevant proved the following relationship between the
evasiveness of $K$ and its algebraic topology.

\begin{thm} If $\tilde{H}_*(K) \ne0$, where $\tilde{H}_*(K)$
denotes the reduced homology of $K$,  then $K$ is evasive.
\label{kss}
\end{thm}

In fact, they proved something stronger, and we will come back to this
point later. We illustrate the previous theorem with a simple example.
Let $S$ be the 2-simplex shown in Figure~\ref{ev}, spanned by the vertices
$v_0,v_1$ and $v_2$, with $K$ the subcomplex consisting of the edge
$[v_0,v_1]$ together with the vertex $v_2$. 
\begin{fig}
\lfigure{slides9.pdf}{An example of an evasive
subcomplex of the 2-dimensional simplex.}{0.3}
\label{ev}
\end{fig}

A possible guessing algorithm is shown in Figure~\ref{alg}.  Define an 
{\it evader} 
of a guessing algorithm to be a face $\s$ of $S$ with the property
that when questions are asked in the order determined by the algorithm 
one must ask all three questions before it is known whether
or not $\s$ is in $K$. In particular, the evaders of the illustrated
guessing algorithm are:
$$
\sigma = [v_2],\ \ [v_0,v_2]
$$

\noindent Note that the subcomplex $K$ has nonzero reduced homology, so the
theorem of Kahn, Saks and Sturtevant guarantees that every guessing
algorithm has some evaders.

\begin{fig}
\lfigure{user17.pdf}{A guessing algorithm}{1.0}
\label{alg}
\end{fig}
Morse Theory comes to the fore when one 
observes that a guessing algorithm induces a discrete vector field on
$S$. For example, the guessing algorithm shown in Figure~\ref{alg}
induces the vector field
\begin{eqnarray*}
V = &\{\,\{\emptyset<[v_1]\}, \{[v_0] < [v_0,v_1]\},\\
&\{[v_2] < [v_0,v_2]\}, \{[v_1,v_2] < [v_0,v_1,v_2]\}\,\}
\end{eqnarray*}
That is, $V$ consists of those pairs of faces of $S$ which are not
distinguished by the guessing algorithm until the last question.
There is slight subtlety here in that a guessing algorithm pairs a
vertex with the empty simplex $\emptyset$, while in our original
definition, it was not permitted to pair a simplex with
$\emptyset$. Thus, to get a true discrete vector field, we must remove
this pair from $V$. (It is precisely this subtle point that results in
the reduced homology of $K$ being the relevant measure of topological
complexity, rather than the nonreduced homology.) However, for
simplicity, from now on we will simply ignore this technical point.


\begin{fig}
\lfigure{slides7.pdf}{The vector field induced
by the guessing algorithm shown in Figure~\ref{alg}.}{0.3}
\label{induced}
\end{fig}
 
\begin{thm} This induced vector field is always a gradient vector field.
\label{always}
\end{thm}
\noindent We will postpone the proof of 
this result until the end of this section.


Now restrict $V$ to $K$ (by taking only those pairs in $V$
such that both simplices are in $K$). For example, in our example, this 
results in the vector field
$$
V_K = \{\{[v_0] < [v_0,v_1]\}\}.
$$
{}From the previous theorem, $V$ has no closed orbits. Any
discrete vector field consisting of a subset of the pairs of $V$ has
fewer paths, and hence also has no closed orbits.  
Therefore, $V_K$ is a gradient vector field on $K$. 
Note that $V$ pairs every face of $S$ with another face, and
hence there are no critical simplices (we are continuing to ignore
for now the simplex which is paired with the emptyset).
Thus, the critical simplices of $V_K$ 
are precisely the simplices of $K$ which are paired in $V$ with a face
of $S$ which is not in $K$. These are precisely the simplices of $K$
which
are the evaders of the
guessing algorithm.

The Morse inequalities of Theorem~\ref{mi} (i)
imply that the number of evaders in $K$ is at
least $\dim\wt H_*(K)$.  Evaders occur in pairs, with each pair having
one face of $K$ and one face not in $K$. This yields the following
quantitative refinement of Theorem~\ref{kss}.

\begin{thm} For any guessing algorithm
$$
\#\text{ of evaders }\ge2\dim\wt H_*(K)
$$
\end{thm}

Suppose that $K$ is nonevasive.  Then there is some guessing algorithm
which has no evaders. From our above discussion we have seen that this
implies that $K$ has a gradient vector field with no critical
simplices. Actually, this is not quite true. The gradient vector field
must have a critical vertex --- the vertex that is paired with the empty
set --- this is that
minor technicality that we have been ignoring.  Applying Lemma~\ref{coll}
yields the following strengthening of Theorem~\ref{kss}.  

\begin{thm} If $K$ is nonevasive, then $K$ simplicially collapses
to a point.
\end{thm}

\noindent This theorem appears in \cite{KSS}. 
The interested reader can consult
\cite{F6} for some additional refinements of this theorem.

We end this section with a proof of Theorem~\ref{always}. 
Fix a subcomplex $K$
of an $n$-simplex $S$, and a guessing algorithm.
Associate to each $p$-simplex $\a$ of $S$ the sequence of integers
$$
n(\a) = n_0(\a) < n_1(\a) < \dots < n_p(\a)
$$
where the $n_i(\a)$'s are the numbers of the questions
answered ``yes'' if $\sigma=\a$.

If $V$ is the vector field induced by the guessing algorithm
and
$$
\a^{(p)}_0,\ \ \b^{(p+1)}_0,\ \ \a^{(p)}_1
$$
is a $V$-path, then $\{ \a_0,\b_0 \}$ is in $V$, which means that
$\a_0$ and $\b_0$ are not distinguished until the $(n+1)^{st}$ question.
Thus,
$$
n(\b_0) = n_0(\a_0) < n_1(\a_0) < \dots < n_p(\a_0)<n+1.
$$
We now observe that the vertices of $a_1$ are a subset of the vertices
of $b_0$. Suppose the vertex of $\b_0$ which is not in $\a_1$ is the
vertex tested in question $n_i(\b_0)$. Then we must have $i \ne n+1$
(since $\a_0 \ne \a_1$). 
This demonstrates that
$$
n(\a_1) = n_0(\a_0) < n_1(\a_0) < \dots <
n_{i-1}(\a_0)<n_i(\a_1)<\dots
$$
for some $i< n+1$, and such that $n_i(\a_1)>n_i(\a_0)$.
Thus $n(\a_1)>n(\a_0)$ in the lexicographic order, which is sufficient
to prove that there are no closed orbits.
\rightline{QED}

\section{Further Thoughts}

We close this paper with some additional thoughts
on the subjects discussed in this paper.

I would like to begin by encouraging the reader to take a look at 
the papers \cite{K1}, \cite{K2}, and \cite{BW}. In these
papers, discrete Morse Theory is used to investigate
quite interesting problems.  These references were not
mentioned earlier only because they did not easily fit into
any of the previous sections of this paper.

There are a number of directions in which 
discrete Morse Theory can be extended and generalized.
Here we mention a few such possibilities. In \cite{F8} we show 
how one can recover the ring structure of the cohomology
of a simplicial complex
from the point of view of discrete Morse Theory (this follows work of
Betz and Cohen \cite{BC} and Fukaya \cite{Fu1,Fu2} in the
smooth setting).  In \cite{No}, 
Novikov presents a generalization of standard smooth Morse
Theory in which the role of the Morse function is now played
by a closed 1-form (the classical case arises when the 
closed 1-form is exact).  In \cite{F7} we present the analogous
generalization  for discrete Morse Theory.  In \cite{Wi}, Witten
shows how smooth Morse Theory can be seen as arising
from considerations of supersymmetry in quantum physics.
In \cite{F3} we present a combinatorial version of Witten's 
derivation.  We believe that this latter work may have greater 
significance.  At crucial points in \cite{Wi}, Witten appeals 
to path integral arguments which are rather standard in 
quantum physics, but are ill-defined mathematically.
In the corresponding moments in \cite{F3} what arises
is a well-defined discrete sum. Perhaps the approach
in \cite{F3} can find uses in the analysis of other
quantum field theories.

One topic which we have only touched upon is the
study of the dynamics associated to flowing 
along the gradient vector field associated to
a discrete Morse function.  In fact, an understanding
of the dynamics is crucial to the proof of theorem
\ref{mc2}, for example.  The relevant study takes 
place in Section~6 of \cite{F2}. In \cite{F4} we study the
dynamical properties of the flow associated to a general
discrete vector field.

One area in which much work remains to be done
is the investigation of discrete Morse Theory
for infinite simplicial complexes. The theory as
described in this paper can be applied without change
to an infinite simplicial complex $K$  endowed with a 
discrete Morse function $f$ which is {\it proper},
i.e., one in which for each real number $c$ the
level subcomplex $K(c)$ is a finite complex.
Unfortunately, properness is often an unnatural 
requirement when considering the infinite simplicial complexes
which arise in practice.  In the interesting paper
\cite{MY}, discrete Morse
Theory is applied to the investigation of infinite simplicial
complexes $K$ which arise as a covering space of a finite simplicial
complex $K'$. In this case, the authors restrict attention to
discrete Morse functions which are lifts of a Morse function
on $K'$, and compare the number of critical simplices 
to the $L^2$-Betti numbers of $K$.  While it appears to be
too much to hope that one can develop a useful theory
that applies to all infinite simplicial complexes with no
restrictions on the discrete Morse function, it seems likely 
that there is room for very useful investigations of large classes
of complexes and functions with restrictions different than those
already considered.

I will close these notes with some comments of a less rigorous nature.
Whether in the smooth category or the combinatorial category,
Morse Theory is not essential to any problem, it is usually
``only" a convenient and efficient language. Anything
that can be done with Morse Theory can be done without it.
It seems to me that  Morse Theory takes on a special 
significance in three different cases. First are the cases
in which Morse Theory is not intrinsic to the problem, but
where the existence of such an efficient language may
make the difference between whether or not 
one is able 
to see the way to the end of a problem.  The best example of this 
in the smooth
setting, I think, is the proof of the higher dimensional
Poincar\'e conjecture (\cite{Sm1}, \cite{Mi2}).
Most of the applications of discrete Morse Theory 
mentioned in Section~\ref{nconn}, 
for example, seem to fall into this category.  Second
are the cases in which the space one is studying comes naturally
endowed with a Morse function, or a gradient vector field.
Here the prime example is Bott's proof of Bott periodicity (\cite{Bo},
see also Part IV of \cite{Mi1}), resting on the fact that 
the loop space of a 
Riemannian manifold is endowed with a natural Morse
function.
In the combinatorial
setting, I would place the Morse-theoretic 
examination of evasiveness of the previous section in this category.
Third are the cases in which the objects under investigation
can be naturally identified as the critical points of 
a Morse function on a larger space.  Examples
of this phenomenon abound in differential geometry,
where one often studies extremals of energy
functionals.  In particular, Morse's first great triumph with
Morse Theory was his investigation of the set of geodesics
between two points in a Riemannian manifold (\cite{Mo1}, see also
Part III of \cite{Mi1}). The geodesics
are precisely the critical points of the natural Morse function
on the path space, and Morse used the Morse inequalities, along 
with a knowledge of the topology of the path space, to 
deduce the existence of many critical points.
It is intriguing to this author that there are as yet no
corresponding examples in the combinatorial setting.  I know
of no examples in which a collection of classically studied
objects in combinatorics can be naturally identified with the 
critical simplices of a Morse function on some larger complex. 
Indeed, I believe that soon combinatorial examples
of interest will be found that fit into this third category.
I wonder if applications of discrete Morse theory will be found that
approach the beauty, depth and fundamental significance of the 
applications of smooth Morse Theory mentioned in this paragraph.

On a broader note, I believe that discrete Morse Theory is only a 
small part of what someday will be a more complete theory of 
``combinatorial differential topology'', although I hesitate
to predict (at least in print) what form such a theory will take.


\newpage
\begin{thebibliography}{BBSLW}

\bibitem{BBLSW} E. Babson, A. Bj\"{o}rner, S. Linusson, J. Shareshian
and V. Welker,
{\em Complexes of not $i$-Connected Graphs}, Topology {\bf 38 } (1999),
pp.~271-299.

\bibitem{BH} E. Babson, P. Hersh, {\em Discrete Morse functions from 
lexicographic orders}, to appear in Topology.

\bibitem{BW}  E. Batzies and V. Welker {\em Discrete Morse Theory
for Cellular Resolutions}, J. Reine Angew.\ Math.\ {\bf 543} (2002), 
pp.~147--168.

\bibitem{BC}  M. Betz and R. Cohen, 
{\em Graph moduli space and cohomology operations}, Turk.\ J. of Math.\
{\bf 18} (1994), pp.~23-41.

\bibitem{Bo} R. Bott, {\em Stable homotopy of the classical groups},
Ann.\ of Math.\ {\bf 70} (1959), pp.~313-337.

\bibitem{C}  M. Chari, {\em On Discrete Morse Functions and
Combinatorial Decompositions}, {Discrete Math.} {\bf 217} (2000),
pp.~101-113.

\bibitem{D} X. Dong, {\em The Topology of Bounded Degree Graph
Complexes and Finite Free Resolutions}, thesis, Univ.\ of Minn., 2001.

\bibitem{Du} A. Duval
{\em A Combinatorial Decomposition of Simplicial Complexes},
Israel J. of Math.\ {\bf 87} (1994), pp.~77-87. 

\bibitem{F1} R. Forman, {\em A Discrete Morse Theory for Cell
Complexes}, in: Geometry, Topology \& Physics for Raoul Bott,
S.T. Yau (ed.),
International Press, 1995.

\bibitem{F2} \bysame, {\em Morse Theory for Cell Complexes}, 
Adv.\ in Math.\ {\bf 134} (1998), pp.~90-145.

\bibitem{F3} \bysame, {\em Witten-Morse Theory for Cell Complexes}, 
Topology {\bf 37} (1998), pp.~945-979.

\bibitem{F4} \bysame, {\em Combinatorial Vector Fields and Dynamical 
Systems}, Math.\ Zeit.\ {\bf 228} (1998), pp.~629-681.

\bibitem{F5} \bysame, {\em Combinatorial differential topology and
geometry}, in: New Perspectives in Algebraic Combinatorics (Berkeley, CA.
1996-97), Math.\ Sci.\ Res.\ Inst.\ Publ.\ 38, Cambridge Univ.\ Press,
Cambridge, 91999), pp.~177-206.
  
\bibitem{F6} \bysame, {\em Morse Theory and Evasiveness}, 
Combinatorica {\bf  20} (2000), pp.~498-504.

\bibitem{F7} \bysame, {\em Novikov-Morse theory for cell complexes}, 
to appear in Int.\ J. of Math.

\bibitem{F8}\bysame {\em The Cohomology Ring and Discrete Morse
Theory}, preprint 2001.

\bibitem{Fu1} K. Fukaya, {\em Morse homotopy,
$A^{\infty}$-category, and Floer homologies}, in: Proc.\ Garc.\ 
Workshop on Geometry and Topology '93, (Seoul, 1993),
ed.\ H. J. Kim, Lecture Notes Ser.\ 18, Seoul National University, pp 1-102.

\bibitem{Fu2} \bysame, {\em Morse homotopy and its quantization},
in: Geometric Topology (Athens, GA 1993),AMS/IP Stud.\ Adv.\ Math\. 21, 
Amer.\ Math.\ Soc., Prov.\ RI, 1997, pp.~409-440. 

\bibitem{GoM1} M. Goresky and R. MacPherson
{\em Stratified Morse Theory},
in: Singularities, Part I (Arcata, CA, 1981),
Proc.\ Sympos.\ Pure Math., 40, Amer.\ Math.\ Soc., R.I., (1983), pp.~517-533.

\bibitem{GoM2}   \bysame
{\em Stratified Morse Theory},
Ergebnisse der Mathematik und ihrer Grenzgebiete (3), {\bf 14},
Springer Verlag, Berlin-New York, 1988.


\bibitem{J1} J. Jonsson, {\em On the homology of some complexes of
graphs}, preprint, 1998.

\bibitem{J2} \bysame, {\em The decision tree method}, preprint, 1999.
 

\bibitem{KSS}  J. Kahn, M. Saks and D. Sturtevant
{\em A topological approach to evasiveness},
Combinatorica {\bf 4} (1984), pp.~297-306.

\bibitem{K1} D. Kozlov, {\em Collapsibility of $\Delta(\Pi_n)/ S_n$
and some related CW complexes}, Proc.\ Amer.\ Math.\ Soc.\ {\bf 128} (2000),
pp.~2253-2259.

\bibitem{K2} \bysame, {\em Topology of spaces of hyperbolic
polynomials with multiple roots}, to appear in Israel J. Math. 


\bibitem{K} W. K\"uhnel,
{\em Triangulations of Manifolds with few Vertices},
in: Advances in Differential Geometry and Topology,
World Sci.\ Publishing, N.J., (1990), pp.~59-114.

\bibitem{LS} S. Linusson and J. Shareshian, {\em Complexes
of $t$-colorable graphs}, preprint.

\bibitem{LW} A. Lundell and S. Weingram, {\em The Topology of CW
Complexes}, Van Nostrand Reinhold Company,  New York, 1969.

\bibitem{MY} V. Mathai and S.G. Yates, {\em Discrete Morse theory and
extended $L^2$ homology}, J. Funct.\ Anal.\ {\bf 168} (1999), pp.~84--110.

\bibitem{Mi1}   J. Milnor {\em Morse Theory},
Annals of Mathematics Study No.~51, Princeton
University Press, 1962.

\bibitem{Mi2}   \bysame,
{\em Lectures on the $h$-Cobordism Theorem}
Princeton Mathematical Notes, Princeton University
Press, 1965.


\bibitem{Mo1} M. Morse,
{\em The Calculus of Variations in the Large},
Amer.\ Math.\ Soc.\ Colloquium Pub.\ {\bf 18}, Amer.\ Math.\ Soc.,
Providence R.I., (1934).

\bibitem{Mo2}  \bysame,
{\em Bowls of a Non-Degenerate Function on a Compact
Differentiable Manifold}, in: Differential and Combinatorial
Topology (A Symposium in Honor of M. Morse),
Princeton University Press
(1965), pp.~81-104.

\bibitem{No} S. Novikov, {\em Multivalued
functions and functions: An analogue of the Morse theory}, Soviet Math.\ Dokl.\
{\bf 24} (1981), pp.~222-226.

\bibitem{RV} R.L. Rivest and J. Vuillemin
{\em On recognizing graph properties from adjacency matrices},
Theor.\ Comp.\ Sci.\ {\bf 3} (1976), pp.~371-384.

\bibitem{Sc} M. Schwartz, {\em Morse Homology}
Progress in Mathematics, 111, Birkh\"auser Verlag, Basel (1993).

\bibitem{S} J. Shareshian, {\em Discrete Morse Theory for 
Complexes of $2$-Connected Graphs}, to appear in Topology. 

\bibitem{Sh} V. Sharko, {\em Functions on Manifolds, Algebraic and
Topological Aspects}, Trans.\ of Math.\ Monographs 131,
Amer.\ Math.\ Soc., Providence, R.I., (1993). 

\bibitem{Sm1} S. Smale,
{\em On Gradient Dynamical Systems},
Annals of Math.\ {\bf74} (1961), pp.~199-206.

\bibitem{Sm2}   \bysame
{\em The Generalized Poincar\'e Conjecture in Dimensions
Greater than Four}, Annals of Math.\ {\bf 74} (1961), pp.~391-406.

\bibitem{Sta} R. Stanley,
{\em A Combinatorial Decomposition of Acyclic Simplicial Complexes},
Discrete Math.\ {\bf 120} (1993), pp.~175--182.

\bibitem{Tu} V. Turchin,
{\em Homology of Complexes of Biconnected Graphs},
Uspekhi Mat.\ Nauk.\ {\bf 52} (1997), pp.~189-190; translation in
Russian Math.\ Surveys {\bf 52} (1997), 426--427.


\bibitem{Va}  V. Vassiliev,
{\em Complexes of Connected Graphs},
in: The Gelfand Mathematical Seminars, 1990--1992,
pp.~223--235.  Birkh\"auser Boston, Boston, (1993).


\bibitem{Wh} J.H.C. Whitehead,
{\em Simplicial Spaces, Nuclei, and $m$-Groups},
Proc.\ London Math.\ Soc.\  {\bf 45} (1939), pp.~243-327.


\bibitem{Wi}  E. Witten
{\em Supersymmetry and Morse Theory}
J.\ Diff.\ Geom.\ {\bf 17}  (1982), pp.~661--692.

\end{thebibliography}
\end{document}
