Discrete Morse Theory

Simplicial Complex

Simplex

A simplex is just an \(n\)-dimensional “triangle”

formally

\[\Delta^n=\LS x \in \R^k: x_0+\cdots+x_{k-1}=1, x_i \geq 0 \text { for } i=0, \ldots, k-1\RS\]

We can also describe an \(n\) simplex combinatorially as a list of the vertices of the simplex \[\sigma = \LB e_0,\ e_1,\ \cdots, e_n\RB\]

Face of a Simplex

We define a face \(\tau \), of a simplex \(\sigma\), as a proper subset of \(\sigma\) that is

\[ \tau < \sigma \] when \[ \LB a,b\RB \subset \LB a, \ b,\ c\RB \]

Simplicial complex

A simplicial complex is a space \(K\) built from glued together simplices and must satisfy

  1. If \(\tau\) is the face of a simplex $\sigma \in K$ then \(\tau\in K\)
  2. If \(\sigma, \tau \in K\) then \(\sigma\cap \tau\) is a face of \(\sigma\) and \(\tau\).

It’s convenient to have a combinatorial description for \(K\). This description is called an “abstract simplicial complex” and is just the collection of combinatorial descriptions of simplices of \(K\)

\[\LS \LB b,c,d\RB, \LB b,c\RB, \LB b,d\RB, \LB c,d\RB, \LB a,c\RB, \LB a,b\RB, \LB d,e\RB, \LB a\RB, \LB b\RB, \LB c\RB, \LB d\RB, \LB e\RB\RS \]

Definition of a “Discrete function”

A discrete function \(f\) on a simplicial complex \(K\) assigns a number to each simplex

\( \begin{aligned} f\LP\LB b,c,d\RB\RP &= 5 \\ f\LP\LB b,c\RB\RP &= 4 \\ f\LP\LB b,d\RB\RP &= 5 \\ f\LP\LB c,d\RB\RP &= 3 \\ f\LP\LB a,c\RB\RP &= 1 \\ f\LP\LB a,b\RB\RP &= 1 \\ f\LP\LB d,e\RB\RP &= 5 \\ f\LP\LB a\RB\RP &= 0 \\ f\LP\LB b\RB\RP &= 2 \\ f\LP\LB c\RB\RP &= 2 \\ f\LP\LB d\RB\RP &= 4 \\ f\LP\LB e\RB\RP &= 6 \\ \end{aligned} \)

Definition of a “Discrete Morse function”

A discrete function \[f:K\to \R\] is called a discrete Morse function if for every \(n\)-simplex \(\alpha^n \in K\) the following are true

  1. \(\#\LS \alpha^n<\beta^{n+1} \MM f\LP\beta^{n+1}\RP\leq f\LP\alpha^n\RP\RS\leq 1\)
  2. \(\#\LS \alpha^n>\gamma^{n-1} \MM f\LP\gamma^{n-1}\RP\geq f\LP\alpha^n\RP\RS\leq 1\)
  1. \(\#\LS \alpha^n<\beta^{n+1} \MM f\LP\beta^{n+1}\RP\leq f\LP\alpha^n\RP\RS\leq 1\)
  2. \(\#\LS \alpha^n>\gamma^{n-1} \MM f\LP\gamma^{n-1}\RP\geq f\LP\alpha^n\RP\RS\leq 1\)
  1. \(\#\LS \alpha^n<\beta^{n+1} \MM f\LP\beta^{n+1}\RP\leq f\LP\alpha^n\RP\RS\leq 1\)
  2. \(\#\LS \alpha^n>\gamma^{n-1} \MM f\LP\gamma^{n-1}\RP\geq f\LP\alpha^n\RP\RS\leq 1\)

Definition of a Critical simplex

An \(n-\)simplex \(\alpha^n\), of a complex \(K\), is critical under a discrete Morse function \(f\) if the following are true

  1. \(\#\LS \alpha^n<\beta^{n+1} \MM f\LP\beta^{n+1}\RP\leq f\LP\alpha^n\RP\RS=0\)
  2. \(\#\LS \alpha^n>\gamma^{n-1} \MM f\LP\gamma^{n-1}\RP\geq f\LP\alpha^n\RP\RS=0\)

We should note that for all the \(\alpha\in K\) at least one of \(1.\) and \(2.\) must be true.

  1. \(\#\LS \alpha^n<\beta^{n+1} \MM f\LP\beta^{n+1}\RP\leq f\LP\alpha^n\RP\RS=0\)
  2. \(\#\LS \alpha^n>\gamma^{n-1} \MM f\LP\gamma^{n-1}\RP\geq f\LP\alpha^n\RP\RS=0\)

Discrete Gradient Vector Field

A discrete gradient vector field on a simplicial complex \(K\) is a collection of pairs \(V=\LS\tau^n<\sigma^{n+1}\RS\) of simplices in \(K\) such that each simplex is in at most one pair of \(V\).

A discrete Morse function induces a gradient vector field on \(K\).

If \(\alpha\) is a non-critical simplex, and \[\alpha<\beta\] with \[f\LP\beta\RP<f\LP\alpha\RP\] We draw an arrow from \(\alpha\to \beta\).

Simplicial collapse

The simplicial equivalent of a deformation retraction is called a simplicial collapse.

Maximal Face

A face \(\sigma\in K\) is called maximal if there is no \(\beta\in K\) so that \(\sigma<\beta\).

Free face

A simplex \(\tau\) of a simplicial complex \(K\) is called a free face if \(\tau\) is a face of exactly one maximal face.

Collapse

If \(\tau\) is a free face of \(\sigma\) we can collapse \(K \searrow K^\prime\) by the following set operation

\[K^\prime = K-\LP\tau \cup \sigma\RP\]

Collapsing A Vector Field

Given a vector field we can simplicially collapse following the arrows.

Main result of discrete Morse Theory

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 \(n\) for each critical simplex of dimension \(n\).

Sphere Theorems

Star of a face

The star of a face \(\tau\) of \(K\) is the subcomplex of \(K\) consisting of all faces \(\sigma\) of \(K\) where \(\tau < \sigma\), as well as all faces of \(\sigma\).

Link of a face

The link of a face \(\tau\) of \(K\) is the subcomplex of \(K\) consisting of all faces of the star of \(\tau\) that do not intersect \(\tau\).

Combinatorial d-ball

A complex \(K\) is a combinatorial d-ball if \(K\) and \(\Delta^d\) have isomorphic subdivisions.

A combinatorial \(\LP d-1\RP\)-sphere is the boundary of a \(d\)-ball

combinatorial d-manifold

A complex is a \(d\)-manifold if the link of every vertex is either a \((d-1)\)-ball or \((d-1)\)-sphere.

Sphere theorems

Let \(K\) be a combinitorial \(d\)-manifold with boundary which simplicially collapses to a vertex. Then \(K\) is a combinitorial \(d\)-ball.

Let \(X\) be a combinatorial \(d\)-manifold with a discrete with a discrete Morse function with exactly two critical simplices. Then \(X\) is a combinitorial sphere.

References