# Computing Persistent Homology of Directed Flag Complexes
## 4 Materials and Methods  
### Mathematical Background  
In this section, we give a brief introduction to directed flag complexes of directed graphs, and to persistent homology. For more detail, see [6; 20; 21]. Definition 1: A graph \(G\) is a pair \((V,E)\), where \(V\) is a finite set referred to as the vertices of \(G\), and \(E\) is a subset of the set of unordered pairs \(e=\{v,w\}\) of distinct points in \(V\), which we call the edges of \(G\). Geometrically the pair \(\{u,v\}\) indicates that the vertices \(u\) and \(v\) are adjacent to each other in \(G\). A directed graph, or a digraph, is similarly a pair \((V,E)\) of vertices \(V\) and edges \(E\), except the edges are ordered pairs of distinct vertices, i.e., the pair \((v,w)\) indicates that there is an edge from \(v\) to \(w\) in \(G\). In a digraph we allow reciprocal edges, i.e., both \((u,v)\) and \((v,u)\) may be edges in \(G\), but we exclude loops, i.e., edges of the form \((v,v)\). Next we define the main topological objects considered in this article. Definition 2: An abstract simplicial complex on a vertex set \(V\) is a collection \(X\) of non-empty finite subsets \(\sigma\subseteq V\) that is closed under taking non-empty subsets. An ordered simplicial complex on a vertex set \(V\) is a collection of non-empty finite ordered subsets \(\sigma\subseteq V\) that is closed under taking non-empty ordered subsets. Notice that the vertex set \(V\) does not have to have any underlying order. In both cases the subsets \(\sigma\) are called the simplices of \(X\), and \(\sigma\) is said to be a \(k\)-simplex, or a \(k\)-dimensional simplex, if it consists of \(k+1\) vertices. If \(\sigma\in X\) is a simplex and \(\tau\subseteq\sigma\), then \(\tau\) is said to be a face of \(\sigma\). If \(\tau\) is a subset of \(V\) (ordered if \(X\) is an ordered simplicial complex) that contains \(\sigma\), then \(\tau\) is called a cface of \(\sigma\). If \(\sigma=(v_{0},\ldots,v_{k})\) is a \(k\)-simplex in \(X\), then the \(i\)-th face of \(\sigma\) is the subset \(\hat{o}_{i}(\sigma)=(v_{0},\ldots,\hat{o}_{i},\ldots,v_{k})\) where by \(\hat{o}_{i}\) we mean omit the \(i\)-th vertex. For \(d\geq 0\) denote by \(X_{d}\) the set of all \(d\)-dimensional simplices of \(X\). Notice that if \(X\) is any abstract simplicial complex with a vertex set \(V\), then by fixing a linear order on the set \(V\), we may think of each one of the simplices of \(X\) as an ordered set, where the order is induced from the ordering on \(V\). Hence any abstract simplicial complex together with an ordering on its vertex set determines a unique ordered simplicial complex. Clearly any two orderings on the vertex set of the same complex yield two distinct but isomorphic ordered simplicial complexes. Hence from now on we may assume that any simplicial complex we consider is ordered. Definition 3: Let \(G=(V,E)\) be a directed graph. The directed flag complex \(\operatorname{dFl}(G)\) is defined to be the ordered simplicial complex whose \(k\)-simplices are all ordered \((k+1)\)-cliques, i.e., \((k+1)\)-tuples \(\sigma=(v_{0},v_{1},\ldots,v_{k})\), such that \(v_{i}\in V\) for all \(i\), and \((v_{i},v_{j})\in E\) for \(i<j\). The vertex \(v_{0}\) is called the initial vertex of \(\sigma\) or the source of \(\sigma\), while the vertex \(v_{k}\) is called the terminal vertex of \(\sigma\) or the sink of \(\sigma\). Let \(\mathbb{F}\) be a field, and let \(X\) be an ordered simplicial complex. For any \(k\geq 0\) let \(C_{k}(X)\) be the \(\mathbb{F}\)-vector space with basis given by the set \(X_{k}\) of all \(k\)-simplices of \(X\). If \(\sigma=(v_{0},\ldots,v_{k})\) is a \(k\)-simplex in \(X\), then the \(i\)-th face of \(\sigma\) is the subset \(\partial_{i}(\sigma)=(v_{0},\ldots,\partial_{i},\ldots,v_{k})\), where \(\partial_{i}\) means that the vertex \(v_{i}\) is removed to obtain the corresponding \((k-1)\)-simplex.