2024-03-14

I often visualize a filtration as a map $f:K\to \mathbb{R}$ such that $f(\tau )\le f(\sigma )$ when $\tau ⪯\sigma$. Bala gave the following definition in class:

Filtration

A filtration of a simp. complex $K$ is a nested sequence of subcomplexes of $K$: $\varnothing =K^0\subseteq K^1\subseteq \cdots \subseteq K^m=K.$

We can tie these two notions together by taking the preimage of $f$:

$$K^r=f^{-1}((-\infty ,r]).$$

Then by using the above construction for all $r\in \mathbb{R}$, we get a nested sequence of subcomplexes.

Question: Is “birth time” of a simplex $\sigma$, the smallest filtration value $r$ such that $\sigma \in K^r$?

I can implement this in scomplex by finding all unique filtration values $r$ and returning all subcomplexes constructed by adding all simplicies with filtration value $\le r$. Under the assumption $f(\tau )\le f(\sigma )$ when $\tau ⪯\sigma$, we can simply do a depth-first search stopping each branch once a filtration value is greater than $r$.

Computationally, finding the unique filtration values would be $O(n^2)$ and each subcomplex could be constructed in $O(n)$, where $n$ is the number of simplicies (this is a rough approximation as the construction time decreases as the filtration value decreases). Resulting in a total of $O(n^2+mn)$ where $m$ is the number of unique filtration values. Since $m\le n$, we get $O(n^2)$, i.e., the main bottle neck appears to be determining the unique filtration values.