Subdivision bifiltration

Let ${\displaystyle T}$ be a simplicial complex. Then a nested sequence of simplices ${\displaystyle \sigma _{1}\subset \sigma _{2}\subset \cdots \subset \sigma _{k}}$ of ${\displaystyle T}$ is called a flag or chain of ${\displaystyle T}$. The set of all flags of ${\displaystyle T}$ comprises an abstract simplicial complex, known as the barycentric subdivision of ${\displaystyle T}$, denoted by ${\displaystyle \operatorname {Bary} (T)}$. The barycentric subdivision is naturally identified with a geometric subdivision of ${\displaystyle T}$, created by starring the geometric realization of ${\displaystyle T}$ at the barycenter of each simplex.^[9]

There is a natural filtration on ${\displaystyle \operatorname {Bary} (T)}$ by considering for each natural number ${\displaystyle k}$ the maximal subcomplex of ${\displaystyle \operatorname {Bary} (T)}$ spanned by vertices of ${\displaystyle \operatorname {Bary} (T)}$ corresponding to simplices of ${\displaystyle T}$ of dimension at least ${\displaystyle k-1}$, which is denoted ${\displaystyle {\tilde {\mathcal {S}}}(T)_{k}}$. In particular, by this convention, then ${\displaystyle {\tilde {\mathcal {S}}}(T)_{1}=\operatorname {Bary} (T)}$. Considering the sequence of nested subcomplexes given by varying the parameter ${\displaystyle k}$, we obtain a filtration on ${\displaystyle \operatorname {Bary} (T)}$ known as the subdivision filtration. Since the complexes in the subdivision filtration shrink as ${\displaystyle k}$ increases, we can regard it as a functor ${\displaystyle {\tilde {\mathcal {S}}}(-):\mathbb {N} ^{\operatorname {op} }\to \mathbf {Simp} }$ from the opposite posetal category ${\displaystyle \mathbb {N} ^{\operatorname {op} }}$ to the category ${\displaystyle \mathbf {Simp} }$ of simplicial complexes and simplicial maps.

Let ${\displaystyle P}$ be a partially ordered set. Given a simplicial filtration ${\displaystyle F:P\to \mathbf {Simp} }$, regarded as a functor from the posetal category of ${\displaystyle P}$ to the category ${\displaystyle \mathbf {Simp} }$, by applying the subdivision filtration object-wise on ${\displaystyle F}$, we obtain a two-parameter filtration ${\displaystyle {\mathcal {S}}(F):\mathbb {N} ^{\operatorname {op} }\times P\to \mathbf {Simp} }$, called the subdivision bifiltration.^[10]

In particular, when we take ${\displaystyle F}$ to be the Rips or Čech filtration, we obtain bifiltrations ${\displaystyle {\mathcal {S}}\operatorname {Rips} (-)}$ and ${\displaystyle {\mathcal {S}}\operatorname {{\check {C}}ech} (-)}$, respectively.

The subdivision-Čech bifiltration is weakly equivalent to the multicover bifiltration, implying that they have isomorphic persistent homology. A combinatorial proof of this statement was given in Sheehy's original conference paper, but a more algebraic version was presented in 2017 by Cavanna et al.^[11] The ideas from Cavanna's proof were later generalized by Blumberg and Lesnick in a 2022 paper on 2-parameter persistent homology.^[8]

By the size of a bifiltration, we mean the number of simplices in the largest complex. The subdivision-Čech bifiltration has exponential size as a function of the number of vertices.^[12] This implies that its homology cannot be directly computed in polynomial time. However, for points in Euclidean space, the homology of subdivision-Čech can be computed in polynomial time, up to weak equivalence, via a construction known as the rhomboid bifiltration. As a precursor to the rhomboid bifiltration, Edelsbrunner and Osang presented in 2021 a polyhedral cell complex called the rhomboid tiling, which they used to compute horizontal or vertices slices of the multicover bifiltration up to weak equivalence.^[13] This was extended a year later by Corbet et al. to the rhomboid bifiltration, which is weakly equivalent to the multicover bifiltration, but has polynomial size.^[12]