6 Degree-0 Persistence

“The art of doing mathematics consists in finding that special case which contains all the germs of generality.” – David Hilbert

This chapter introduces persistence in its simplest form: tracking connected components as a function value sweeps across \mathbb{R}. No homology is required yet — degree-0 persistence is entirely about how path-connected components are born and merge. The concepts developed here carry over verbatim to all higher degrees once homology is in place.

Step	Object	Description
1	F(t)	Sublevel set — the part of X where f \leq t
2	\varphi(s,t)	Induced map — tracks where each component goes as t grows
3	b(c),\, d(c)	Birth and death times of a component
4	\mathrm{Barcode}(f)	Multiset of intervals encoding all births and deaths
5	\mathrm{Dgm}(f)	Persistence diagram — the barcode plotted in \mathbb{R}^2

6.1 Sublevel Set Filtrations

Input: f : X \to \mathbb{R}.

In order to understand the degree-0 topology of f, we want to look at the path-connected components of the excursion sets induced by f (called a filtration):

sublevel sets: f^{-1}((-\infty, t])
superlevel sets: f^{-1}([t, +\infty))

Assumption: f is tame, i.e., every excursion set has finitely many path-connected components (cc).

We define: F(t) := f^{-1}((-\infty, t]) \qquad \pi_0 F(t) := \{\text{cc of } F(t)\}

Observation. For any two reals s, t with s \leq t, we have that \forall\, c \in \pi_0 F(s), \exists!\, c' \in \pi_0 F(t) satisfying c \cap c' \neq \emptyset (in fact, c \subset c'). This is because connected components grow with t and are, by definition, pairwise disjoint. Thus, one can define an induced map \varphi(s,t) : \pi_0 F(s) \to \pi_0 F(t) that tells where each connected component of F(s) “goes” in F(t).

The following figure lets you explore the sublevel set filtration interactively. Choose a function and drag the threshold — or press animate — to watch components be born, merge, and die.

Figure 6.1 — sublevel set filtration and degree-0 persistence

threshold t = –

choose a function and drag the slider to explore

Exercise 6.1

Let f : \mathbb{R} \to \mathbb{R} be a smooth function with three local minima and two local maxima. Sketch the sublevel set filtration and identify all values of t at which \pi_0 F(t) changes.
Prove that \varphi(s,t) is always injective: distinct components of F(s) map to distinct components of F(t). Hint: components are disjoint and c \subset c' whenever \varphi(s,t)(c) = c'.
Show that \varphi(r,t) = \varphi(s,t) \circ \varphi(r,s) for all r \leq s \leq t.

6.2 Birth Times, Death Times, and Barcodes

Birth and Death Times

Given t \in \mathbb{R} and c \in \pi_0 F(t), we define

Birth time: b(c) := \inf \{s \leq t \mid c \in \mathrm{Im}\,\varphi(s,t)\}
Death time: d(c) := \sup \bigl\{u \geq t \;\big|\; \forall\, c' \in \varphi(t,u)^{-1}(\{\varphi(t,u)(c)\}),\; b(c') \geq b(c)\bigr\}

The interval [b(c), d(c)] is the bar corresponding to c in the barcode of f.

When two components merge, the younger one dies — the one born at the higher function value is absorbed into the one born at the lower value. This convention is the Elder Rule, and it makes the birth–death pairing unique.

Barcode

The barcode of f is the multiset of intervals \mathrm{Barcode}(f) := \{[b(c),\, d(c)] \mid c \in \mathcal{C}\} where \mathcal{C} := \{c \mid c \in \pi_0 F(t) \text{ for some } t \in \mathbb{R}\} / {\sim}, and for t \leq u and c \in \pi_0 F(t), c' \in \pi_0 F(u): c \sim c' \iff \varphi(t,u)(c) = c' \text{ and } u \leq d(c). Exactly one bar extends to +\infty, corresponding to the oldest component — born at the global minimum of f.

Persistence Diagram

The persistence diagram of f (in degree 0) is the multiset \mathrm{Dgm}(f) := \{(b(c),\, d(c)) \in \mathbb{R}^2 \mid c \in \mathcal{C}\} plotted in the birth–death plane. All points satisfy b(c) \leq d(c) and lie on or above the diagonal b = d.

The persistence of a component is \mathrm{pers}(c) = d(c) - b(c). Points far from the diagonal are long-lived topological features; points near the diagonal are noise.

Exercise 6.2 Consider f : \{a, b, c, d, e\} \to \mathbb{R} defined on the path graph a - b - c - d - e, with values:

Point	a	b	c	d	e
f	1	3	2	4	5

Each edge takes value \max of its endpoints. Trace the filtration:

t	Event	\pi_0 F(t)	Action
1	Vertex a enters	\{a\}	Born at b = 1
2	Vertex c enters	\{a\},\, \{c\}	Born at b = 2
3	Vertex b + edges ab, bc enter	\{a,b,c\}
4	Vertex d + edge cd enters
5	Vertex e + edge de enters

Complete the Action column for t = 3, 4, 5, recording each bar as it closes.
Write out \mathrm{Barcode}(f).
Plot \mathrm{Dgm}(f) in the birth–death plane.
Which bars survive a persistence threshold of \varepsilon = 1.5?

6.3 Superlevel Set Filtrations

The superlevel set filtration \{F^+(t)\} with F^+(t) = f^{-1}([t,+\infty)) grows as t decreases. All definitions carry over:

Components are born at local maxima of f.
Components die when they merge at saddles.
The Elder Rule applies: the younger component (born at a lower maximum) dies.
Exactly one bar extends to -\infty, corresponding to the global maximum.

Duality

Degree-0 superlevel persistence of f equals degree-0 sublevel persistence of -f: \mathrm{Dgm}_{+}(f) = \{(-d, -b) \mid (b,d) \in \mathrm{Dgm}(-f)\}. In particular, all algorithms for sublevel sets apply directly to superlevel sets by negating the function.

Exercise 6.3

Compute the superlevel set barcode for the same function f from the previous exercise.
Verify the duality above by checking that \mathrm{Dgm}_+(f) equals the image of \mathrm{Dgm}(-f) under (b,d) \mapsto (-d,-b).
Give one application where superlevel persistence is more natural than sublevel persistence, and one where the reverse holds.

6.4 Computing Degree-0 Persistence

Input: Graph (V, E), and a map f : V \sqcup E \to \mathbb{R}.

Hypothesis: f gives us a graph filtration, that is for any (u,v) \in E where u, v \in V, we have f((u,v)) \geq \max\{f(u), f(v)\}.

Pre-processing: Sort V \sqcup E by increasing lexicographic order (value of f, dimension). It gives a sequence (\sigma_1, \ldots, \sigma_m) of vertices and edges. Then initialise a union–find data structure \mathcal{V}.

for i = 1 … m do
  if σᵢ is a vertex v then
    Create new entry eᵥ := {v} in 𝒱          // birth of a new cc
  else  // σᵢ is an edge (u, v)
    Find entries eᵤ, eᵥ containing u and v in 𝒱
    if eᵤ ≠ eᵥ then  // assume wlog f(eᵤ) ≤ f(eᵥ)
      Merge eᵥ into eᵤ in 𝒱
      Record interval [f(eᵥ), f((u,v))] in the barcode
    end
  end
end

Post-processing: For any e_v remaining in \mathcal{V}, record [f(e_v), +\infty).

Running time:

Pre-processing: \mathcal{O}(m \log m)
Main: \mathcal{O}(m\,\alpha(m)), where \alpha is the inverse Ackermann function
Post-processing: \mathcal{O}(m)

Exercise 6.4

Trace through the algorithm on the graph from the previous section. Write the state of \mathcal{V} after each step \sigma_i and verify you recover \mathrm{Barcode}(f) = \{[2,3],\,[4,5],\,[1,+\infty)\}.
Explain why the Elder Rule (merging e_v into e_u when f(e_u) \leq f(e_v)) is the correct choice. What would go wrong if we merged the older component into the younger?
Construct a small example where f((u,v)) < \max\{f(u), f(v)\} for some edge. Show that the algorithm produces an incorrect barcode when the graph filtration condition is violated.
How would you modify the algorithm to compute the superlevel set barcode directly, without negating f?

6.5 Stability

Stability Theorem (Cohen-Steiner, Edelsbrunner, Harer 2007)

For any tame functions f, g : X \to \mathbb{R}, d_B^\infty\!\left(\mathrm{Dgm}(f),\, \mathrm{Dgm}(g)\right) \leq \|f - g\|_\infty where d_B^\infty is the bottleneck distance: the infimum over all matchings between points of the two diagrams (with unmatched points moved to the diagonal) of the maximum displacement.

An immediate consequence: if \|f - g\|_\infty \leq \varepsilon, then every bar of persistence > 2\varepsilon is guaranteed to have a corresponding bar in \mathrm{Dgm}(g). Features that outlive the noise level are stable.

Exercise 6.5

Let f have barcode \{[1,4],\,[2,3],\,[0,+\infty)\} and let g = f + 0.5 (a constant shift). Compute \mathrm{Dgm}(g) directly and verify the stability bound.
If \|f - g\|_\infty = \varepsilon, what is the minimum persistence a bar of f must have to be guaranteed to appear (possibly shifted) in \mathrm{Dgm}(g)?
The stability theorem uses the bottleneck distance d_B^\infty. Would the result still hold with the p-Wasserstein distance W_p for p < \infty? (We will return to this in the chapter on metrics on diagram spaces.)

6.6 References

Cohen-Steiner, D., Edelsbrunner, H., Harer, J. (2007). Stability of persistence diagrams. Discrete & Computational Geometry 37, 103–120.
Edelsbrunner, H., Letscher, D., Zomorodian, A. (2002). Topological persistence and simplification. Discrete & Computational Geometry 28, 511–533.
Oudot, S. (2015). Persistence Theory: From Quiver Representations to Data Analysis. AMS.
Edelsbrunner, H. & Harer, J. (2010). Computational Topology: An Introduction. AMS. Chapter VII.