Discrete Morse theory simplifies the study of a finite complex by pairing cells that can be treated together and retaining critical cells that describe a smaller topological model. Its practical value is a reduction with a reason: fewer cells to understand or compute with, while a specified mathematical structure is preserved.
The gold standard is a valid pairing, a check that it contains no forbidden closed paths, and a precise statement of what the reduced model retains. Counting unmatched cells is useful, but it does not by itself calculate every homology group, prove that a matching is optimal, or preserve a filtration. This guide develops those distinctions through explicit graphs, triangles and a changed-context example.
Start with Computational Topology for complexes and boundary matrices. Return to the Gold Standard master, Education parent and How X Works hub for connected learning routes.
Choose your discrete Morse theory route
Chapters 1–3: Define cells and functions
Chapters 4–6: Match and test paths
Chapters 7–9: Collapse and recover information
Chapters 10–12: Preserve the right structure
Chapter index
Define cells and functions · Chapters 1–3
1. Identify what needs to become smaller
Match and test paths · Chapters 4–6
4. Replace function values by a matching
Collapse and recover information · Chapters 7–9
7. Collapse a filled square step by step
Preserve the right structure · Chapters 10–12
10. Preserve a filtration only with additional conditions
Transfer and continue · Chapters 13–14
CHAPTER 1 OF 14 · Define cells and functions
1. Identify what needs to become smaller
A representation can be larger than its topology requires
A path with a hundred edges is topologically an interval, just as a path with one edge is. Its many vertices may be essential for storing measurements, but they are not all needed to describe its homotopy type. Discrete Morse theory provides a structured way to distinguish the combinatorial detail of a representation from the topology that a particular calculation needs.
Begin with the output requirement. If the task is to understand connected components and loops, a smaller model may suffice. If the task also requires precise lengths, original coordinates or a physical transport calculation, a topological simplification alone does not promise to retain those quantities. A reduction can be mathematically correct and still unsuitable for the intended application.
For example, replacing a winding path by a single point preserves its homotopy type. It destroys the information needed to report the path’s length or travel time. That is not a contradiction in the theory. It is a mismatch between the property preserved and the property requested.
Fix the mathematical setting
The examples here use finite simplicial complexes, with vertices, edges and filled triangles identified explicitly. Every face of an included simplex is included. We discuss ordinary homotopy type and homology first, then explain why a filtration imposes additional requirements. This scope avoids silently importing results for one class of cells into a more general construction.
A useful project statement is: construct an acyclic matching on the face incidences of this finite complex, report its critical cells by dimension, and verify the resulting homology against an independent calculation. That statement separates the construction, its validity and the evidence for the output. Each part can fail independently, so each deserves its own check.
CHAPTER 2 OF 14 · Define cells and functions
2. Distinguish a cell from a point in a picture
Incidence is the essential input
The triangle ABC contains seven nonempty simplices: A, B, C, AB, AC, BC and ABC. Its boundary alone contains six. A drawing of the three edges does not tell a program whether the filled triangle is included. That one decision changes which pairings are available and what topology the model represents.
A face incidence joins a simplex to a face one dimension lower. For ABC, these are the incidences with AB, AC and BC. Each edge also has two vertex incidences. Organising these relations produces the Hasse diagram of the face poset. Its nodes are simplices, not merely the original vertices of the geometric drawing.
This distinction matters when reading an algorithm. A graph search on the Hasse diagram is traversing relations among cells of several dimensions. A graph search on the original one-skeleton traverses only vertices and edges. Both are graphs in the computer-science sense, but their nodes and meanings differ.
Check a tiny input before importing a large mesh
List each simplex using a consistent ordering of its vertex identifiers. Check that every required face exists, that duplicate records have been reconciled, and that shared edges really use shared identifiers. Two triangles that appear to touch on a screen may remain disconnected in the data if their common coordinates have different vertex identities.
For a square triangulated by diagonal AC, the maximal simplices are ABC and ACD. There are four vertices, five edges and two triangles, for eleven nonempty simplices. The diagonal occurs once in the complex even though it belongs to two triangles. This is a small enough input to audit completely and rich enough to reveal a mistaken treatment of shared faces.
CHAPTER 3 OF 14 · Define cells and functions
3. Read a discrete Morse function correctly
Numbers belong to cells of every dimension
A discrete Morse function assigns a real number to each simplex. For a p-simplex, at most one immediate coface may have a value less than or equal to its value, and at most one immediate face may have a value greater than or equal to its value. A cell is critical when neither exception occurs.
The rule differs from simply assigning a height to each vertex. Edges and triangles also receive values, and the inequalities are checked against their incidences. The foundational reference is Robin Forman’s A User’s Guide to Discrete Morse Theory. Its central result gives a homotopy-equivalent CW model with one cell for each critical simplex, in the corresponding dimension.
Work the smallest nontrivial example
Take the interval with vertices A and B and edge AB. Set f(A) = 0, f(AB) = 1 and f(B) = 2. Vertex B has exactly one exceptional coface, AB, because 1 is less than 2. Edge AB has exactly one exceptional face, B, because 2 is greater than 1. Vertex A has no exception and is critical.
Thus B and AB form a pair, while A remains critical. The interval has been described by one critical vertex, consistent with its contractibility. The arithmetic is simple enough that the important work is identifying which comparisons are actually required.
Now set both vertex values to two while retaining edge value one. The edge has two exceptional faces, violating the definition. A plausible-looking valley is therefore not automatically a discrete Morse function. The local count of exceptions is the test; intuition from a smooth height drawing is only a guide.
Pair adjacent dimensions, without reusing a cell
A discrete vector field can be represented as a partial matching of face incidences. A pair consists of a p-cell and an incident cell of dimension p + 1. No cell may occur in more than one pair. Cells not used in any pair are the critical candidates.
This representation is often easier to implement than searching directly for real-valued function assignments. It makes two local checks explicit: the proposed cells must be incident in adjacent dimensions, and neither may already be matched. But these local conditions are not the whole validity test.
The Zuse Institute’s discrete Morse functions project describes the additional acyclicity condition and the optimisation problem of reducing critical cells. A maximum-size matching in an ordinary graph need not satisfy that condition. Choosing more pairs is not automatically choosing a better Morse matching.
Orient the incidences to expose the global condition
Use the following convention throughout this article. Direct every unmatched incidence from the higher-dimensional cell to its face. Reverse every matched incidence, directing it from the lower-dimensional cell to its partner. Check the resulting directed graph for cycles. An acyclic matching has no directed cycle.
State the convention in code comments and diagnostic reports. Reversing every arrow consistently preserves whether a directed cycle exists, but mixing conventions within one graph can produce a meaningless test. The simplest verification uses one orientation rule to construct the entire graph, then an independent topological-sort or depth-first-search routine.
The output of a failed check should include an actual cycle, not merely the word invalid. A sequence of named cells lets a person see which pairs interact to create the problem. It also makes the failure reproducible after vertex labels or input order change.
CHAPTER 5 OF 14 · Match and test paths
5. See why a locally valid matching can fail
A closed triangular frame
Take the triangle boundary with vertices A, B, C and edges AB, BC, CA, with no filled triangle. Propose the pairs A–AB, B–BC and C–CA. Each pair uses an incident vertex and edge. No cell is reused. By the local matching rules, everything appears acceptable.
With our orientation convention, however, the directed Hasse diagram contains A → AB → B → BC → C → CA → A. The arrows going upward are the proposed pairs. The arrows returning to vertices are the other endpoint incidences. This is a directed cycle, so the matching is not an acyclic Morse matching.
The same obstruction appears if we try to assign function values. The pair A–AB requires f(A) ≥ f(AB). The unmatched endpoint B must satisfy f(AB) > f(B). Continuing around the triangle gives f(A) > f(B) > f(C) > f(A), which is impossible.
Repair the matching rather than hiding the cycle
Remove the pair C–CA. The remaining pairs A–AB and B–BC leave C and CA critical. The directed path now terminates instead of closing. There is one critical vertex and one critical edge, matching the familiar CW description of a circle.
Notice what the repair did not do. It did not remove edge CA from the original complex, and it did not claim the circle was an interval. It changed the matching so that the smaller model can retain the loop. Treating every unmatched edge as a disposable error would destroy exactly the information the method needs to preserve.
This example is an especially useful regression test. A routine that checks only disjointness of pairs will accept the invalid three-pair proposal. A routine that genuinely checks acyclicity must reject it and accept the repaired two-pair version. Both tests are necessary.
Choose a root and work away from it
Consider the tree with edges AB, BC, BD and DE. Choose B as the root. Pair A with AB, C with BC, D with BD and E with DE. Every non-root vertex is paired with the edge connecting it toward the root. B remains the only critical cell.
The directed paths in the matching move toward B after each upward-and-downward step. For example, E → DE → D → BD → B. Since graph distance to the root decreases after each such step, a closed path is impossible. This supplies a simple numerical reason for acyclicity rather than relying solely on a picture.
There are five vertices and four edges. Four pairs account for eight cells, leaving one critical vertex. The original Euler characteristic is 5 − 4 = 1, and the critical-cell alternating sum is also one. This count agrees with the tree’s contractibility.
Change the root and examine what changes
If E is chosen as the root instead, the pairing changes. A pairs with AB, B with BD, C with BC and D with DE. Now E is critical. The chosen representative is different, while the homotopy conclusion is unchanged.
This distinction matters in applied work. A critical cell’s location can depend on a legitimate algorithmic choice. It should not automatically be interpreted as a uniquely meaningful physical landmark. If location is important, record the root-selection rule, tie breaking and other choices that influence the representative.
The tree example also gives a constructive debugging strategy. Run the algorithm on randomly relabelled copies of the same tree. The surviving label may change under a label-based root rule, but the count of critical cells should not. If loops or extra components appear, inspect the incidence construction before attempting a more sophisticated optimisation.
CHAPTER 7 OF 14 · Collapse and recover information
7. Collapse a filled square step by step
Free-face removal is a concrete special case
Use the square triangulation ABC and ACD. Edge AB belongs only to triangle ABC, so remove the pair AB–ABC as an elementary collapse. In the remaining complex, edge CD belongs only to triangle ACD, so remove CD–ACD. The surviving edges are AC, BC and AD.
These edges form the path B–C–A–D. Remove B–BC, then C–AC, then D–AD. Vertex A remains. At each step, the lower-dimensional member is a free face of the higher-dimensional member in the current complex. The order matters because the current cofaces determine whether a removal is legal.
The full sequence contains two edge–triangle pairs and three vertex–edge pairs. It removes ten of the eleven original cells. The critical vector is therefore (1,0,0). The direct collapse sequence proves more than a successful cell count: it provides a checkable sequence of topological simplifications.
Why the diagonal is not initially free
At the beginning, AC belongs to both ABC and ACD. It cannot be removed with just one of those triangles as an elementary free-face collapse. Doing so would leave the other triangle without a required boundary edge. This is a closure failure in the remaining simplicial complex, not a small numerical discrepancy.
A general acyclic matching need not be executable by deleting all its pairs in arbitrary order as free-face collapses. The broader theory organises attachments and reductions through critical cells. Keep that theorem distinct from the simpler special case where an explicit elementary-collapse sequence is available.
For implementation, record the coface count at the moment each proposed elementary collapse is applied. An initially free face may cease to be relevant after earlier removals, while another face may become free. Reusing a stale eligibility list without checking the current complex can turn a valid first move into an invalid later move.
CHAPTER 8 OF 14 · Collapse and recover information
8. Count critical cells without overclaiming
Pairing preserves an alternating count
Let nₚ count original p-cells and mₚ count critical p-cells. Every matched pair has adjacent dimensions, so its contribution to the alternating count is zero: (−1)ᵖ + (−1)ᵖ⁺¹ = 0. Therefore the original Euler characteristic equals the alternating sum of the critical-cell counts.
For the triangular circle, three vertices minus three edges gives zero, while one critical vertex minus one critical edge also gives zero. For the filled square, four minus five plus two gives one, agreeing with a single critical vertex. These are independent arithmetic checks on the recorded pairs.
The converse fails dramatically. The invalid complete matching on the triangular circle leaves no critical cells, whose alternating sum is also zero. It passes the Euler-characteristic check while failing acyclicity. A necessary invariant can catch some mistakes without proving the entire construction correct.
Critical counts are bounds, not always Betti numbers
Over a chosen field, the number of critical cells in each dimension bounds the corresponding Betti number from above. Extra critical cells can interact through the boundary maps of the Morse complex. The counts become exact Betti numbers only in special situations, such as when the relevant reduced boundary maps vanish.
A tree with no pairs at all illustrates the point without advanced algebra. Every vertex and edge is critical under the dimension function, yet the tree still has only one connected component and no first homology. The critical counts describe available generators, not necessarily independent surviving homology classes.
The existing guide on critical-point bounds and Lusternik–Schnirelmann category develops a neighbouring lesson: a lower bound, a count for one chosen function and an optimum over all choices are different claims. Keeping those claims separate is useful in both smooth and discrete settings.
CHAPTER 9 OF 14 · Collapse and recover information
9. Recover the reduced boundary information
A smaller model still needs attaching data
Knowing that a reduction leaves two critical vertices and one critical edge does not tell you whether that edge joins the vertices or attaches both endpoints to the same vertex. Those possibilities have different component and loop behaviour. Cell counts need to be accompanied by information about how the reduced cells attach.
In a Morse chain complex, the boundary data are obtained using the matching and its gradient paths, with appropriate coefficients and signs. Over F₂, contributions combine modulo two. Over other coefficients, orientations cannot simply be ignored. A correct implementation must follow the chosen construction rather than copying the old boundary submatrix on unmatched cells.
A path A–B–C gives a small warning. Match B with AB, leaving A, C and BC critical. The reduced critical edge must connect A to C after the cancellation. Merely restricting the original boundary of BC to the unmatched vertices leaves only C, because B was removed. That is not the correct reduced boundary.
Verify the answer by a different route
The original path is connected and has no loop. The reduced chain complex should therefore have a boundary map of rank one from its one-dimensional chain group to its two-dimensional vector space of vertex chains. Its first Betti number is zero and its zeroth Betti number is one.
Over F₂, the correct reduced boundary is A + C. This has rank one and agrees with the geometric contraction of AB. The example is deliberately small: it reveals why cancellation must update relationships among surviving cells, even when the list of surviving cells itself is correct.
Keep a map back to original chains when the application needs representatives. A cycle expressed in reduced cells is not automatically a list of original mesh edges. Recovering an interpretable representative is a separate output requirement that should be included before deciding what reduction data can be discarded.
CHAPTER 10 OF 14 · Preserve the right structure
10. Preserve a filtration only with additional conditions
Final topology does not encode earlier events
Consider vertices A and B appearing at parameter zero and edge AB appearing at parameter five. Before five, the complex has two components. At five, they merge. Its ordinary H₀ persistence contains one finite interval [0,5) and one interval that continues indefinitely.
As an unfiltered space, the final interval AB collapses to a point. But replacing the entire filtered construction by a single vertex present from zero erases the finite interval. The final homotopy type is preserved while the persistence information is not. This counterexample shows exactly why an unfiltered reduction guarantee is insufficient.
For a filtered chain cancellation, matching cells at the same filtration value is a common sufficient compatibility condition when used within the appropriate filtered reduction construction. The Mischaikow–Nanda paper on Morse theory for filtrations develops the filtered construction. The chain maps and cancellation procedure must respect the filtration as well. A rule about equal numbers is not a replacement for the complete theorem and implementation contract.
Choose the preservation theorem before the optimisation
The official GUDHI edge-collapse documentation describes a specific reduction of filtered flag complexes that preserves persistent homology. That is a specialised guarantee for a specified construction. It should not be generalised to every operation called edge collapse in geometry software.
In an image application, the pore-connectivity specialist guide explains why filtration values may encode distance, intensity or a physical entry condition. Erasing an interval can therefore erase an event relevant to the question, even if the final object remains connected.
Before simplifying, write down whether the required output is final homology, homotopy type, a persistence module, geometric measurements or physical predictions. Then choose a method whose guarantee matches that output. A smaller structure is valuable only if it still answers the intended question.
CHAPTER 11 OF 14 · Preserve the right structure
11. Diagnose matching failures systematically
Check local validity before global validity
First verify that both cells in every pair exist, differ in dimension by one and have the required incidence. Next check that no cell appears in two pairs. Then construct the oriented Hasse diagram from the complete incidence relation and test acyclicity. Missing unmatched incidences can hide a cycle, so the graph construction itself needs verification.
If the directed graph is cyclic, return the cycle as a sequence of cell identifiers. Compare it with the triangular-frame counterexample. The repair may require removing a pair or revising several choices. Do not suppress the failing edge from the test graph merely because it was not selected by the matching routine; unmatched incidences are essential to the condition.
After validity passes, compare original and critical Euler characteristics. Independently calculate small-case homology. For an explicit collapse sequence, verify face closure after every removal. These checks serve different purposes and should be reported separately rather than combined into a single unexplained pass flag.
Separate a valid result from a good result
The empty matching is acyclic and valid. It leaves every cell critical, so it may offer no reduction. Validity therefore does not establish efficiency. Conversely, an impressive reduction ratio does not establish validity. The first question is whether the mathematical guarantee applies; only then is the amount of simplification meaningful.
Record original cell counts by dimension, matched pairs, critical counts, validation time and downstream computation time. A reduction that costs more than the calculation it accelerates may still help repeated analyses, but that needs a workload argument. Compare total costs for the actual usage pattern rather than timing only the final small matrix.
Tie-breaking rules also belong in reproducibility records. Two valid runs may produce different critical sets and different reduction sizes. Preserve the input order and seed if randomness is used, while testing correctness independently of those particular choices.
CHAPTER 12 OF 14 · Preserve the right structure
12. Connect to smooth theory without conflating definitions
Critical cells and smooth critical points are related ideas
Smooth Morse theory studies critical points of a differentiable function and the changes associated with their indices. Discrete Morse theory replaces that setting with combinatorial cells and incidence conditions. The analogy is powerful, but a discrete critical edge is not literally a point where an ordinary derivative vanishes.
The site’s Morse–Bott specialist article examines smooth critical submanifolds and normal Hessians. Those hypotheses belong to its smooth setting. A matching on a simplicial complex is checked using incidences and acyclicity, not by inventing a Hessian for every edge.
A sampled height field may motivate the construction of a discrete field, but the conversion needs a defined procedure. Equal vertex values, flat regions and cell extensions can change the resulting matching. Merely transferring the word gradient does not prove that a particular discrete assignment has the required properties.
Know what optimisation does and does not establish
Finding an acyclic matching is different from proving it has the fewest possible critical cells. A greedy method may stop at a valid but nonoptimal answer. An unsuccessful attempt to reduce further does not prove that no better matching exists.
For a graph, choosing a spanning tree in each component gives a transparent construction with one critical vertex per component and one critical edge per edge outside the forest. In higher-dimensional complexes, local choices can interact in more complicated ways. Avoid transferring the simplicity of the graph case into a universal claim about optimal reduction.
When a proof needs a specific critical vector, exhibit the matching and verify it. When a lower bound is needed, supply a separate argument. When an algorithm merely finds a candidate, label it as a candidate. This keeps the scope of the evidence aligned with the strength of the conclusion.
CHAPTER 13 OF 14 · Transfer and continue
13. Transfer the method when one new edge appears
Exercise: turn a tree into a loop with a tail
Start with edges AB, BC and CD on vertices A, B, C and D. Root the path at A, pairing B with AB, C with BC and D with CD. Now add edge AC, but no triangle ABC. Determine which critical cells remain if the original matching is kept, whether the matching is acyclic, and what topological feature the new edge contributes.
The original path has one critical vertex A. After AC is added, AC is also critical because it is unmatched. The existing pairs still lead toward A. The new edge has unmatched downward arrows to A and C; no arrow enters it from a matched vertex. It cannot close a directed cycle in the Hasse diagram. The matching remains acyclic.
The critical vector is (1,1). The original graph now has four vertices and four edges and is connected, so its cycle rank is 4 − 4 + 1 = 1. The triangle-shaped frame A–B–C–A contributes one loop, while the edge CD is a tail. The matching and the independent graph calculation agree.
Change the input again: fill the triangle
Include the filled simplex ABC. The previous matching leaves A, AC and ABC critical, giving counts (1,1,1). That is still a valid but less efficient description of a contractible complex. The critical edge and critical triangle need not represent surviving homology classes; their boundary interaction can remove the apparent loop.
A better explicit collapse sequence is to remove D–CD, then AB–ABC, then B–BC, then C–AC. Only A remains. At the second step, AB is a free face of the sole triangle. The subsequent graph is a path and can be collapsed from its leaves.
The transfer lesson is precise. Adding an edge can create a loop, while adding a face can fill it. A matching valid before the change may remain valid without remaining efficient. Recompute both the mathematical question and the quality of the reduction instead of assuming that a previously good matching is still optimal.
CHAPTER 14 OF 14 · Transfer and continue
14. Build a learning route and a trustworthy implementation
Is every matched pair safe to delete immediately?
No. An elementary collapse requires a free face in the current complex. A general acyclic matching supports a broader Morse-theoretic construction, whose reduced cells and attaching information must be handled correctly. Arbitrary deletion can break face closure or discard necessary boundary information.
Does one critical cell mean the original complex was one point?
It means the applicable Morse theorem provides a model with that critical-cell structure. If there is just one critical vertex and no other critical cells, the complex is homotopy equivalent to a point. It may still have many original simplices and substantial geometric extent. Homotopy equivalence does not preserve lengths, angles or the number of input records.
What should a beginner calculate first?
Begin with the interval function in Chapter 3. Check every inequality, including the deliberately invalid alternative. Then draw the oriented Hasse diagram for the triangular frame and find the closed path. Repair the matching and explain why one critical edge must remain in that construction.
Next reproduce the tree pairing and the filled-square collapse sequence without software. Write the coface counts before each collapse. Only after those examples are clear should you implement the incidence graph and cycle detector. Use separate routines for selecting a matching and checking it so that one mistaken assumption is less likely to affect both.
For a first research or engineering prototype, keep the original complex, the complete matching, a validity certificate or cycle report, critical counts, reduced boundary data and maps needed to recover representatives. Add filtration compatibility only when the application actually requires it, and test the two-vertex delayed-edge example before trusting a persistence-preserving claim.
The useful progression is from a visible pair to a global path condition, then from a count to a correctly attached smaller model. Return to Computational Topology to connect that model to homology calculations. The standard of understanding is being able to explain why a reduction works, identify what it preserves, and revise the argument when a new cell or filtration changes the problem.