First Betti number of the path homology of random directed graphs

Thomas Chaplin

doi:10.1007/s41468-022-00108-3

Chaplin, Thomas

2022-12-04 00:00:00

Path homology is a topological invariant for directed graphs, which is sensitive to their asymmetry and can discern between digraphs which are indistinguishable to the directed ﬂag complex. In Erdos–Rén ˝ yi directed random graphs, the ﬁrst Betti number undergoes two distinct transitions, appearing at a low-density boundary and vanish- ing again at a high-density boundary. Through a novel, combinatorial condition for digraphs we describe both sparse and dense regimes under which the ﬁrst Betti number of path homology is zero with high probability. We combine results of Grigor’yan et al., regarding generators for chain groups, with methods of Kahle and Meckes in order to determine regimes under which the ﬁrst Betti number is positive with high prob- ability. Together, these results describe the gradient of the lower boundary and yield bounds for the gradient of the upper boundary. With a view towards hypothesis testing, we obtain tighter bounds on the probability of observing a positive ﬁrst Betti number in a high-density digraph of ﬁnite size. For comparison, we apply these techniques to the directed ﬂag complex and derive analogous results Keywords Path homology · Directed ﬂag complex · Stochastic topology · Directed graphs · Random graphs Mathematics Subject Classiﬁcation 05C20 · 05C80 · 55U15 · 60C05 · 62F03 1 Introduction In applications, networks often arise with asymmetry and directionality. Chemical synapses in the brain have an intrinsic direction (see (Purves et al. 2018, §5)); gene regulatory networks record the causal effects between genes (e.g. Aalto et al. 2020); B Thomas Chaplin thomas.chaplin@maths.ox.ac.uk Mathematical Institute, University of Oxford, Woodstock Rd, Oxford OX2 6GG, Oxfordshire, UK 123 T. Chaplin communications in social networks have a sender and a recipient (e.g. Leskovec and Krevl 2014). A common hypothesis is that the structure of a network determines its function (Ingram et al. 2006; Reimann et al. 2017), at least in part. In order to investigate such a claim, one requires a topological invariant which describes the structure of the network. To obtain such a summary for a digraph, one often symmetrises to obtain an undirected graph, before applying traditional tools from TDA (e.g. Helm et al. 2021). This potentially inhibits the predictive power of the descriptor, since the pipeline becomes blind to the direction of edges. In recent years, particularly in applications related to neuroscience (e.g. Caputi et al. 2021; Reimann et al. 2017), researchers have explored the use of topological methods which are sensitive to the asymmetry of directed graphs. A much-studied construction, for undirected graphs, is the clique complex (or ﬂag complex)—a simplicial complex in which the k-simplices are the (k +1)-cliques in the underlying graph. An obvious extension to the case of directed graphs is the directed ﬂag complex (Lütgehetmann et al. 2020). This is an ordered simplicial complex in which the ordered k-simplices are the (k +1)-directed cliques: (k +1)-tuples of distinct vertices (v ,...,v ) such that v → v whenever i < j. An important property of 0 k i j this construction is that is able to distinguish between directed graphs with identical underlying, undirected graphs; it is sensitive to the asymmetry of the digraph. Path homology (ﬁrst introduced by Grigor’yan et al. (2012)) provides an alternative construction which, while more computationally expensive, is capable of distinguish- ing between digraphs which are indistinguishable to the directed ﬂag complex (e.g. Fig. 1, c.f. Chowdhury and Mémoli (2018)). Moreover, the non-regular chain complex, from which path homology is deﬁned, contains the directed ﬂag complex as a subcom- plex. Intuitively, the generators of the kth chain group of the directed ﬂag complex are all the directed paths, of length k, such that all shortcut edges are present in the graph. Whereas, the kth chain group of the non-regular chain complex consists of all linear combinations of directed paths, of length k, such that any missing shortcuts of length (k − 1) are cancelled out. Other desirable features of path homology include good functorial properties in an appropriate digraph category (Grigor’yan et al. 2014, 2020) and invariance under an appropriate notion of path homotopy (Grigor’yan et al. 2014, Theorem 3.3). Fur- thermore, path homology is a particularly novel method since it operates directly on directed paths within the digraph, rather than ﬁrst constructing a simplicial complex. Rather than being freely generated by distinguished motifs, the chain groups for path homology are formed as the pre-images of the boundary maps. As such, ﬁnding a basis for the chain groups is often non-trivial, which complicates the understanding Fig. 1 Two motifs which are j k indistinguishable to the directed ﬂag complex but have different path homology m i (b) (a) 123 First Betti number of the path homology of random... of how homology arises in a random digraph. Hence, it is desirable to develop an understanding of the statistical behaviour of path homology, both from an applied perspective and from independent interest. Key questions include (as discussed for the clique complex in Kahle 2009; Kahle et al. 2014; Kahle and Meckes 2013): when should one expect homology to be trivial or non-trivial; when homology is non-trivial, what are the expected Betti numbers; and how are the Betti numbers distributed? Notation 1.1 Assume G is disturbed according to a null model depending only on n, e.g. after assuming all other parameters are functions of n. 1. We say a property P holds with high probability, if property P holds with proba- bility tending to 1 as n →∞. 2. Given two random variables X , Y , depending on G, we write X ∼ Y with high probability if for any > 0 P 1 − ≤ ≤ 1 + →1as n →∞. (1.1) To date, traditional topological invariants enjoy a greater statistical understanding in the context of basic null models. In particular, Kahle showed the following: Theorem 1.2 (Kahle 2009; Kahle et al. 2014) For an Erdos–Rényi ˝ random undirected graph G ∼ G(n, p), denote the kth Betti number (over a ﬁeld of characteristic 0) of its clique complex X(G) by β . Let f denote the number of k-cliques then k k k+1 n α ( ) E[ f ] = p . Assume p = n , then k+1 1. if −1/k <α < −1/(k + 1) then β ∼ E[β ]∼ E[ f ]∼ f with high probability; k k k k 2. if −1/k <α < −1/(k + 1) then β > 0 with high probability; 3. if α< −1/k then β = 0 with high probability; 4. if α> −1/(k + 1) then β = 0 with high probability. In essence, this characterises the understanding that, in any given degree, ran- dom graphs only have non-trivial, clique complex homology in a ‘goldilocks’ region, wherein graph density is neither too big nor too small. Moreover, the boundaries of this region are dependent on the number of nodes in the graph, scaling as a power law. Our primary contribution is a similar description for two different ﬂavours of path homology, in degree 1. 1.1 Summary of results In order to derive useful probability bounds, it is often necessary to prescribe a null model which is highly symmetric and depends on few parameters. Therefore, through- out this paper we will be focusing on an Erdos–Rén ˝ yi random directed graph model, in which the number of nodes is ﬁxed (at n) and each possible directed edge appears independently, with some probability p. Note, this model allows for the existence of a reciprocal pair of directed edges. 123 T. Chaplin Although individual results are potentially stronger, the following theorems charac- terise the theoretical understanding that we will develop. Denote the kth Betti number − → − → of the non-regular path homology of a digraph by β . Firstly, ( β + 1),isthe k 0 number of weakly connected components. This coincides with the number of con- nected components of the ﬂat symmetrisation of the digraph (see Deﬁnition 2.10). If − → G ∼ G (n, p) is an Erdos–Rén ˝ yi random directed graph then its symmetrisation is an Erdos–Rén ˝ yi random undirected graph, G ∼ G(n, p ¯), where p ¯ = 1 − (1 − p) . Thus, we use a standard result due to Erdos ˝ and Rényi (1960), Kahle (2009) to prove the following. − → − → Theorem 1.3 For an Erdos–Rényi ˝ random directed graph G ∼ G (n, p(n)),let β denote the 0th Betti number of its non-regular path homology over Z. Assume 1 − (1 − p(n)) = (log(n) + f (n))/n, then − → 1. if lim f (n) =−∞ then β > 0 with high probability; n→∞ 0 − → 2. if lim f (n) =∞ then β = 0 with high probability. n→∞ 0 The same result holds for regular path homology. Our primary contribution identiﬁes a similar ‘goldilocks’ region for the ﬁrst Betti − → number of path homology, β . − → − → Theorem 1.4 For an Erdos–Rényi ˝ random directed graph G ∼ G (n, p(n)),let β denote the 1st Betti number of its non-regular path homology over Z. Let N denote the number of edges, N = #E (G), then E[N ]= n(n − 1)p. Assume p(n) = n , 1 1 then − → − → 1. if −1 <α < −2/3 then β ∼ E[ β ]∼ E[N ]∼ N with high probability; 1 1 1 1 − → 2. if −1 <α < −2/3 then β > 0 with high probability; − → 3. if α< −1 then β = 0 with high probability; − → 4. if α> −1/3 then β = 0 with high probability. The same result holds for regular path homology. − → By way of justifying the assumption p(n) = n ,inFig. 9aweplot P[ β (G) = − → 0],for G ∼ G (n, p), in colour against log(n) and log(p) along the two spatial axes. We observe two transitions between three distinct regions in parameter space. − → There is an interim region, in which we observe mostly β > 0; when p becomes − → too small we suddenly observe mostly β = 0, and likewise when p becomes too large. On this plot, the boundaries between the three regions appear as straight lines. Hence a reasonable conjecture is that these boundaries follow a power-law relationship log(p) = α log(n)+c. Therefore, following power-law trajectories through parameter − → − → space will allow us to derive either P[ β (G)> 0]→ 1or P[ β (G) = 0]→ 1. 1 1 Turning our attention to higher degrees, we provide weak guarantees for the asymp- − → totic behaviour of β , for arbitrary k ≥ 1, at low densities. − → − → Theorem 1.5 For an Erdos–Rényi ˝ random directed graph G ∼ G (n, p(n)),let β denote the kth Betti number of its non-regular path homology over Z. Assume p(n) = 123 First Betti number of the path homology of random... − → α N +1 n with α< − for some N ∈ N. Then, β = 0 with high probability for every k ≥ N . The same result holds for regular path homology. For comparison, in Sect. 5, we apply the techniques used to prove Theorem 1.4 in order to obtain analogous results for the directed ﬂag complex. − → Theorem 1.6 For an Erdos–Rényi ˝ random directed graph G ∼ G (n, p(n)),let β denote the kth Betti number of its directed ﬂag complex homology over Z. Let N − → denote the number of directed k-cliques, N = rank X (G), then E[N ] = (k + k k k k+1 k+1 ( ) α 1)! p . Assume p(n) = n , then for each k ≥ 0 1. if −1/k <α < −1/(k + 1) then E[β ]∼ E[N ]; k k 2. if −1 <α < −1/2 then β ∼ E[β ]∼ E[N ] ∼ N with high probability; 1 1 1 1 3. if −1 <α < −1/2 then β > 0 with high probability; 4. if α< −1 then β = 0 with high probability; 5. if α> −1/4 then β = 0 with high probability. In Sect. 6, we summarise these results and compare path homology and the directed ﬂag complex to more traditional symmetric methods. We provide Table 1 in which we record, for each of the homologies under consideration, the α-region in which we know β is either zero or positive, with high probability (assuming p = n ). In Appendix A, with a view towards hypothesis testing, we derive a tighter explicit − → bound for P( β (G)> 0), which becomes useful when p is large. In order to identify a given Betti number as statistically signiﬁcant, against a Erdos–Rén ˝ yi null model, one would usually resort to a Monte Carlo permutation test (e.g. Dwass 1957). This would require the computation of path homology for a large number of random graphs. For large graphs (n ≥ 100 nodes), this is often infeasible, due to the computational complexity of path homology. However, if graph density falls into one of the regions identiﬁed by the results in Appendix A, one can potentially circumvent this costly computation. 2 Background 2.1 Graph theory definitions and assumptions For clarity, we present a number of standard deﬁnitions, and assumptions that we will use throughout this paper. First, we ﬁx our notation for graphs. Deﬁnition 2.1 1. A (undirected) graph is a pair G = (V , E ), where V is an arbitrary set and E is a set of 2-element subsets of V . 2. A directed graph (or digraph) is a pair G = (V , E ), where V is an arbitrary set and E ⊆ V × V . 3. A (resp. directed) multigraph is a (resp. directed) graph G = (V , E ) in which E is allowed to be a multiset. 4. In all cases, we call V (G) := V the set of nodes or vertices and E (G) := E the set of edges. 123 T. Chaplin 5. A digraph G = (V , E ) is simple if E ⊆ (V × V ) \ , where := {(i , i ) | i ∈ V }. 6. The density of a simple digraph G = (V , E ) is the ratio of edges present, relative to the maximum number of possible edges: #E density(G) := . (2.1) #V (#V − 1) Assumption 2.2 Throughout this paper, unless stated otherwise, we assume that all digraphs G = (V , E ) are simple. This means that they contain no self loops and contain at most one edge between any ordered pair of vertices. Given a directed graph G, we make the following deﬁnitions to refer to subgraphs within G. Deﬁnition 2.3 Givenadigraph G = (V , E ), we make the following deﬁnitions. 1. A subgraph is another graph G = (V , E ) such that V ⊆ V and E ⊆ E;we denote this as G ⊆ G. 2. Given a subgraph G ⊆ G and a subset of edges E ⊆ E (G) we let G ∪ E 1 2 1 2 denote a new graph with edges E (G ∪ E ) = E (G ) ∪ E . (2.2) 1 2 1 2 and node-set V (G ∪E ), the smallest superset of V (G ) that contains all endpoints 1 2 1 of edges in E . 3. A (combinatorial) undirected walk is an alternating sequences of vertices and edges ρ = (v , e ,v , e ,...,v , e ,v ) (2.3) 0 1 1 2 n−1 n n such that edges connect adjacent vertices, in either direction. That is, for each i, either e = (v ,v ) or e = (v ,v ). i i −1 i i i i −1 4. A (combinatorial) directed walk is an undirected walk such that all edges are forward edges, that is e = (v ,v ) for every i. i i −1 i 5. A (combinatorial) directed/undirected path is a directed/undirected walk which never repeats vertices or edges, that is v = v or e = e implies i = j. i j i j 6. A (combinatorial) directed/undirected cycle is a directed/undirected walk such that v = v , i = j ⇐⇒ {i , j}={0, n}. (2.4) i j 7. The length of a walk is the number of edges it traverses, e.g. the length of ρ in equation (2.3)is n. 8. A double edge is an unordered pair of vertices {i , j } ⊆ V such that both directed edges are in the graph, i.e. (i , j ), ( j , i ) ∈ E. Notation 2.4 1. For vertices i , j ∈ V , we write i → j if (i , j ) ∈ E. 2. If E ={e} is a singleton then we deﬁne G ∪ e := G ∪ E . 2 1 1 2 Remark 2.5 Assumption 2.2 allows for the existence of double edges. 123 First Betti number of the path homology of random... 2.2 Analytic and algebraic definitions Next, we provide deﬁnitions of ‘Landau symbols’, which we use describe the asymp- totic behaviour of two functions, relative to one another. Notation 2.6 Given two functions f , g : N → R we write f (n) 1. f (n) = o(g(n)) if lim = 0; n→∞ g(n) g(n) 2. f (n) = ω(g(n)) if lim = 0; n→∞ f (n) f (n) 3. f (n) ∼ g(n) if lim = 1. n→∞ g(n) Remark 2.7 1. There is an equivalence, f (x ) = ω(g(x )) ⇐⇒ g(x ) = o( f (x )). 2. Note that, if X and Y are deterministic random variables then X ∼ Y with high probability if and only if X ∼ Y in the sense above. Finally, we make a formal, algebraic deﬁnition, which will be required later in order to deﬁne path homology. Deﬁnition 2.8 Given a ring R and a set V,welet RV denote the R-module of formal R-linear combinations of elements of V . That is, RV := α e | n ∈ N,α ∈ R,v ∈ V (2.5) i v i i i =1 where {e | v ∈ V } are formal symbols which form a basis of the free R-module RV . 2.3 Erdos–Rényi random graphs Throughout this paper, we will primarily be investigating random directed graphs under an Erdos–Rén ˝ yi model. Deﬁnition 2.9 1. The Erdos–Rényi ˝ random undirected graph model, G(n, p),isa probability space of undirected graphs. Each graph has exactly n nodes {1,..., n} and each directed edge is included, independently, with probability p.Agiven graph G on n nodes with m edges appears with probability m −m ( ) p (1 − p) . (2.6) For a graph drawn from this model, we write G ∼ G(n, p). − → 2. The Erdos–Rényi ˝ random directed graph model, G (n, p), is a probability space of directed graphs. Each graph has exactly n nodes {1,..., n} and each directed edge is included, independently, with probability p. A given digraph G on n nodes with m edges appears with probability m n(n−1)−m p (1 − p) . (2.7) − → For a digraph drawn from this model, we write G ∼ G (n, p). 123 T. Chaplin 2.4 Symmetrisation Deﬁnition 2.10 Given a directed graph G = (V , E ), ¯ ¯ 1. the ﬂat symmetrisation is an undirected graph, G := (V , E ), where {i , j}∈ E with multiplicity 1 ⇐⇒ (i , j ) ∈ E or ( j , i ) ∈ E or both. (2.8) ◦ ◦ 2. the weak symmetrisation is an undirected multigraph G := (V , E ), where {i , j } appears in E with multiplicity 2 if both (i , j ) ∈ E and ( j , i ) ∈ E, or with multi- plicity if 1 if only one of these edges is present. Remark 2.11 We can view G and G as topological spaces by giving them the natural structure of a simplicial complex and delta complex respectively. Both of these struc- tures have no simplices above dimension 1, so clearly β (G) = β (G) = 0 for all k k k > 1. − → Lemma 2.12 Given a random directed graph G ∼ G (n, p), the ﬂat symmetrisation is distributed as G ∼ G(n, p ¯) where 2 2 p ¯ := 1 − (1 − p) = 2 p − p . (2.9) Proof A given undirected edge {i , j } appears in G if and only if at least one of (i , j ) or ( j , i ) is in G. Therefore P({i , j } ∈ / E ) = P (i , j)/ ∈ E and ( j , i)/ ∈ E = (1 − p) . (2.10) Hence, the undirected edge appears with probability 1 − (1 − p) . The existence of each undirected edge depends on the existence of a distinct pair of directed edges. Hence each undirected edge appears independently. Remark 2.13 Since we always assume p → 0, note that p ¯ ∼ 2 p. This clearly implies −1/k −1/k that p = o(n ) ⇐⇒ p ¯ = o(n ). Deﬁnition 2.14 Throughout this paper, we deﬁne p ¯ as in (2.9), whenever the under- lying p is clear from context. Deﬁnition 2.15 Given an undirected graph G = (V , E ), 1. a k-clique is a subset of vertices V ⊆ V , such that #V = k and for any two, distinct vertices, i , j ∈ V , the edge between them is present, i.e. {i , j}∈ E; 2. the clique complex, X(G) is a simplicial complex where the k-simplices are the (k + 1)-cliques in G. We now investigate the behaviour of these ‘symmetric methods’ on random directed − → graphs. Since the ﬂat symmetrisation of a random digraph G (n, p) is a random graph G(n, p ¯) and the asymptotics of p ¯ do not differ greatly from those of p, Theorem 1.2 123 First Betti number of the path homology of random... can be restated immediately for β (X(G)) with the only change being that E[ f ]= k k k+1 ( ) p ¯ . k+1 Next, we prove that if p = p(n) shrinks too quickly then β will vanish for G and G, with high probability. This is a special case of the proof given by Kahle (Kahle (2009), Theorem 2.6). We repeat the proof to illustrate that it can be applied to β (G), − → β (G) and, later on, path homology β (G). 1 1 −1 Proposition 2.16 If p = p(n) = o(n ) then, given a random directed graph G ∼ − → G (n, p), we have lim P(β (G) = 0) = lim P(β (G) = 0) = 1. (2.11) 1 1 n→∞ n→∞ Proof Note that the existence of an undirected cycle in G of length L ∈[3, n] is a necessary condition for β (G)> 0. For each L, by a union bound, the probability of there being an undirected cycle of length L is at most (n p ¯) . Hence, the probability that there is an undirected cycle of any length is at most (n p ¯) /(1 − (n p ¯)). The assumption −1 p = o(n ) implies that lim (n p ¯) = 0 and hence the bound converges to 0 as n→∞ n →∞. − → To prove β (G) = 0 with high probability, all that remains is to bound probability of there being an undirected cycle on 2 nodes (i.e. a double edge) in G. The probability 2 2 2 that there is some double edge is at most p ≤ n p which tends to 0 since −1 p = o(n ). Finally, we investigate conditions under which we expect β (G)> 0 and β (G)> 1 1 0 with high probability, and determine the growth rate of E[β ] in each situation. Standard techniques, as employed for the clique complex in Kahle (2009), shows the following. −1 Proposition 2.17 If p = p(n) = ω(n ) then, given a random directed graph G ∼ − → G (n, p), E[β (G)]∼ p ¯ and E[β (G)]∼ n(n − 1)p. (2.12) 1 1 ◦ ◦ ¯ ¯ Moreover, β (G) ∼ E[β (G)] and β (G) ∼ E[β (G)] with high probability and 1 1 1 1 hence lim P(β (G)> 0) = lim P(β (G)> 0) = 1. (2.13) 1 1 n→∞ n→∞ Proof Denoting the original digraph G = (V , E ), we deal with the ﬂat symmetrisation ﬁrst. For convenience, we deﬁne N := #E and N := #V . Note that E[N ] = p ¯ 1 0 1 and E[N ] = n. A standard application of the Euler characteristic shows N − N ≤ β ≤ N . (2.14) 1 0 1 1 123 T. Chaplin −1 The assumption p(n) = ω(n ) yields E[N ] = o(E[N ]) and hence E[β ]∼ E[N ]. 0 1 1 1 Now we show β ∼ E[β ] with high probability. Since E[β ]∼ E[N ] →∞,by 1 1 1 1 an application of Chebyshev’s inequality Alon and Spencer (2016), it sufﬁces to show that Var(β ) = o(E[β ] ). Using the inequalities (2.14) we can (eventually) bound 1 1 2 2 2 Var(β ) E[β ]− E[β ] E N − E[N − N ] 1 0 1 1 1 1 = ≤ . (2.15) 2 2 2 E[β ] E[β ] E[N − N ] 1 1 1 0 Then since N is a binomial random variable with mean E[N ] →∞ we have 1 1 2 2 2 2 E N ∼ E N . We have already seen that E N ∼ E N − N and hence [ ] [ ] [ ] 1 1 1 0 the bound in (2.15) tends to 0. Now since β ∼ E[β ] with high probability and eventually E[β ] > 0, the ﬁnal 1 1 1 conclusion β > 0 with high probability follows because for any ∈ (0, 1) we can eventually bound ¯ ¯ P β (G)> 0 ≥ P β (G) ≥ (1 − )E[β ] → 1. (2.16) 1 1 1 The case for the weak symmetrisation has an identical proof, except that E[#E]= E[#E] = n(n − 1)p. 3 Path homology of directed graphs 3.1 Definition Path homology was ﬁrst introduced by Grigor’yan et al. (2012, 2020). The key concept behind path homology is that, in order to capture the asymmetry of a digraph, we should not construct a simplicial complex, but instead a path complex. In a simplicial complex, one can remove any vertex from a simplex and obtain a new simplex in the complex. This property may not hold for directed paths in digraphs; if we bypass a vertex in the middle of a path then we may not obtain a new path. However, we can always remove the initial or ﬁnal vertex of a path and obtain a new path. This is the deﬁning property of a path complex (Grigor’yan et al. (2012), §1). Path homology can be deﬁned on any path complex but for this paper we focus on the natural path complex associated to a digraph. Throughout this section we ﬁx a ring R and a simple digraph G = (V , E ). Deﬁnition 3.1 We make the following deﬁnitions to classify sequences of vertices in V : 1. Any sequence v ...v of (p + 1) vertices v ∈ V is an elementary p-path. 0 p i 2. An elementary path is regular if no two consecutive vertices are the same, i.e. v = v for every i. Otherwise, the path is called non-regular or irregular. i i +1 3. An elementary path is allowed if subsequent vertices are joined by a directed edge in the graph, i.e. (v ,v ) ∈ E for every i. i i +1 Remark 3.2 An allowed path coincides with a combinatorial, directed walk. 123 First Betti number of the path homology of random... Deﬁnition 3.3 The following R-modules are deﬁned to be freely generated by the generators speciﬁed, for p ≥ 0: := (G; R) := R v ...v elementary p-path on V (3.1) p p 0 p R := R (G; R) := R v ...v regular p-path on V (3.2) p p 0 p A := A (G; R) := R v ...v allowed p-path in G (3.3) p p 0 p For p =−1, we let := R := A := R. Given an elementary p-path v ...v , −1 −1 −1 0 p the corresponding generator of is denoted e . For convenience, given an edge p v ...v 0 p τ = (a, b) ∈ E (G) we deﬁne e := e as an alias for the basis element of A . τ ab 1 We can construct homomorphisms → for each p. p p−1 Deﬁnition 3.4 Given p > 0, we can deﬁne the non-regular boundary map ∂ : → p p by setting p−1 ∂ (e ) := (−1) e (3.4) p v ...v 0 p v ...vˆ ...v 0 i p i =0 where v ... vˆ ...v denotes the elementary (p − 1)-path v ...v with the vertex v 0 i p 0 p i omitted. This deﬁnes ∂ on a basis of , from which we extend linearly. In the case p p p = 0, we deﬁne ∂ : → R by 0 0 ∂ α e := α (3.5) 0 v v v v∈V v∈V which yields an element of R. Remark 3.5 1. A standard check veriﬁes that ∂ ◦ ∂ = 0 (Grigor’yan et al. (2012), p−1 p Lemma 2.4) and hence ,∂ forms a chain complex. p p 2. Since we assume all digraphs are simple, there are no self-loops. Therefore, any allowed path must be regular and hence A ⊆ R ⊆ . (3.6) p p p In order to incorporate information about paths in the graph we would like a bound- ary operator between the A . However, the boundary of an allowed path may not itself be allowed, because it involves removing vertices from the middle of paths. To resolve this, we deﬁne a R-module, for each p ≥ 0, called the space of ∂-invariant p-paths −1 := (G; R) := v ∈ A | ∂ v ∈ A = A ∩ ∂ (A ). (3.7) p p p p p−1 p p−1 Since ∂ ◦ ∂ = 0, we see that ∂ ( ) ⊆ . Hence, we can make the following p−1 p p p p−1 construction. 123 T. Chaplin Deﬁnition 3.6 The non-regular chain complex is ∂ ∂ ∂ ∂ 3 2 1 0 −1 ... R 0 (3.8) 2 1 0 where each ∂ is the restriction of the non-regular boundary map to . p p Deﬁnition 3.7 The homology of the non-regular chain complex (3.8)isthe non-regular path homology of G.The pth homology group is denoted ker ∂ H (G; R) := . (3.9) im ∂ p+1 − → The rank of the pth homology group is pth Betti number, denoted β (G; R). When computing , one often encounters paths v ∈ A with irregular summands p p in their boundary. For example, ∂ (e ) = e − e + e . (3.10) 2 iji ji ii ij Since irregular summands are never allowed, these must be cancelled to obtain an element of . An alternative construction, which is featured more frequently in the literature, alters the boundary operator to remove these irregularities. There is a projection map π : → R which sends every irregular path to 0. p p This allows us to make the following construction: Deﬁnition 3.8 For each p ≥ 0, the regular boundary operator ∂ : R → R is p p−1 deﬁned by ∂ := π ◦ ∂ . (3.11) With this new boundary operator we still have the issue that the boundary of an allowed path may not be allowed. Therefore, we again construct an R-module, for each p ≥ 0, called the space of ∂ -invariants p-paths. R R R R −1 := (G; R) := v ∈ A | ∂ v ∈ A = A ∩ (∂ ) (A ). p p−1 p p−1 p p p p (3.12) One can check that, given any irregular path v, either ∂v = 0or ∂v is a sum of irregular paths (Grigor’yan et al. 2012, Lemma 2.9) and hence R R ∂ ◦ ∂ = π ◦ ∂ ◦ ∂ = π ◦ 0 = 0. (3.13) p−1 p p−1 p Deﬁnition 3.9 The regular chain complex is R R R R ∂ ∂ ∂ ∂ 3 2 1 0 −1 R R R ... R 0 (3.14) 2 1 0 123 First Betti number of the path homology of random... R R where each ∂ is the restriction of the non-regular boundary map to . p p Deﬁnition 3.10 The homology of the regular chain complex chain complex is the regular path homology of G and the kth homology group is denoted ker ∂ H (G; R) := . (3.15) im ∂ k+1 − → We denote the Betti numbers for these homology groups by β (G; R). Remark 3.11 1. If R is also a ﬁeld, then the homology groups H and H are vector − → − → spaces and so fully characterised, up to isomorphism, by β and β respectively. 2. Since we augment the chain complex with R in dimension −1, this is technically a reduced homology, but we omit additional notation for simplicity. 3. As noted in (Grigor’yan et al. (2012), §5.1), given a subgraph G ⊆ G then, for every p ≥ 0, R R (G ) ⊆ (G) and (G ) ⊆ (G). (3.16) p p p p Notation 3.12 When G is clear from context, we shall omit it from notation. If the coefﬁcient ring R is omitted from notation, assume that R = Z. Note that the primary difference between the regular and non-regular chain complex is the boundary operator. The difference between the boundary operators ∂ and ∂ affects the difference between the R-modules and . 3.2 Proof of Theorem 1.5 As an easy ﬁrst step, we show that, when graph density is too low, it is very unlikely that there are any long paths within the digraph. Therefore, for large k, A becomes − → trivial and consequently β = 0. −(N +1)/N Proposition 3.13 Given N ∈ N,if p = p(n) = o(n ) for some N ∈ N then, − → given a random directed graph G ∼ G (n, p), for all k ≥ N we have − → lim P( β (G) = 0) = 1. (3.17) n→∞ Proof Note that it sufﬁces to show that P(A ={0}) → 1as n →∞ because, if there are no allowed N -paths, then there are certainly no allowed k-paths. If there are − → no allowed k-paths then = {0} and so β = 0. k k For A to be non-trivial there must be some combinatorial, directed walk of length N . Equivalently, there must exist a combinatorial, directed cycle or a combinatorial, directed path of length N (or both). −(N +1)/N −1 If p = o(n ) then certainly p = o(n ) and hence, following the proof of Proposition 2.16, the probability that there is a directed cycle tends to 0 as n →∞. 123 T. Chaplin A combinatorial, directed path is a sequence of N + 1 distinct nodes, each joined by an edge in the forward direction. By a union bound, the probability that there exists such a sequence is at most N N +1 N (N + 1)! p ≤ n p (3.18) N + 1 which, by the assumption on p, tends to 0 as n →∞. α −(N +1)/N Proof of Theorem 1.5 By Proposition 3.13, it sufﬁces to note that n = o(n ) N +1 whenever α< − . − → This theorem is very weak. For example, to obtain β = 0 with high probability, we −2 require p = o(n ), in which case the expected number of edges in the digraph tends to 0. The weakness of this result stems from its reliance on the chain of inequalities − → β ≤ rank(ker ∂ ) ≤ rank ≤ rank A . (3.19) k k k k There is likely a region of graph densities wherein one or more of these inequalities is strict. Hence, in order to obtain stronger results, we require an understanding of , at the very least. 3.3 Chain group generators Proposition 3.14 (Grigor’yan et al. 2012, §3.3) For any simple digraph G = (V , E ), R R = = RV = A and = = RE = A . (3.20) 0 0 1 1 0 1 Proof Certainly ⊆ A and ⊆ A . Moreover, the boundary of any vertex is just 0 0 1 1 an element of R = A and hence allowed. The boundary of any edge is a sum of −1 vertices and any vertex is an allowed 0-path. Therefore A ⊆ and A ⊆ . 0 0 1 1 We can also see that the non-regular chain complex is a subcomplex of the regular chain complex, which immediately implies an inequality between the Betti numbers. This subcomplex relation was ﬁrst noted by Grigor’yan et al. (2012, Proposition 3.16). Proposition 3.15 For any simple digraph G, the non-regular chain complex is a sub- complex of the regular chain complex. In particular, for each p ≥ 0, we have (G) ⊆ (G). (3.21) Proof Suppose v ∈ , then ∂ (v) ∈ A . We have seen that A ⊆ R . Hence, p p p−1 p−1 p−1 if we project ∂ (v) onto R via π, we do not remove any summands. Therefore p p−1 ∂ (v) = π ∂ (v) = ∂ (v) ∈ A . (3.22) p p p−1 R R Certainly v ∈ A and hence v ∈ . Since the two operators, ∂ and ∂ , agree on p p p p , the non-regular chain complex is a subcomplex of the regular chain complex. 123 First Betti number of the path homology of random... Fig. 2 Generators for j j j (G; Z) as described in Proposition 3.17. a A double edge. b A directed triangle. c A long square. The red, dashed line must not be present for the third i k i motif to constitute a long square (a) (b) (c) − → − → Corollary 3.16 For any simple digraph G, β (G) ≤ β (G). Proof By Proposition 3.14, the two complexes coincide in dimensions 0 and 1 and R R hence rank ker ∂ = rank ker ∂ . By Proposition 3.15,im ∂ ⊆ im ∂ and hence 1 2 1 2 rank im ∂ ≤ rank im ∂ . Therefore, − → − → R R R β (G) = rank ker ∂ − rank im ∂ ≤ rank ker ∂ − rank im ∂ = β (G). (3.23) 1 2 1 1 1 2 Note, given a directed edge τ = (i , j ), ∂ (e ) = ∂ (e ) = e − e . From this, it 1 ij ij j i is easy to obtain the characterisation of the lowest Betti number ﬁrst stated in Sect. 1. − → − → Proof of Theorem 1.3 A standard argument shows that β = β = #C − 1, where #C is the number of weakly connected components of the digraph G. Note, #C coin- cides with the number of connected components of the symmetrisation G.The result follows by Lemma 2.12 and a standard result due to Erdos ˝ and Rényi (see e.g. Erdos ˝ and Rényi 1960; Kahle 2009). Unfortunately, higher chain groups do not enjoy such a concise description. How- ever, when working with coefﬁcient over Z, it is possible to write down generators for , in terms of motifs within the digraph G. Proposition 3.17 (Grigor’yan et al. (2014), Proposition 2.9) Let G be any ﬁnite digraph. Then any ω ∈ (G; Z) can be represented as a linear combination of 2-paths of the following three types: 1. e with i → j → i (double edges); iji 2. e with i → j → k and i → k (directed triangles); ijk 3. e − e with i → j → k, i → m → k, i → k and i = k (long squares). ijk imk Remark 3.18 Note that all vertices i , j , k, m in this theorem are distinct, either due to the existence of an edge (e.g. i → j implies i = j) or explicit statement (e.g. i = k). The following non-regular corollary follows immediately since, by Proposi- tion 3.15, ⊆ . Corollary 3.19 Let G be any ﬁnite digraph. Then any ω ∈ (G; Z) can be represented as a linear combination of 2-paths of the three types enumerated in Proposition 3.17. 123 T. Chaplin Fig. 3 Linearly dependent long squares with source i and sink k Note that each of the generators in Proposition 3.17 are elements of and hence they form a generating set for (G; Z). Note that elements of each type reside in mutually orthogonal components of A because they are supported on distinct basis elements. That is, we can write = D ⊕ T ⊕ S (3.24) where D is freely generated by all double edges e in G, and T is freely generated iji by all directed triangles e in G. The ﬁnal component, S, is generated by all long ijk squares e −e in G. However, they may not be linearly independent, for example, ijk imk as seen in Fig. 3, (e − e ) + (e − e ) + (e − e ) = 0. (3.25) ijk imk imk ilk ilk ijk Note that double edges are not ∂-invariant paths, i.e. e ∈ / . However there are iji 2 linear combinations of double edges which do belong to . For example, suppose i → j → i and i → k → i, then e − e ∈ . It is possible to state a non-regular iji iki 2 version of Proposition 3.17, in which all generators are elements of . This can be achieved by replacing double edge generators with such differences of double edges, which share a common base point. However, we omit this result, as it is not necessary for our main contribution. Remark 3.20 1. An alternative approach to computing rank and rank was ﬁrst seen in (Grigor’yan et al. (2012), Proposition 4.2) and is explored further in Appendix 1. 2. For the interested reader, more results which characterise relations between the are available in Grigor’yan et al. (2012, 2020). 3. We can use Proposition 3.17 to obtain an intuition for H (G; Z). Starting with the cell complex G, glue in a 2-cell for each generator identiﬁed by Proposition 3.17 by identifying its boundary with the corresponding motif in G. Then H of this cell complex coincides with H (G; Z). Unfortunately, since we do not have generators for for p > 2, developing intuition in higher degrees is much harder. Example 3.21 For further intuition, we reproduce the example given in (Grigor’yan et al. (2012), Proposition 4.7) but compute both regular and non-regular path homology. A cycle graph is a weakly connected digraph, on n ≥ 2, nodes such that each vertex 123 First Betti number of the path homology of random... has degree 2. Fix a cycle graph G. Then, H (G; Z) Z unless G is a double edge, directed triangle or long square, in which case H (G; Z) = 0. Whereas, H (G; Z) = Z unless G is a directed triangle or long square, in which case H (G; Z) = 0. For more examples, please consult Grigor’yan et al. (2012). 4 Asymptotic results for path homology Intuitively, we expect that the two transitions, identiﬁed in Fig. 9, correspond to two distinct topological phenomena. When density becomes sufﬁciently large, cycles start to appear in the graph and ker ∂ is non-empty for the ﬁrst time. Then, when density becomes too large, boundaries enter into which begin to cancel out all of the cycles, removing all homology. In the interim period, we expect that the number of cycles and the number of boundaries is approximately balanced. Therefore, in order to understand the lower boundary we should study ker ∂ and in order to understand − → the upper boundary we should study im ∂ . In order to show that β > 0in the 2 1 ‘goldilocks’ region we should compare the growth rates of rank ker ∂ and rank im ∂ , 1 2 or some approximation thereof. Moreover we expect reasonable conditions on p(n) α α to be of the form p = o(n ) or p = ω(n ) for some α, since conditions of this sort constrain p(n) relative to straight lines through Fig. 9. 4.1 Proof of Theorem 1.4(1) − → In order to characterise the behaviour of β when it is non-trivial, we will follow the approach of Kahle in (2009, §7). The approach is to use the ‘Morse inequalities’. In the context of a digraph G, denote the ranks of the chain groups by N := rank (G; Z) k k R R and N := rank (G; Z). Then we have k k − → − N + N − N ≤ β ≤ N . (4.1) k−1 k k+1 k k − → R R and a similar set of inequalities between the N and β . It is usually easier to k k compute the rank of chain groups than the rank homology groups. Hence, we use the − → limiting behaviour of N to investigate the limiting behaviour of β . First we will k k need estimates for E[N ]. − → Lemma 4.1 For a random directed graph G ∼ G (n, p) we have the following expec- tations E[N ] = E N = n (4.2) E[N ] = E N = n(n − 1)p (4.3) R 2 2 3 3 4 4 E[N ] ≤ E N ≤ n p + n p + n p . (4.4) 123 T. Chaplin Proof The ﬁrst two claims are clear since they count the expected number of nodes and edges in G, respectively. There is no difference between the regular and non-regular chain complex in dimensions 0 and 1. We use Proposition 3.17 to compute bounds for E[N ] and then the bound on E[N ] follows immediately because ⊆ (by Proposition 3.15). Since both 2 2 orientations of a double edge constitute a distinct basis element of , the expected 2 2 2 number of double edges is n(n −1)p , which is bounded above by n p . The expected number of directed triangles is 6 p , because each subset of 3 vertices can support 6 distinct directed triangles. Counting linearly independent long squares is more involved. For an upper bound, note that any subset of 4 vertices can support 12 long squares (not double counting for the two orientations since they differ by a factor of ±1). Each ﬁxed long square appears with probability p (1 − p). Therefore an upper bound on the number of linearly independent long squares is 4 4 4 12 p (1 − p) ≤ n p . (4.5) Combining these counts yields the upper bound on E[N ]. − → −1 Proposition 4.2 If G ∼ G (n, p) where p = p(n), with p(n) = ω(n ) and p(n) = −2/3 o(n ), then − → E[−N + N − N ] ∼ E[N ] and hence E[ β (G)]∼ E[N ] . (4.6) 0 1 2 1 1 1 − → R R Moreover, the same relations hold between the N and β . k k Proof We prove the non-regular case, but the regular case follows from an identi- cal argument. Using our expectations from Lemma 4.1,wesee E N = o(E N ) [ ] [ ] 0 1 because E[N ] n 1 lim = lim = lim = 0, (4.7) n→∞ n→∞ n→∞ E[N ] n(n − 1)p np −1 where the ﬁnal equality follows from the assumption p = ω(n ). Next, note that 2 2 3 3 4 4 E[N ] n p + n p + n p 2 2 3 0 ≤ lim ≤ lim = lim p + np + n p . n→∞ n→∞ n→∞ E[N ] n(n − 1)p (4.8) −2/3 2/3 The assumption p = o(n ) is equivalent to n p → 0as n →∞. This is sufﬁcient 2 2 3 to ensure p → 0, np → 0 and n p → 0as n →∞ and so E[N ] = o(E[N ]). 2 1 Hence the ﬁrst relation follows and the latter follows immediately from the Morse inequalities (4.1). 123 First Betti number of the path homology of random... Remark 4.3 If we choose p = n to satisfy the hypotheses of Proposition 4.2, then we 2 α+2 must have −1 <α < −2/3 in which case E[N ] is of the order n p = n . Then − → α + 2 > 1so E[ β ]→∞ at least linearly as n →∞. − → −1 Proposition 4.4 If G ∼ G (n, p) where p = p(n), with p(n) = ω(n ) and − → − → − → − → −2/3 R R p(n) = o(n ), then β (G) ∼ E[ β (G)] and β (G) ∼ E[ β (G)] with 1 1 1 1 high probability. Proof We prove the non-regular case but the regular case follows by an identical − → − → argument. As in Proposition 2.17, it sufﬁces to show that Var( β ) = o(E[ β ] ). 1 1 We have seen that E[N ] ∼ E[−N + N − N ] and certainly E[N ] →∞ as 1 0 1 2 1 n →∞. Therefore, eventually E[−N + N − N ]≥ 0 so, by the Morse inequalities, 0 1 2 eventually we can bound − → 2 2 E[ β ] ≥ E[−N + N − N ] . (4.9) 1 0 1 2 − → 2 2 Moreover, we always have β ≤ N so eventually we can bound 1 1 − → − → − → 2 2 2 2 Var( β ) E[ β ]− E[ β ] E N − E[−N + N − N ] 0 1 2 1 1 1 1 = ≤ . (4.10) − → − → 2 2 E[N + N − N ] E[ β ] E[ β ] 0 1 2 1 1 2 2 To conclude, it sufﬁces to show E N ∼ E[−N + N − N ] . By Proposition 4.2, 0 1 2 2 2 2 2 we know E[−N + N − N ] ∼ E[N ] . Then E N ∼ E[N ] because N is a 0 1 2 1 1 1 binomial random with mean E[N ] →∞. α −1 Proof of Theorem 1.4(1) If p(n) = n for −1 <α < −2/3 then p = ω(n ) and −2/3 −1 p = o(n ). Moreover, p = ω(n ) is sufﬁcient to ensure E[N ]→∞ as n →∞. Since N is a binomial random variable, this implies N ∼ E[N ] with high probability. 1 1 1 Combining Proposition 4.2 and Proposition 4.4 yields the result. 4.2 Proof of Theorem 1.4(2) − → − → Having done the work of showing β ∼ N , showing that β > 0 is now an easy 1 1 1 corollary. − → −1 Corollary 4.5 If G ∼ G (n, p) where p = p(n), with p(n) = ω(n ) and p(n) = −2/3 o(n ), then − → − → lim P( β (G)> 0) = lim P( β (G)> 0) = 1. (4.11) n→∞ n→∞ − → − → Proof As in Proposition 2.17, this follows immediately because β ∼ E[ β ] and 1 1 − → − → R R β ∼ E[ β ] with high probability and both expectations are eventually positive. 1 1 123 T. Chaplin α −1 Proof of Theorem 1.4(2) If p(n) = n for −1 <α < −2/3 then p = ω(n ) and p = − → − → −2/3 R o(n ). Hence, by Corollary 4.5, P[ β (G)> 0]→ 1 and P[ β (G)> 0]→ 1 as n →∞. 4.3 Proof of Theorem 1.4(3) − → Having understood the behaviour of E[ β ] in the ‘goldilocks’ region, we turn our attention to the boundaries of this region. As with the symmetric methods, we expect − → that if p is too small then β will vanish due to the lack of cycles. −1 Proposition 4.6 If p = p(n) = o(n ) then, given directed random graphs G ∼ − → G (n, p), we have − → − → lim P( β (G) = 0) = lim P( β (G) = 0) = 1. (4.12) n→∞ n→∞ Proof Given a double edge iji, note ∂ (e ) = e + e . Hence, for the regular case, iji ij ji − → a necessary condition for β > 0 is that there is some undirected cycle, of length at least 3, in the digraph. Whereas, for the non-regular case, a necessary condition is that there is some undirected cycle, of length at least 2, in the digraph. Therefore, the proof − → of the regular case is identical to the proof that β (G) = 0 with high probability and − → the proof of the non-regular case is identical to the proof that β (G) = 0 with high probability, as seen in Proposition 2.16. α −1 Proof of Theorem 1.4(3) Assume that p(n) = n .If α< −1 then p = o(n ) and − → − → hence, by Proposition 4.6, P( β (G) = 0) → 1 and P( β (G) = 0) → 1as n →∞. 4.4 Proof of Theorem 1.4(4) For the previous subsection we chose p small enough to ensure that it is highly likely − → that ker ∂ is empty. We also observe β vanishing for larger values of p. In these 1 1 regimes ker ∂ is likely non-empty but all cycles are cancelled out by boundaries. Put another way, we wish to show that, when p is large, every cycle ω ∈ ker ∂ can be shown to satisfy ω = 0 (mod im ∂ ). (4.13) The strategy is to ﬁnd conditions under which cycles supported on many vertices can be reduced down to cycles supported on just 3 vertices, and then show that small − → cycles can be reduced to 0. For this subsection, we will prove that P[ β (G) = 0]→ 1 − → which then implies, by Corollary 3.16, that P[ β (G) = 0]→ 1, as n →∞. First, we need to ensure that we can choose a basis for ker ∂ which will be amenable to our reduction strategy. 123 First Betti number of the path homology of random... Deﬁnition 4.7 Givenanelement ω ∈ (G), we can write ω in terms of the standard basis ω = α e . (4.14) τ τ τ ∈E (G) 1. We deﬁne the support of v to be supp(ω) := {τ ∈ E | α = 0} . (4.15) 2. We call ω a fundamental cycle if ω ∈ ker ∂ , α ∈ {±1} for each τ ∈ E, and 1 τ supp(ω) forms a combinatorial, undirected cycle in G. Lemma 4.8 Given a simple digraph, ker ∂ has a basis of fundamental cycles in G. Proof Take an undirected spanning forest T for G, i.e. a subgraph of T in which every two vertices in the same weakly connected component of G can be joined by a unique undirected path through T . One can check that ∂ : (T ; R) → (T ; R) has trivial 1 1 0 kernel, since there are no undirected cycles in T . Given an edge outside the forest τ = (a, b) ∈ E (G) \ E (T ), there is a unique undirected path ρ through T which joins the endpoints of τ : ρ = (a = v ,τ ,v ,...,τ ,v ,τ , b = v ). (4.16) 0 1 1 k−1 k−1 k k for some v ∈ V (G), τ ∈ E (G). Deﬁne i i 1if τ = (v ,v ) i i −1 i α := (4.17) −1if τ = (v ,v ) i i i −1 and note that ∂ e − α e = 0. (4.18) 1 τ i τ i =1 Hence b := e − α e ∈ ker ∂ . Note that b is a fundamental cycle. τ τ i τ 1 τ i =1 i The set B := {b | τ ∈ E (G) \ E (T )} is linearly independent because, given b ∈ τ τ B, no other b ∈ B involves the basis element e of . Note, we can write τ τ 1 = R{e | τ ∈ E (T )} ⊕ RB . (4.19) 1 τ Since there are no cycles in the spanning forest T , the kernel of ∂ on the ﬁrst component is trivial. Therefore, rank ker ∂ ≤ #B and hence B spans ker ∂ . 1 1 Now we can describe the strategy by which systematically reduce long fundamental cycles into smaller ones. We design a combinatorial condition on a directed graph which is more likely to occur at higher densities. 123 T. Chaplin v v v v v v 0 1 1 2 1 2 v v v v 0 3 0 3 v v κ κ 1 2 κ (a) (b) (c) (d) Fig. 4 a, b Directed centres for undirected paths of length 3. The blue, dashed edges constitute J . c A σ,κ cycle centre for a 3-cycle. d A cycle centre for a 2-cycle Deﬁnition 4.9 1. An undirected path σ ⊆ G, on vertices (v ,...,v ),issaidtobe 1 k reducible if there is some shortcut edge, e = (v ,v ), with |i − j | > 1 such that i j − → β (σ ∪ e) = 0. If a path is not reducible then it is called irreducible. 2. Given an undirected path σ ⊆ G of length 3, on vertices (v ,v ,v ,v ), and a 0 1 2 3 vertex κ ∈ V (G) \ V (σ ), deﬁne the linking set J := {e ∈ E (G) | e = (v ,κ) or e = (κ, v ) for some i } . (4.20) σ,κ i i Such a vertex, κ, is called a directed centre for σ if there is some subset of linking − → edges J ⊆ J such that β (σ ∪ J ) = 0 and σ ∪ J contains an undirected path, σ,κ 1 of length 2, on the vertices (v ,κ,v ). 0 3 3. A cycle centre for a directed cycle of length k, on vertices (v ,...,v ), is a vertex 0 k−1 κ ∈ V (G) \ {v ,...,v } such that (k,v ) ∈ E (G) for all i = 0,..., k − 1or 0 k−1 i (v , k) ∈ E (G) for all i. In the following examples, we demonstrate the utility of directed centres. Example 4.10 Figure 5 shows four examples of the reduction strategy described by Lemma 4.11. For illustration, we describe these reductions in more detail below. 1. In Fig. 5a, the initial undirected path of length 3 has a directed centre κ which does not coincide with a vertex in the rest of the cycle. Therefore, we can write [e + e − e ]+ e − e − e + e + e v v v v v v v v v v v v v v v v 0 1 1 2 3 2 3 4 5 4 6 5 6 7 7 0 =[e + e ]+ e − e − e + e + e (mod im ∂ ). v κ κv v v v v v v v v v v 2 0 3 3 4 5 4 6 5 6 7 7 0 (4.21) 2. In Fig. 5b, the path has a directed centre κ = v . Replacing the initial path with the smaller path, via the directed centre, yields a sum of two fundamental cycles: [e + e − e ]+ e − e − e + e + e v v v v v v v v v v v v v v v v 0 1 1 2 3 2 3 4 4 6 6 7 7 0 5 5 =[e + e ]+ e − e − e + e + e (mod im ∂ ) v κ κv v v v v v v v v v v 2 0 3 3 4 4 6 6 7 7 0 5 5 =[e − e + e + e ]+[e + e − e ] (mod im ∂ ). v v v v v v v v v v v v v v 2 0 5 6 5 6 7 7 0 5 3 3 4 5 4 (4.22) 123 First Betti number of the path homology of random... Fig. 5 Examples of the v v 1 1 v v reductions used in Lemma 4.11 2 2 which are explained in greater v v 3 3 v v depth in Example 4.10. Black, 0 0 solid edges indicate the initial cycle. Blue, dash-dotted edges v v 4 4 are new edges in the reduced v v 7 7 cycle. Red, dashed edges are v = κ those removed in the reduced v v 6 6 cycle. Green, dotted edges must be present in order to do the (a) (b) illustrated reduction. Square nodes symbolise directed centres v v 1 for the undirected path (v ,v ,v ,v ). 0 1 2 3 v v 2 v v 3 v 5 v = κ v 4 4 (c) (d) 3. In Fig. 5c, the path has a directed centre κ = v . Replacing the initial path (v ,v ,v ,v ) with the smaller path (v ,κ,v ) yields a much smaller support 0 1 2 3 0 3 since the edge (v ,v ) gets cancelled out: 3 4 [e + e − e ]+ e − e − e v v v v v v v v v v v v 0 1 1 2 3 2 3 4 5 4 0 5 =[e − e ]+ e − e − e (mod im ∂ ) v κ v κ v v v v v v 2 0 3 3 4 5 4 0 5 = e − e − e (mod im ∂ ). (4.23) v v v v v v 2 0 4 5 4 0 5 4. Finally, in Fig. 5d, the initial path is reducible via the shortcut edge (v ,v ) and 0 2 hence [e + e − e ]+ e − e − e v v v v v v v v v v v v 0 1 1 2 3 2 3 4 5 4 0 5 =[e − e ]+ e − e − e (mod im ∂ ). (4.24) v v v v v v v v v v 2 0 2 3 2 3 4 5 4 0 5 These examples tell the story of each case in the following lemma, in which we conﬁrm that the presence of directed centres allows us to systematically reduce fun- damental cycles. Lemma 4.11 For any simple digraph G, suppose every irreducible, undirected path of length 3 has a directed centre. Given a fundamental cycle ω ∈ ker ∂ with # supp(ω) = k ≥ 4, there exists fundamental cycles ω ˜ , ω ˜ ∈ ker ∂ such that 1 2 1 ω =˜ ω +˜ ω (mod im ∂ ) (4.25) 1 2 2 with # supp(ω ˜ ) + # supp(ω ˜ ) ≤ k − 1 and, potentially, one or more ω ˜ = 0. 1 2 i 123 T. Chaplin Proof Since v is a fundamental cycle, it is supported on some combinatorial, undirected cycle ρ = (v ,τ ,v ,...,v ,τ ,v = v ). (4.26) 0 1 1 k−1 k k 0 for some v ∈ V and τ ∈ E ordered such that i i ω = α e (4.27) i τ i =1 where 1if τ = (v ,v ) i i −1 i α := . (4.28) −1if τ = (v ,v ) i i i −1 Since k ≥ 4, the vertices (v ,...,v ) are distinct and, along with the edges 0 3 τ ,τ ,τ , form an undirected path of length 3. Either this is reducible via some short- 1 2 3 cut edge τ ∈ E, or there exists a directed centre κ ∈ V . In either case, there is some undirected path, from v to v , of length at most 2. This path is represented by some 0 3 η ∈ with coefﬁcients in {±1}, such that ∂ η = e − e and # supp η ≤ 2. 1 1 v v 3 1 Since both η and η := α e are supported on undirected paths from v to i τ 0 i =1 i v ,wehave ∂ η − η = 0. Since supp(η) ⊆ E (G ) and supp(η ) ⊆ E (G ) for some 3 1 − → subgraph G ⊆ G with β (G ) = 0 (either due to reducibility or a directed centre), there is some u ∈ (G) such that ∂ u = η − η . Therefore we can replace the initial 2 2 undirected path of length 3, in v, with an undirected path of length at most 2, i.e ω = η + α e =:ω( ˜ mod im ∂ ). (4.29) i τ 2 i =4 Certainly # supp(ω) ˜ ≤ 2 + (k − 3)< 3 + (k − 3) = # supp(ω) so ω ˜ has a strictly smaller support. It remains to prove that ω ˜ can be decomposed into a sum of at most two fundamental cycles. In the case that the path has a directed centre κ, we split into two further sub-cases. Case 1.1: If κ = v for any i, supp(ω) and supp(η ) are disjoint so all coefﬁcients of ω ˜ are still ±1. Moreover, since κ is distinct from the vertices of ρ, replacing (v ,...,v ) 0 3 with (v ,κ,v ) certainly yields an undirected cycle in G. 0 3 Case 1.2: If κ = v for some i ∈{0,..., k − 1} then there are number of possible sub-cases. If supp(ω) ∩ supp(η ) =∅ then all coefﬁcients of ω ˜ are still ±1. However, the replacement procedure has the effect of pinching supp(ω) ˜ into two edge-disjoint, undirected cycles, which share a vertex at κ. Hence, we can easily decompose ω ˜ into a sum of two fundamental cycles ω ˜ and ω ˜ , supported on each of these underlying 1 2 cycles. 123 First Betti number of the path homology of random... If the intersection is non-empty, then supp(ω) ∩ supp(η ) ⊆{τ ,τ }, so there are 4 k at most two offending edges. Moreover, in order to attain ∂ (η − η ) = 0 these edges must appear with opposite signs in ω and η respectively. If there are two offending edges then we must have 4 = k − 1 and the replacements procedure yields ω ˜ = 0. If there is only one offending edge then this edge is no longer contained in supp(ω) ˜ and the length of the underlying undirected cycle is further reduced. Case 2: If the path was reducible, in most cases supp(ω) and supp(η ) are disjoint and the replacement process simply removes one or two vertices from the undirected cycle. The only remaining case is if k = 4 and supp(ω) ∩ supp(η ) ={τ }, in which case the replacement procedure yields ω ˜ = 0. Once we have reduced large cycles into smaller ones, we need conditions to ensure that the resulting small cycles are themselves homologous to zero. Lemma 4.12 Given a fundamental cycle ω ∈ ker ∂ such that supp(ω) is a directed cycle of length k, if supp(ω) has a cycle centre κ ∈ V then ω = 0 (mod im ∂ ). (4.30) Proof For some vertices v ,...,v ∈ V and edges τ ,...,τ ∈ E we can write 0 k−1 1 k the underlying cycle as ρ = (v ,τ ,...,v ,τ ,v ) (4.31) 0 1 k−1 k 0 so that k−1 ω =± e . (4.32) i =0 Since κ is a cycle centre, either γ := e ∈ for every i or γ := e ∈ i κv v 2 i v v κ 2 i i +1 i i +1 for every i (identifying v = v ). In either case, by a telescoping sum argument, k 0 k−1 k−1 ∂ γ = e . (4.33) 1 i τ i =0 i =0 After adjusting for a factor of ±1, this concludes the proof. Piecing these lemmas together, gives us a topological condition, which implies − → β (G) = 0, and which is likely to occur in high density graphs. Proposition 4.13 For any simple digraph G, if every irreducible, undirected path of length 3 has a directed centre, and every directed cycle of length 2 or 3 has a cycle − → − → centre, then β (G) = 0 and β (G) = 0. Proof We prove the non-regular case from which the regular case immediately follows by Corollary 3.16. 123 T. Chaplin Fix a basis {ω ,...,ω } of fundamental cycles for ker ∂ , as described by 1 k 1 Lemma 4.8. Choose an arbitrary i ∈{1,..., k} It sufﬁces to show that ω = 0 (mod im ∂ ). By Lemma 4.11, we can reduce each ω to a sum of fundamental cycles 2 i ω = ω ˜ (mod im ∂ ) (4.34) i i , j 2 j =1 with # supp ω ˜ ≤ 3 for each j. i , j If supp(ω ˜ ) is a directed triangle then ω ˜ is the boundary of the corresponding i , j i , j basis element in ; hence ω ˜ = 0 (mod im ∂ ). Otherwise, supp(ω ˜ ) must be a 2 i , j 2 i , j directed cycle or length 2 or 3. In either case, the support has a cycle centre and hence, by Lemma 4.12, ω ˜ = 0 (mod im ∂ ). Therefore ω = 0 (mod im ∂ ). i , j 2 i 2 Remark 4.14 Every double edge (i , j ), ( j , i ) ∈ E appears as an allowed 2-path in and ∂ (e ) = e + e . Therefore, the requirement that every cycle of length 2 has iji ji ij − → a cycle centre is not strictly necessary to ensure β (G) = 0. Deﬁnition 4.15 For each n ∈ N,the complete directed graph on n-nodes, K ,is deﬁned by V (K ) := {1, 2,..., n} , E (K ) := {(i , j ) | i = j } . (4.35) n n Moreover, we deﬁne the following collection of subgraphs contained within K : 1. P := {subgraphs σ ⊆ K | σ is an undirected path of length 3}; 2. For each k ≥ 2, C := {subgraphs σ ⊆ K | σ is a directed cycle of length k}. Given a random graph G ∼ G(n, p), we deﬁne the following events: n n 1. for σ ∈ P or σ ∈ C for some k ≥ 2, S is the event that σ is a subgraph of G; 3 k 2. for σ ∈ P , I is the event that σ is irreducible in the graph G ∪ σ ; 3. for σ ∈ P , A is the event that κ is a directed centre for σ in the graph G ∪ σ ; σ,κ 4. for σ ∈ C for some k ≥ 2, B is the event that κ is a cycle centre for σ in the σ,κ graph G ∪ σ . Remark 4.16 For a ﬁxed σ ∈ P , the events S , I and A for every κ ∈ V (G)\V (σ ) σ σ σ,κ are mutually independent. For a ﬁxed σ ∈ C for some k ≥ 2, the events S and B σ σ,κ for every κ ∈ V (G) \ V (σ ) are mutually independent. − → −1/3 Proposition 4.17 If G ∼ G (n, p), where p = p(n) = ω (n/ log(n)) , then − → − → lim P( β (G) = 0) = lim P( β (G) = 0) = 1. (4.36) n→∞ n→∞ Proof By Proposition 4.13, it sufﬁces to show that the probability that there exists an irreducible, undirected path of length 3 without directed centre, or a cycle of length 123 First Betti number of the path homology of random... 2 or 3 without directed centre, tends to 0 as n →∞. The probability that there is an irreducible, undirected path of length 3 without a directed centre is at most ⎛ ⎡ ⎤ ⎞ ⎝ ⎣ ⎦ ⎠ P[S ] · P[I ] · P A . (4.37) σ σ σ,κ σ ∈P κ∈V (G)\V (σ ) Because the events A | κ ∈ V (G) \ V (σ ) are independent, P ∩ A = σ,κ κ σ,κ n 2 (1 − P A ). Note that #P = 4! 2 . This count arises because an undi- σ,κ 3 4 rected path of length 3 is determined by a choice of 4 nodes, an order on the nodes and a choice of orientation on each edge. However, this counts each path twice: once in each direction. Also, each path arises in G with probability P[S ] = p and clearly P[I ] ≤ 1. For each σ ∈ P and κ ∈ V (G) \ V (σ ), there is at least one choice of 3 directed edges, from κ to the vertices of the path, which forms a directed centre. Namely, label the vertices of σ by (v ,...,v ). Then we can always choose an edge between κ and 0 3 v and another edge between κ and v so that there is a long square on {κ, v ,v ,v },as 0 2 0 1 2 illustrated in Fig. 4. The third edge can then be chosen to ensure that there is a directed triangle on {κ, v ,v }. If these three edges are present in G, they constitute J ⊆ J 2 3 σ,κ with the properties required to form a directed centre and hence P A ≥ p . σ,κ Therefore we can bound the probability (4.37) further by n−4 2 3 3 4 3 3 4! 2 p 1 − p ≤ 4n p exp −p (n − 4) . (4.38) We wish to show that this bound tends to 0 as n →∞. Since p ≤ 1, it sufﬁces 4 3 to show lim n exp(−p n) = 0. By Lemma 4.18, the condition on p ensures n→∞ that lim (4log(n) − p n) =−∞. By the continuity of the exponential function, n→∞ 4 3 lim n exp(−p n) = 0. n→∞ n n n n Note #C = and #C = 2 . By another union bound, we see that the 2 3 2 3 probability that there is a directed cycle, of length 2, without cycle centre, is at most ⎛ ⎞ 2n−4 c 2 2 ⎝ ⎠ P[S ] · P B = p [1 − p ] . (4.39) σ σ,κ σ ∈C κ∈V (G)\V (σ ) Similarly, the probability that there is a directed cycle, of length 3, without cycle centre is at most 2n−6 3 3 2 p [1 − p ] . (4.40) Again, by Lemma 4.18, the condition on p sufﬁces to ensure that these two bounds also tend to 0 as n →∞. 123 T. Chaplin −1/k Lemma 4.18 Given k ∈ N and A, B > 0,if p = ω (n/ log(n)) then >0 lim (A log(n) − Bnp ) =−∞. (4.41) n→∞ np Proof The condition on p is equivalent to lim =∞, which implies n→∞ log(n) log(n) (A − B) →−B and np →∞ as n →∞. np Proof of Theorem 1.4(4) Assume that p(n) = n .If α> −1/3 then an application −1/3 of L’Hôpital’s rule shows p = ω (n/ log(n)) and hence, by Proposition 4.17, − → − → P( β (G) = 0) → 1 and P( β (G) = 0) → 1as n →∞. Remark 4.19 Lemma 4.18 reveals the origin of the ratio 1/3, which appears in Theo- rem 1.4(4) and Proposition 4.17. In particular, it arises as the ratio between the power of n and the power of p inside the exponential of equation (4.38). The power of n is 1 because there are on the order of n possible directed centres for an undirected path of length 3. The power of p is 3 because we require at least 3 edges from κ to the path, in order for κ to form a directed centre. In Lemma A.7, we will see that this is indeed the minimal number of edges required to form a directed centre. The bounds used in the proof of Proposition 4.17 are by no means the best possible. Indeed, by splitting P into four isomorphism classes, it is possible to get exact values for P[I ] and P A . We explore this further in Appendix 1 in order to obtain tighter σ σ,κ bounds, useful for hypothesis testing. − → Moreover, the topological condition for β (G) = 0 presented in Proposition 4.13 was chosen since it is likely to occur at high densities. However, there may (and − → indeed probably does) exist weaker topological conditions which imply β (G) = 0 and occur at somewhat lower densities. This could potentially allow for a weaker hypothesis on Proposition 4.17. In order to conjecture the weakest possible hypothesis, we conduct a number of experiments in Appendix B. 5 Directed ﬂag complex of random directed graphs For comparative purposes, we now apply the techniques of Sect. 4 to the directed ﬂag complex, which features more readily in the literature. Deﬁnition 5.1 (Lütgehetmann et al. 2020, Deﬁnition 2.2) An ordered simplicial com- plex on a vertex set V is a collection of ordered subsets of V , which is closed under taking non-empty, ordered subsets (with the induced order). A subset in the collection consisting of (k + 1) vertices is called a k-simplex. Deﬁnition 5.2 (Lütgehetmann et al. 2020, Deﬁnition 2.3) Given a directed graph G = (V , E ), 1. a directed (k + 1)-clique is a (k + 1)-tuple of distinct vertices (v ,...,v ) such 0 k that (v ,v ) ∈ E whenever i < j; i j 123 First Betti number of the path homology of random... − → 2. the directed ﬂag complex, X (G), (often denoted dFl(G)) is an ordered simplicial complex, whose k-simplicies are the directed (k + 1)-cliques. − → Given a ring R,the directed ﬂag chain complex is { X (G), ∂ } where, for k ≥ 0, k k k≥−1 − → − → X (G) := X (G; R) := R{(v ,...,v ) | directed (k + 1)-clique in G} , (5.1) k k 0 k ∂ (e ) := (−1) e . (5.2) k (v ,...,v ) 0 k (v ,...,vˆ ,...,v ) 0 i k i =0 where (v ,..., vˆ ,...,v ) denotes the directed k-clique (v ,...,v ) with the vertex 0 i k 0 k − → v removed. This deﬁnes ∂ on a basis of X (G), from which we extend linearly. We i k k − → also deﬁne X (G) = R and ∂ simply sums the coefﬁcients in the standard basis, −1 0 as in equation (3.5). The homology of this chain complex is the directed ﬂag complex homology.The − → Betti numbers are denoted β ( X (G)). When the coefﬁcient ring R is omitted from notation, assume R = Z. − → Firstly, as with path homology, β ( X (G)) captures the weak connectivity of a digraph G and hence Theorem 1.3 also holds for the directed ﬂag complex. Next, − → since we have an explicit list of generators for X (G), and they are easy to count, we can calculate the expected rank of the chain groups in every dimension. As before, we − → denote the ranks of chain groups as N := rank X (G) and use these to estimate the k k Betti numbers. − → Lemma 5.3 For an Erdos–Rényi ˝ directed random graph G ∼ G (n, p), for any k ≥ 0 we have k+1 ( ) E[N ]= (k + 1)! p . (5.3) k + 1 Proof A possible directed clique is uniquely determined by an ordered (k + 1)-tuple of distinct vertices. Therefore, there are (k + 1)! possible cliques. For a given k+1 clique to be present, one edge must be present in G for every pair of distinct nodes. Using the Morse inequalities as before, this allows us to compute the growth rate of the expected Betti numbers, under suitable conditions on p = p(n). − → −1/k Proposition 5.4 For k ≥ 0,if G ∼ G (n, p) where p = p(n), with p(n) = ω(n ) −1/(k+1) and p(n) = o(n ), then − → E −N + N − N ∼ E[N ] and hence E[β ( X (G))]∼ E[N ] . (5.4) k−1 k k+1 k k k Proof It is easy to check that E N 1 1 k−1 −k = p ∼ (5.5) E[N ] (n − k) np 123 T. Chaplin −1/k which tends to 0 thanks to the condition p(n) = ω(n ). It follows that k+1 E N /E[n ] ∼ np which tends to 0 thanks to the condition p(n) = k+1 k −1/(k+1) o(n ). As in Proposition 4.2, the result then follows by the Morse inequali- ties. − → −1 Proposition 5.5 If G ∼ G (n, p) where p = p(n), with p(n) = ω(n ) and p(n) = − → − → −1/2 o(n ), then β ( X (G)) ∼ E[β ( X (G)] with high probability. 1 1 −1/2 Proof The proof is identical to Proposition 4.4 except we only need p(n) = o(n ) to ensure E[−N + N − N ] ∼ E[N ]. 0 1 2 1 − → −1 Corollary 5.6 If G ∼ G (n, p) where p = p(n), with p(n) = ω(n ) and p(n) = −1/2 o(n ), then − → lim P(β ( X (G)) > 0) = 1. (5.6) n→∞ Proof The proof is identical to Corollary 4.5 expect again we only require p(n) = −1/2 o(n ) to invoke Proposition 5.5. As with path homology, degree 1 homology appears in the directed ﬂag complex with the appearance of undirected cycles in the underlying digraph. Therefore, the − → same conditions show that β ( X (G)) = 0 with high probability, when p = p(n) shrinks too quickly. −1 Proposition 5.7 If p = p(n) = o(n ) then, given a random directed graph G ∼ − → G (n, p), we have − → lim P(β ( X (G)) = 0) = 1. (5.7) n→∞ Proof The proof is identical to the non-regular case of Proposition 4.6. The techniques from Sect. 4.4 can be applied, mutatis mutandis, to show β (G) = 0 with high probability, when p = p(n) shrinks too slowly. − → −1/4 Proposition 5.8 If G ∼ G (n, p), where p = p(n) = ω (n/ log(n)) , then − → lim P(β ( X (G)) = 0) = 1. (5.8) n→∞ Proof This follows from the same argument as Proposition 4.17. The only difference is that a directed centre for an undirected path of length 3 requires at least 4 edges, in order to form 3 directed cliques. This results in the ratio 1/4 instead of 1/3. As in the earlier sections, the results obtain here sufﬁce to prove the summary result, Theorem 1.6, presented in the introduction. 123 First Betti number of the path homology of random... 6 Discussion We have identiﬁed asymptotic conditions on p = p(n) which ensure that a random − → − → directed graph G ∼ G (n, p) has β (G)> 0 with high probability. Moreover, under − → these conditions we showed that E[ β (G)]∼ n(n −1)p. Beneath the lower boundary − → of this positive region, we showed that β (G) = 0 with high probability. Immedi- − → ately after the upper boundary of the positive β range, our theory is inconclusive, − → but experimental results (shown in Appendix B) provide evidence that β (G) = 0 with high probability. Further away from the positive region, e.g. when p = n for − → α> −1/3, our theory again guarantees that β (G) = 0 with high probability. For comparison, we applied these techniques to the directed ﬂag complex and found sim- ilar results, with minor changes to the gradient of the boundary lines. We summarise these results, along with similar results for ‘symmetric methods’ in Table 1. These results, along with known results for the clique complex of a random undi- rected graph, motivate the following research directions: 1. Tighter upper boundary – Experimental results, in Appendix 1, indicate that the conditionα> −1/3 of Theorem 1.4 could be weakened signiﬁcantly, potentially as − → far as α> −2/3. Indeed this is the best possible result because β > 0 with high probability for −1 <α < −2/3. We saw how the ratio 1/3 arose from our proof in Remark 4.19, which informs how we might improve this result. Generalising a directed centre to be a set of k > 1 nodes, with suitable conditions, might yield better results since there are on the order of n set of k nodes. However, this would complicate the probability bound because two directed centres would no longer be − → Table 1 Given a random directed graphs G ∼ G (n, p), assuming p = n , we record the known regions of α for which various homologies are either positive, or zero, with high probability Homology Expected growth Positive region (α) Zero region (α) Symmetric methods β (G) n(n − 1)p (−1, 0] (−∞, −1) β (G) p ¯ (−1, 0] (−∞, −1) β (X(G)) p ¯ (−1, −1/2)(−∞, −1) ∪ (−1/2, 0] k+1 ( ) 1 1 1 1 β (X(G)), k > 1 p ¯ − , − −∞, − ∪ − , 0 k+1 k k+1 k k+1 Directed methods − → β ( X (G)) n(n − 1)p (−1, −1/2)(−∞, −1) ∪ (−1/4, 0] − → β (G) n(n − 1)p (−1, −2/3)(−∞, −1) ∪ (−1/3, 0] − → β (G) n(n − 1)p (−1, −2/3)(−∞, −1) ∪ (−1/3, 0] − → k+1 β (G), k > 1 ?? −∞, − → k+1 β (G), k > 1 ?? −∞, k k Moreover, we describe the growth rate of the expected Betti numbers, in the respective positive regions. That is, for Betti number β, we give a function f (n) such that, when α is in the positive region, E[β(G)]∼ f (n) 123 T. Chaplin independent. Alternative approaches may include ﬁnding a cover of the random graph which can be used to show that the digraph is contractible via path homotopy Grigor’yan et al. (2014). − → 2. Higher degrees – So far we only have weak guarantees for the behaviour of β for k > 1. One potential avenue for improvement is to ﬁnd conditions under which − → P[ ={0}] → 1as n →∞. In order to get better results for vanishing β at k k small p, we require a greater understanding of generators of ker ∂ . In order to get better results at large p, we need a high-density, topological condition which implies that these generators can be reduced to 0 (mod im ∂ ). k+1 − → 3. Distributional results—One direction of research is to show that normalised β converges to a normal distribution as n →∞. More evidence for this conjecture is given in Appendix 1. This could be done, for example, by Stein’s method Chen et al. (2011), as is done by Kahle and Meckes (2013)for β (X(G(n, p))). Acknowledgements The author would like to thank his supervisors Ulrike Tillmann and Heather Harrington for their support and guidance throughout this project. The author would also like to thank Gesine Reinert and Vidit Nanda for their helpful feedback on a prior draft. Finally, the author would like to thank both reviewers for their helpful comments which both helped the presentation and strengthened the result of Theorem 1.41. The author is a member of the Centre for Topological Data Analysis, which is funded by the EPSRC grant ‘New Approaches to Data Science: Application Driven Topological Data Analysis’ EP/R018472/1. Data availability The code and data for the experiments of Appendix B, as well as an implementation of the algorithm described in Lemma A.7, are available on both the OSF repository Chaplin (2022) and GitHub Chaplin (2021). All code is written in MATLAB and data from the experiments is available in the .mat format. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. Appendix A: Explicit probability bounds The results presented in Sect. 4 provide a broad-stroke, qualitative description of the − → behaviour of β on random directed graphs. However, they provide no guarantees for a digraph of a ﬁxed size, such as those arising in applications. For hypothesis testing, − → − → it is desirable to have explicit bounds on the P[ β (G)> 0] and P[ β (G) = 0] for 1 1 − → G ∼ G (n, p),given n and p. In this section, we describe such bounds arising from the proofs in Sect. 4 and improve on them where possible. 123 First Betti number of the path homology of random... A.1 Positive Betti numbers at low densities First we reﬁne the bound developed in Proposition 4.6, in order to show that it is − → unlikely to observe β (G)> 0 when graph density is low. − → Theorem A.1 If G ∼ G (n, p) then n L! − → P β (G)> 0 ≤ (2 p) . (A1) L 2L L=2 − → − → The same bound holds for P[β ( X (G)) > 0]. The same bound holds for P[ β (G)> 0] after removing the L = 2 term. Proof We start with the non-regular and directed ﬂag complex case. We follow the same argument as the proof of Proposition 4.6 but make more accurate estimates. A − → − → sufﬁcient condition for both β (G) = 0 and β ( X (G)) is that there are no undirected 1 1 cycles of any length 2 ≤ L ≤ n in G. For each L, there are n L! 2 (A2) L 2L possible undirected cycles. This is because an undirected cycle can be determined by a choice of L vertices, an order on those vertices, and a choice of orientation for each edge. However, this over-counts, by a factor of 2L, since we could traverse the cycle in either direction and start at any vertex. Each cycle of length L appears with probability p so a union bound yields the result. For regular path homology, the only undirected cycles of length 2 are double edges, which are boundaries in the regular path complex. Therefore we can remove the L = 2 term from the bound. The region of parameter space in which this theorem applies is illustrated in Fig. 6a. t t For each n,weplot p (n), the maximum value such that for all p ≤ p (n), Proposi- l l − → tion A.1 implies that P[ β (G)> 0]≤ 0.05. A.2 Zero Betti numbers In order to obtain the best possible estimate, following the second moment method of Corollary 4.5, we need an exact value for E[rank ]. We reproduce the approach of (Grigor’yan et al. (2012), Proposition 4.2), making the necessary alterations for the non-regular case. The approach is to determine the number of linearly independent conditions required to describe as a subspace of A . 2 2 Deﬁnition A.2 Given a directed graph G = (V , E ), 1. a semi-edge is an ordered pair of distinct vertices (i , k) ∈ V , i = k such that i → k but there is some other vertex j ∈ V , j = i , k such that i → j → k; 123 T. Chaplin 2. a semi-vertex is a vertex i ∈ V such that there is some other vertex j ∈ V , j = i such that i → j → i. We denote the set of all semi-edges by S and all semi-vertices by S . E V − → Lemma A.3 If G ∼ G (n, p) then n−2 2 2 2 E[rank (G; Z)] = n(n − 1) p − n(n − 1)(1 − p) 1 − (1 − p ) n−1 − n 1 − (1 − p ) (A3) n−2 R 2 2 2 E rank (G; Z) = n(n − 1) p − n(n − 1)(1 − p) 1 − (1 − p ) (A4) Proof First we deal with the non-regular case. Given v ∈ A , then v ∈ if and only 2 2 if ∂v ∈ A .Let A denote the set of all allowed 2-paths in G, then we can write 1 2 ijk v = v e (A5) ijk ijk∈A so that ijk ∂v = v (e − e + e ). (A6) jk ik ij ijk∈A Since ijk is allowed, so too are ij and jk. Therefore ijk ∂v =− v e (mod A ). (A7) ik 1 ijk∈A Now we split off terms corresponding to double edges ijk iji ∂v =− v e − v e (mod A ). (A8) ik ii 1 ijk∈A iji ∈A 2 2 i =k Note ii is never an allowed 1-path. However, for i = k, ik is an allowed 1-path if i → k, so we can remove these summands ijk iji ∂v =− v e − v e (mod A ). (A9) ik ii 1 ijk∈A iji ∈A 2 2 i =k,i →k Therefore, ∂v ∈ A if and only if for each (i , k) ∈ V with i = k and i → k ijk v =0(A10) j : ijk∈A 123 First Betti number of the path homology of random... and for each i ∈ V iji v = 0. (A11) j : iji ∈A Some of the indexing sets of these summations may be empty and hence some of these conditions may be trivial. The remaining conditions are linearly independent and hence it remains to count the number of non-trivial equations. Equation (A10)is non-trivial if and only if (i , k) is a semi-edge and equation (A11) is non-trivial if and only if i is a semi-vertex. Therefore rank = rank A − #S − #S . (A12) 2 2 E V Taking expectations 2 2 E[rank A ] = n(n − 1) p , (A13) n−2 E[#S ] = n(n − 1)(1 − p) 1 − (1 − p ) , (A14) n−1 E[#S ] = n 1 − (1 − p ) (A15) which concludes the non-regular case. For the regular case, note that equation (A9) becomes R ijk ∂ v =− v e (mod A ). (A16) ik 1 ijk∈A i =k,i →k since the e terms are removed by the projection. Hence all the semi-vertex conditions ii of equation (A11) are removed. − → Theorem A.4 If G ∼ G (n, p) then − → max (0, −n + n(n − 1)p − E[N ]) P β (G)> 0 ≥ (A17) 2 2 2 n(n − 1)p(1 − p) + n (n − 1) p where n−2 2 2 2 E[N ] = n(n − 1) p − n(n − 1)(1 − p) 1 − (1 − p ) n−1 −n 1 − (1 − p ) . (A18) Proof In theory, we could track back the bound from the theorems invoked by Corol- − → lary 4.5. Instead we use a more direct bound. Since β (G) is a non-negative random 123 T. Chaplin − → − → variable, an application of the Cauchy-Schwarz inequality to E[ β 1 ] gives β >0 − → E[ β (G)] − → P[ β (G)> 0]≥ . (A19) − → E[ β (G) ] Employing the Morse inequalities again, we see − → max(0, E[−N + N − N ]) 0 1 2 P β (G)> 0 ≥ (A20) E N where N := rank (G; Z). We obtain the numerator using the expectations for N k k 0 and N from Lemma 4.1 and the expectation of N from Lemma A.3. Then N is a 1 2 1 binomial random variable on n(n − 1) trials, each with independent probability p, and hence the second moment is 2 2 2 2 E N = n(n − 1)p(1 − p) + n (n − 1) p (A21) which concludes the proof. Remark A.5 Letting N denote the rank of the kth chain group in each of the respective chain complexes, it is quick to see that N is the same random variable across all − → complexes. In order to obtain an analogous theorem to bound P[ β (G)> 0] one need simply replace E[N ] with the computation of E rank from Lemma A.3. To obtain a result for the directed ﬂag complex, one can use the expectations from Lemma 5.3. Unfortunately, this bound is not useful for practical applications. In Fig. 6bwe plot the minimum value of this bound over all p ∈[0, 1], for a range of n. Note that the bound does not reach a signiﬁcance level of 0.1, at any p, until approximately n = 7.4 × 10 and does not reach a signiﬁcance level of 0.05 until approximately − → n = 1.2 × 10 . At these large graph sizes, computing β (G) is infeasible and hence this bound serves no practical use. A.3 Positive Betti numbers at high densities − → Finally, we tackle bounding P[ β (G)> 0] when graph density is large. In order to improve upon the naive bound available from Proposition 4.17, we provide more avenues for reducing long paths into shorter ones. Speciﬁcally, we will obtain better bounds on P[I ] and P A . This will not effect the asymptotic behaviour of the σ σ,κ bound, but may provide a substantially lower bound, at a ﬁxed n and p. In order to achieve this, we must partition P , the set of all possible undirected paths of length 3, on an n-node graph. Every undirected path of length 3 is uniquely determined by a choice of 4 distinct nodes in the graph, an ordering on these nodes (v ,v ,v ,v ), and a choice of orientation for the edges joining {v ,v } and {v ,v }. 0 1 2 3 0 1 2 3 123 First Betti number of the path homology of random... 0.05 0.25 0.045 0.2 0.04 0.035 0.15 0.03 0.025 0.1 0.02 0.015 0.01 0.005 0.05 4 5 6 7 0 50 100 150 200 10 10 10 10 (a) (b) − → − → Fig. 6 a If (n, p) falls beneath the line p (n) then Theorem A.1 implies P( β ( G (n, p)) > 0) ≤ 0.05. 4 7 Both axes are linearly scaled. b For n ∈[10 , 1.5 × 10 ], we plot the minimum value of the bound of Theorem A.4 for p ∈[0, 1]. Both axes are logarithmically scaled v v v v v v v v 1 2 1 2 1 2 1 2 v v v v v v v v 0 3 0 3 0 3 0 3 (a) (b) (c) (d) Fig. 7 The four possible ‘3-path motifs’ which partition P , shown with black edges. From left to right n n n n we see the edge orientations for σ belonging to P , P , P and P respectively. Dashed, red edges 3,0 3,1 3,2 3,3 indicate edges which must not be present for the path to be considered irreducible The edge joining the middle two nodes is assumed to be ‘forward’, i.e. via (v ,v ),so 1 2 as to avoid double counting each path. Therefore, we can partition P , based on the choices of edge orientations, into one of four classes, P for m ∈{0, 1, 2, 3}. These 3,m classes are visualised in Fig. 7. n c Lemma A.6 If σ ∈ P then P[I ] = (1 − p) , where c = (c ) = (2, 4, 4, 4) . σ m 3,m Proof The red, dashed edges shown in Fig. 7 identify ‘shortcut’ edges; if any one of these edges is present then σ is reducible. Moreover, these are the only shortcut edges, − → since the addition of any other edge would create a subgraph with β > 0. Hence, if σ ∈ P , it is irreducible if and only if none of these c edges are present. Since the 3,m existence of each edge is independent, the result follows. Lemma A.7 If σ ∈ P then 3,m l 8−l P[A ]= q p (1 − p) , (A22) σ,κ m,l l=0 123 T. Chaplin where ⎛ ⎞ 0 0 0 2 11 22 23 8 1 ⎜ ⎟ 0 0 0 4 19 33 25 8 1 ⎜ ⎟ Q = (q ) = . (A23) m,l ⎝ ⎠ 0 0 0 4 19 33 25 8 1 0 0 0 2 16 34 26 8 1 Proof Assume that σ ∈ P and κ ∈ V (G) \ V (σ ).Let q denote the number of m,l 3,m l-element subsets J ⊆ {(v, κ), (κ, v) | v ∈ V (σ )} such that κ is a generic directed centre for σ in the graph σ ∪ J . Note, q is well-deﬁned because, for a ﬁxed m,all m,l σ ∪ J are isomorphic for σ ∈ P and κ ∈ V (G) \ V (σ ). 3,m Then, conditioning on the cardinality of J , we can write σ,k P[A ]= P[A | # J = l]· P(# J = l) (A24) σ,κ σ,κ σ,κ σ,κ l=0 q 8 m,l l 8−l = · p (1 − p) . (A25) l=0 l Since q depends only on m and l, we can compute an exact value which does m,l not depend on σ or κ. This is done as follows: 1. For each m = 0, 1, 2, 3, initialise a graph G with nodes V (G ) ={v ,...,v ,κ}. m m 0 3 The edge set E (G ) consists solely of an undirected path σ , of length 3, on the vertices (v ,...,v ), such that σ ∈ P (the black, solid edges of Fig. 7). 0 3 3,m 2. Deﬁne the set of all possible linking edges L := {(v , κ), (κ, v ) | i = 0, 1, 2, 3} . i i 3. For each subset J ⊆ L, construct G := (V (G ), E (G ) ∪ J ). m,J m m 4. Set α := 1if G contains an undirected path of length 2 from v to v and m,J m,J 0 3 − → β (G ) = 0. Otherwise set α := 0. 1 m,J m,J 5. For each subset J ⊆ L,set γ := 1if α = 1 for any J ⊆ J . Otherwise set m,J m,J γ = 0. m,J 6. Then q = γ . m,l m,J J ⊆L : # J =l This algorithm was implemented as a MATLAB script and was subsequently used to compute the matrix Q given in the statement of the theorem. In step 4, Betti numbers are computed via the pathhomology package Yutin (2022), using the symbolic option. This uses MATLAB’s symbolic computational toolbox in order to avoid any numerical errors. Details on how to access the codebase are available in Sect. 1.3. 123 First Betti number of the path homology of random... − → Theorem A.8 If G ∼ G (n, p) then n−4 3 8 − → n 3 c l 8−l P β (G)> 0 ≤ 4! p (1 − p) 1 − q p (1 − p) 1 m,l m=0 l=0 2n−4 2n−6 n n 2 2 3 3 + p 1 − p + 2 p 1 − p , 2 3 (A26) where c = (c ) = (2, 4, 4, 4) and ⎛ ⎞ 0 0 0 2 11 22 23 8 1 ⎜ ⎟ 0 0 0 4 19 33 25 8 1 ⎜ ⎟ Q = (q ) = . (A27) m,l ⎝ ⎠ 0 0 0 4 19 33 25 8 1 0 0 0 2 16 34 26 8 1 Proof We follow the same approach as Proposition 4.17, but with tighter bounds. One can bound the probability that there is an irreducible, undirected 3-path, without a directed centre by ⎛ ⎞ ⎝ ⎠ P[S ]· P[I ]· [1 − P(A )] . (A28) σ σ σ,κ m=0 σ ∈P κ∈V (G)\V (σ ) 3,m By Lemma A.6 and Lemma A.7 we can bound this further by n−4 3 8 3 c l 8−l 4! p (1 − p) 1 − q p (1 − p) (A29) m,l m=0 l=0 since #P = 4! for each m. The same bounds, from Proposition 4.17, apply to 3,m 4 the probability that there is a directed cycle, of length 2 or 3, without cycle centre. Combining these bounds concludes the proof. Remark A.9 By Corollary 3.16 the bound identiﬁed in Theorem A.8 also holds for − → β (G). However, as noted in Remark 4.14, we can obtain a stronger bound by removing the term 2n−4 1 − p (A30) which corresponds to undirected cycles of length 2. To demonstrate the utility of this theorem, in Fig. 8, at each n, we plot the minimum p (n) such that the bounds from Proposition 4.17 (respectively Theorem A.8)imply − → − → t t P( β ( G (n, p)) > 0) ≤ 0.05 for all p ≥ p (n). We compute p (n) via MATLAB’s u u 123 T. Chaplin Proposition 4.17 0.9 Theorem A.8 0.8 0.7 0.6 0.5 0.4 0.3 1 2 3 10 10 10 Fig. 8 Boundaries of the parameter regions in which Proposition 4.17 and Theorem A.8 apply. If (n, p) − → − → falls above a given line then the corresponding theorem implies P( β ( G (n, p)) > 0) ≤ 0.05 fzero root-ﬁnding algorithm, with an initial interval of [0.1, 1]. For graphs on n ≤ 470 nodes, the region of p in which Theorem A.8 applies is at least 0.1 larger. With p (t ) plotted on logarithmic axes, the boundaries both appear to be straight lines with the same gradient. This demonstrates that the bound derived in Theorem A.8 would not allow for weaker asymptotic conditions on p(n) in Proposition 4.17. Finally, these same techniques can be applied to the directed ﬂag complex to get a similar explicit bound. − → Theorem A.10 If G ∼ G (n, p) then n−4 3 8 − → n 3 c l 8−l P β ( X (G)) > 0 ≤ 4! p (1 − p) 1 − q p (1 − p) 1 m,l m=0 l=0 2n−4 2n−6 n n 2 2 3 3 + p 1 − p + 2 p 1 − p , 2 3 (A31) where c = (c ) = (2, 3, 3, 4) and ⎛ ⎞ 0000516198 1 ⎜ ⎟ 00007 20208 1 ⎜ ⎟ Q = (q ) = . (A32) m,l ⎝ ⎠ 00007 20208 1 00008 22218 1 123 First Betti number of the path homology of random... Table 2 Scope of the four data collection experiments Exp. # Homology Samples n-range p-range − → −4 1 β (G) 100 [20, 150][10 , 0.15] − → 2 β (G) 100 [20, 100][0.05, 0.35] − → −4 3 β ( X (G)) 200 [20, 200][5 × 10 , 0.3] − → 4 β ( X (G)) 200 [20, 200][0.1, 0.45] Proof This follows from the same argument as Theorem A.8. The only changes are the counts of possible shortcut edges for each isomorphism class in Lemma A.6, and the output of the algorithm in the proof of Lemma A.7. Appendix B: Experimental results B.1 Data collection In order to further investigate the behaviour of path homology on random directed graphs, we sample empirical distributions of Betti numbers. Table 2 records the four experiments that were conducted. In each experiment, a number of random graphs − → were sampled from G ∼ G (n, p),for n evenly spaced in intervals of 5 in the noted n-range, and 50 values of plogarithmically spaced in the noted p-range. Then, we compute the ﬁrst Betti number of either non-regular path homology or directed ﬂag complex, as noted in the table. By logarithmically spaced in the range [a, b] we mean that values are chosen evenly spaced between log(a) and log(b) and then we apply the exponential function. We dis- cuss the reason for this logarithmic spacing in Appendix 1. Non-regular path homology is computed with the pathhomology package Yutin (2022). Unlike in Appendix A, we do not use the symbolic option and hence Betti numbers are subject to numerical errors, due to error in rank computations. Directed ﬂag complex homology is com- puted with the flagser package Lütgehetmann et al. (2020), without approximation turned on. Also note that, due to computational restrictions, Experiments 1 and 2 were occasionally stopped and restarted. These experiments were run before rng persis- tence was implemented and hence reproduction attempts may yield slightly different results. B.2 Illustrations In Fig. 9, we merge the samples from Experiments 1 and 2 for n ∈[20, 100]. We then use the colour axis to plot statistics for each of these samples, against the logarithm of each parameter on the two spatial axes. In Fig. 9a we record the empirical probability − → − → that β = 0 for each of the samples. In Fig. 9b, we record β (G)/n(n − 1)p, 1 1 − → − → where β (G) is the mean β for each random sample of graphs. In the following 1 1 123 T. Chaplin − → Fig. 9 Statistics for the path homology of samples of 100 random directed graphs G ∼ G (n, p), sampled at a range of parameter values, plotted against the natural logarithm of the parameters. Our primary contribution is descriptions of the boundaries of the darker, blue region in (a) and a limiting value for the lighter, yellow region of (b) as n →∞ informal discussion, we refer to these ﬁgures as proxies for the exact probabilities and expectations of the distributions from which we sample. We observe two distinct transitions between three distinct regions in parameter − → space. Namely, when graph density is relatively low P[ β = 0] is almost 1. Next, − → − → there is a ‘goldilocks’ region in which suddenly P[ β = 0] is close to 0 and E[ β ] 1 1 appears to be growing. Finally, when density is too large, we transition back to a regime − → in which P[ β = 0] is almost 1. Thanks to the logarithmic scaling of the parameter axes, the boundaries between these regions appear to be straight lines. Theorem 1.4 describes the fate of straight line trajectories through this diagram. Theorem 1.4(3-4) says that a straight line with gradient m < −1 (resp. m > −1/3) will eventually cross into and remain in the lower (resp. upper) yellow region of − → Fig. 9a, where P( β = 0) is close to 1. Theorem 1.4(2) says that a straight line with gradient −1 < m < −2/3 will eventually reach the blue region of Fig. 9a, − → where P( β = 0) is close to 0. In particular, this implies that the gradient of the lower boundary region tends towards −1 and the gradient of the upper boundary is eventually in the region [−2/3, −1/3]. Finally, Theorem 1.4(1) says that a straight line with gradient −1 < m < −2/3 will eventually reach the yellow region of Fig. 9b and the colour will approach 1. In Fig. 10, we merge the samples from Experiments 3 and 4 for n ∈[20, 200].This ﬁgure provides Theorem 1.6 with a similar interpretation, as above, except that the upper boundary is eventually in the region [−1/2, −1/4]. It is worth reiterating that these interpretations and results all hold in the limit. That is, Theorem 1.4 provides no guarantees for a ﬁnite line segment, regardless of its gradients or length. However, we do observe that the boundaries between the three regions converge onto straight lines, of the correct gradient, relatively quickly 123 First Betti number of the path homology of random... − → Fig. 10 Statistics for the directed ﬂag complex homology of samples of 200 random graphs G ∼ G (n, p) sampled at a range of parameter values (i.e. within n ≤ 50 nodes). We will see empirical evidence for this in the following section. B.3 Finding boundaries Note, Theorem 1.4 says nothing of the region −2/3 <α < −1/3. In the follow- ing discussion we attempt to determine, empirically, the equations of the boundaries between the positive region and the two zero regions identiﬁed in Fig. 9.Thispro- vides evidence to support the conjecture that the zero region for path homology can be expanded to (−∞, −1) ∪ (−2/3, 0]. − → − → Conjecture B.1 For an Erdos–Rényi ˝ random directed graph G ∼ G (n, p(n)),let β denote the 1st Betti number of its non-regular path homology. Assume p(n) = n ,if − → α> −2/3 then β (G) = 0 with high probability. The same holds for regular path homology. Using the samples from Experiment 1, for each n, we determine the maximum p (n) − → − → such that for all p ≤ p (n) we observe P[ β (G) = 0]≥ 0.95 for G ∼ G (n, p), l 1 where P denotes the empirical probability, derived from our sampled distribution. Similarly, using the samples from Experiment 2, we determine the minimum p (n) − → − → such that for all p ≥ p (n) we observe P[ β (G) = 0]≥ 0.95 for G ∼ G (n, p). u 1 Since we anticipate a power-law relationship, the logarithmic spacing of p allows us to achieve greater precision as n increases, since the values of log(p) are evenly spaced. Moreover, we chose the boundaries of the p-region so that precision is greater near the lower boundary in Experiment 1 and near the upper boundary in Experiment 2. 123 T. Chaplin 0.26 -2 0.24 0.22 0.2 0.18 0.16 0.14 0.12 0.1 -3 50 100 150 20 40 60 80 100 (a) (b) − → Fig. 11 Over a range of parameters (n, p) we measure the ﬁrst Betti number, β (G), for 100 sampled − → random graphs G ∼ G (n, p). Then, at each n, we determine maximum p (n) (and minimum p (n))such l u − → − → that for all p ≤ p (n) (and all p ≥ p (n)) at most 5% of graphs sampled from G (n, p) have β (G)> 0. l u 1 The ﬁgures show log–log plots of these two functions. In both cases, we ﬁt a line of best ﬁt in order to obtain an approximate power-law relationship We then compute a least-squares, line of best ﬁt between log(p (n)) and log(n),to obtain a power-law relationship of the form p (n) = An . We repeat this for the upper boundary to obtain a similar relationship for p (n). The results of this experiment are shown in Fig. 11. Figure 11a shows that the empirical lower boundary has a similar dependency −1 on n to that predicted by Theorem 1.4(2, 3), i.e. p (n) ∼ n . Moreover, Fig. 11a contains a plot of p (n), as deﬁned in Appendix A.1. For a parameter pair (n, p) − → falling below this line, Theorem A.1 implies P[ β (G)> 0]≤ 0.05. We observe that this theoretical boundary of signiﬁcance lies very close to the observed, experimental boundary, indicating that Theorem A.1 is close to the best possible bound. −0.660 Conversely, Fig. 11b predicts an upper boundary of p (n) ∼ n . This is consis- tent with Theorem 1.44 since −0.660 < −1/3, but indicates that there is signiﬁcant room for improvement. This suggests that the hypothesis of Theorem 1.44 can be weakened to α> −2/3. However, short of a stronger theoretical result, we require more experiments with graphs on n > 150 nodes to conﬁrm this; computational complexity is currently the limiting factor. In Fig. 12 we repeat the same analysis with Experiments 3 and 4 respectively, in order to discern the boundaries of the positive region for directed ﬂag complex homology. Again, Fig. 12a shows that the empirical lower boundary has a similar −1 dependency on n to that predicted by Theorem 1.6(3, 4), i.e. p (n) ∼ n .Fig. 11b −0.443 shows an upper boundary of p (n) ∼ n . This is also consistent with Theo- rem 1.65 since −0.437 < −1/4. This provides evidence that the zero region for directed ﬂag complex can be expanded as far as (−∞, −1) ∪ (−1/2, 0]. 123 First Betti number of the path homology of random... 0.4 -2 0.35 0.3 0.25 0.2 -3 0.15 50 100 150 200 50 100 150 200 (a) (b) − → Fig. 12 As for Fig. 11 but for 200 samples of β ( X (G)) − → − → Fig. 13 Results for 10 normality tests on samples of β (G) for G ∼ G (n, p) at a range of n and p. Red rectangles indicate that at least 5% of samples were zero and hence are excluded from the experiment. Colour indicates the P-value for the hypothesis test in question. Finally, for each test and at each n,we average the P-value of the range of relevant p, which is recorded on the line graph. Note adjacent densities, p, on the horizontal axis are shown with equal width, despite being logarithmically spaced B.4 Testing for normal distribution In analogy to known results for the clique complex (Kahle and Meckes 2013, The- orem 2.4), one conjecture is that, in the known positive region, the normalised Betti − → number β approaches a normal distribution. 123 T. Chaplin − → Fig. 14 As Fig. 13 but for β ( X (G)) −1 Conjecture B.2 If G ∼ G(n, p), where p = p(n) with p(n) = ω(n ) and p(n) = −2/3 o(n ), then − → − → β (G) − E β (G) 1 1 ' ⇒ N (0, 1) as n →∞ (B.1) − → Var β (G) where N (0, 1) is the normal distribution with mean 0 and variance 1. To provide some empirical evidence towards this conjecture, we perform 10 normality − → tests on the distributions of β , obtained in Experiment 1. We restrict our focus to the samples in which at most 5% of samples were zero, so that we are in a parameter region where we hope our conjecture would apply. We normalise each of the remaining samples and perform 10 hypothesis tests under the null hypothesis that the samples come from normal distributions. To avoid confu- sion with the null model parameter, we refer to the signiﬁcance of these hypothesis tests as P-values. These tests are computed with the MATLAB package normalitytest Öner et al. (2017). The P-values (and names of the tests) are recorded in Fig. 13, along with the average P-value against edge-inclusion probability p. In all tests, we see a noisy but consistent trend: there is a decreasing amount of evidence for discarding the null hypothesis as n →∞. − → In Fig. 14, we repeat this analysis with the distributions of β ( X (G)) collected in Experiment 3. Again we observe a similar but stronger trend: there is a decreasing amount of evidence for discarding the null hypothesis as n →∞. − → While no individual test is sufﬁcient to conclude that β tends towards a normal distribution, the ensemble of tests provide good evidence towards this claim. Larger sample sizes, as well as samples at larger n, are required for more convincing evidence. 123 First Betti number of the path homology of random... References Aalto, A., Viitasaari, L., Ilmonen, P., Mombaerts, L., Gonçalves, J.: Gene regulatory network inference from sparsely sampled noisy data. Nature Commun. 11(1), 3493 (2020). https://doi.org/10.1038/s41467- 020-17217-1 Alon, N., Spencer, J.H.: The Probabilistic Method, 4th edn. Wiley series in discrete mathematics and optimization. Wiley, Hoboken, New Jersey (2016) Caputi, L., Pidnebesna, A., Hlinka, J.: Promises and pitfalls of topological data analysis for brain connectivity analysis. NeuroImage 238, 118245 (2021). https://doi.org/10.1016/j.neuroimage.2021.118245 Chaplin, T.: First Betti number of the path homology of random directed graphs - Code and Data Repository. https://github.com/tomchaplin/phrg-code Chaplin, T.: First Betti number of the path homology of random directed graphs - Code and Data Repository. OSF (2022). https://doi.org/10.17605OSF.IO/ZVUMB. https://osf.io/zvumb/ Chen, L.H.Y., Goldstein, L., Shao, Q.-M.: Fundamentals of Stein’s Method, pp. 13–44. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-15007-4_2 Chowdhury, S., Mémoli, F.: Persistent Path Homology of Directed Networks, pp. 1152–1169 (2018). https:// doi.org/10.1137/1.9781611975031.75 Dwass, M.: Modiﬁed randomization tests for nonparametric hypotheses. Ann. Math. Stat. 28(1), 181–187 (1957). https://doi.org/10.1214/aoms/1177707045 Erdos, ˝ P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5(1), 17–60 (1960) Grigor’yan, A., Lin, Y., Muranov, Y., Yau, S.-T.: Homologies of path complexes and digraphs (2012). arXiv:1207.2834 [math.CO] Grigor’yan, A., Lin, Y., Muranov, Y., Yau, S.-T.: Homotopy theory for digraphs. Pure Appl. Math. Q. 10(4), 619–674 (2014). https://doi.org/10.4310/PAMQ.2014.v10.n4.a2 Grigor’yan, A.A., Lin, Y., Muranov, Y.V., Yau, S.-T.: Path complexes and their homologies. Journal of Mathematical Sciences 248(5), 564–599 (2020). https://doi.org/10.1007/s10958-020-04897-9 Helm, A., Blevins, A.S., Bassett, D.S.: The growing topology of the C. elegans connectome. bioRxiv (2021). https://doi.org/10.1101/2020.12.31.424985 Ingram, P.J., Stumpf, M.P., Stark, J.: Network motifs: structure does not determine function. BMC Genomics 7(1), 1–12 (2006). https://doi.org/10.1186/1471-2164-7-108 Kahle, M.: Topology of random clique complexes. Discrete Math. 309(6), 1658–1671 (2009). https://doi. org/10.1016/j.disc.2008.02.037 Kahle, M.: Sharp vanishing thresholds for cohomology of random ﬂag complexes. Ann. Math. (2014). https://doi.org/10.4007/annals.2014.179.3.5 Kahle, M., Meckes, E.: Limit theorems for Betti numbers of random simplicial complexes. Homol. Homo- topy Appl. 15(1), 343–374 (2013). https://doi.org/10.4310/HHA.2013.v15.n1.a17 Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection (2014). http://snap. stanford.edu/data Lütgehetmann, D., Govc, D., Smith, J.P., Levi, R.: Computing persistent homology of directed ﬂag com- plexes. Algorithms (2020). https://doi.org/10.3390/a13010019 Öner, M., Deveci Kocakoç, I.: Jmasm 49: A compilation of some popular goodness of ﬁt tests for nor- mal distribution: Their algorithms and matlab codes (matlab). Journal of Modern Applied Statistical Methods 16(2), 30 (2017). https://doi.org/10.22237/jmasm/1509496200 Purves, D., Augustine, G.J., Fitzpatrick, D., Hall, W., LaMantia, A., McNamara, J., White, L. (eds.): Neuroscience, 6th edn. Sinauer Associates, New York (2018) Reimann, M.W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., Dłotko, P., Levi, R., Hess, K., Markram, H.: Cliques of neurons bound into cavities provide a missing link between structure and function. Front. Comput. Neurosci. 11, 48 (2017). https://doi.org/10.3389/fncom.2017.00048 Yutin, M.: Performant Path Homology. https://github.com/SteveHuntsmanBAESystems/ PerformantPathHomology Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afﬁliations.

http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Journal of Applied and Computational Topology Springer Journals

http://www.deepdyve.com/lp/springer-journals/first-betti-number-of-the-path-homology-of-random-directed-graphs-1RQKNfPtCP

Loading next page...

Publisher: Springer Journals
Copyright: Copyright © The Author(s) 2022
ISSN: 2367-1726
eISSN: 2367-1734
DOI: 10.1007/s41468-022-00108-3
Publisher site: See Article on Publisher Site

Abstract

Journal

Journal of Applied and Computational Topology – Springer Journals

Published: Dec 4, 2022

Keywords: Path homology; Directed flag complex; Stochastic topology; Directed graphs; Random graphs; 05C20; 05C80; 55U15; 60C05; 62F03

References

Gene regulatory network inference from sparsely sampled noisy data

Aalto, A; Viitasaari, L; Ilmonen, P; Mombaerts, L; Gonçalves, J
Promises and pitfalls of topological data analysis for brain connectivity analysis

Caputi, L; Pidnebesna, A; Hlinka, J
Modified randomization tests for nonparametric hypotheses

Dwass, M
On the evolution of random graphs

Erdős, P; Rényi, A
Homotopy theory for digraphs

Grigor’yan, A; Lin, Y; Muranov, Y; Yau, S-T
Path complexes and their homologies

Grigor’yan, AA; Lin, Y; Muranov, YV; Yau, S-T
Network motifs: structure does not determine function

Ingram, PJ; Stumpf, MP; Stark, J
Topology of random clique complexes

Kahle, M
Sharp vanishing thresholds for cohomology of random flag complexes

Kahle, M
Limit theorems for Betti numbers of random simplicial complexes

Kahle, M; Meckes, E
Computing persistent homology of directed flag complexes

Lütgehetmann, D; Govc, D; Smith, JP; Levi, R
Cliques of neurons bound into cavities provide a missing link between structure and function

Reimann, MW; Nolte, M; Scolamiero, M; Turner, K; Perin, R; Chindemi, G; Dłotko, P; Levi, R; Hess, K; Markram, H

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

First Betti number of the path homology of random directed graphs

First Betti number of the path homology of random directed graphs

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

First Betti number of the path homology of random directed graphs

First Betti number of the path homology of random directed graphs

Abstract

Journal

Recommended Articles

References

Our policy towards the use of cookies