# Computing Persistent Homology of Directed Flag Complexes
## 4 Materials and Methods
### Mathematical Background
For \(k\geq 1\), define the \(k\)-th boundary map \(d_{k}\colon C_{k}(X)\to C_{k-1}(X)\) by  
\[d_{k}(\sigma)=\sum_{i=0}^{k}(-1)^{i}\partial_{i}(\sigma)\in C_{k-1}(X).\]  
The boundary map has the property that \(d_{k}\circ d_{k+1}=0\) for each \(k\geq 1\)[21]. Thus \(\operatorname{Im}(d_{k+1})\subseteq\operatorname{Ker}(d_{k})\) and one can make the following fundamental definition:  
Definition 4: Let \(X\) be an ordered simplicial complex. The \(k\)-th homology group of \(X\) (over \(\mathbb{F}\)) denoted by \(H_{k}(X)=H_{k}(X;\mathbb{F})\) is defined to be  
\[H_{k}(X)=\operatorname{Ker}(d_{k})/\operatorname{Im}(d_{k+1}).\]  
If \(X\) is an ordered simplicial complex, and \(Y\subseteq X\) is a subcomplex, then the inclusion \(\iota\colon Y\to X\) induces a chain map \(\iota_{*}\colon C_{*}(Y)\to C_{*}(X)\), i.e., a homomorphism \(\iota_{k}\colon C_{k}(Y)\to C_{k}(X)\) for each \(k\geq 0\), such that \(d_{k}\circ\iota_{k}=\iota_{k-1}\circ d_{k}\). Hence one obtains an induced homomorphism for each \(k\geq 0\),  
\[\iota_{*}\colon H_{k}(Y)\to H_{k}(X).\]  
This is a particular case of a much more general property of homology, namely its functoriality with respect to so called simplicial maps. We will not however require this level of generality in the discussion below. Definition 5: A filtered simplicial complex is a simplicial complex \(X\) together with a filter function \(f\colon X\to\mathbb{R}\), i.e., a function satisfying the property that if \(\sigma\) is a face of a simplex \(\tau\) in \(X\), then \(f(\sigma)\leq f(\tau)\). Given \(b\in\mathbb{R}\sqcup\{\infty\}\), define the sublevel complex \(X[b]\) to be the inverse image \(f^{-1}\left((-\infty,b]\right)\). Notice that the condition imposed on the function \(f\) in Definition 5 ensures that for each \(b\in\mathbb{R}\sqcup\{\infty\}\), the sublevel complex \(X[b]\) is a subcomplex of \(X\), and if \(b\leq b^{\prime}\) then \(X[b]\subseteq X[b^{\prime}]\). By default we identify \(X\) with \(X[\infty]\). Thus a filter function \(f\) as above defines an increasing family of subcomplexes \(X[b]\) of \(X\) that is parametrised by the real numbers. If the values of the filter function \(f\) are a finite subset of the real numbers, as will always be the case when working with actual data, then by enumerating those numbers by their natural order we obtain a finite sequence of subspace inclusions  
\[X[1]\subseteq X[2]\subseteq\cdots\subseteq X[n]=X.\]For such a sequence one defines its persistent homology as follows: for each \(i\leq j\) and each \(k\geq 0\) one has a homomorphism  
\[h_{k}^{ij}\colon H_{k}(X[i])\to H_{k}(X[j]),\]  
induced by the inclusion \(X[i]\to X[j]\). The image of this homomorphism is a \(k\)-th persistent homology group of \(X\) with respect to the given filtration, as it represents all homology classes that are present in \(H_{k}(X[i])\) and carry over to \(H_{k}(X[j])\). To use the common language in the subject, \(\mathrm{Im}(h_{k}^{ij})\) consists of the classes that were \"born\" at or before filtration level \(i\) and are still \"alive\" at filtration level \(j\). The rank of \(\mathrm{Im}(h_{k}^{ij})\) is a persistent Betti number for \(X\) and is denoted by \(\beta_{k}^{i,j}\). Persistent homology can be represented as a collection of persistence pairs, i.e., pairs \((i,j)\), where \(0\leq i<j\leq n\). The multiplicity of a persistence pair \((i,j)\) in dimension \(k\) is, roughly speaking, the number of linearly independent \(k\)-dimensional homology classes that are born in filtration \(i\) and die in filtration \(j\). More formally,  
\[\mu_{k}^{ij}=(\beta_{k}^{i,j-1}-\beta_{k}^{i-1,j-1})-(\beta_{k}^{i,j}-\beta_{k }^{i-1,j}).\]  
Persistence pairs can be encoded in persistence diagrams or persistence barcodes. See [22] for more detail. Flagser computes the persistent homology of filtered directed flag complexes. The filtration of the flag complexes is based on filtrations of the 0-simplices and/or the 1-simplices, from which the filtration values of the higher dimensional simplices can then be computed by various formulas.