Avalanche homology of digraphs via sandpile dynamics
January 01, 1970
1 Introduction↩︎
The sandpile model is a discrete dynamical system on a graph \(G\). Its states are configuration vectors \(\mathbf{c}_t \in \mathbb{N}^n\), whose elements denote the number of grains of sand on each of the \(n\) vertices of \(G\); the process begins from the initial configuration \(\mathbf{c}_0\). If at some time step a vertex has more grains than its degree, this vertex is unstable and fires by sending one grain to each of its neighbours, thus lowering the number of grains on it by the corresponding amount. The dynamics reaches a stable configuration when there are no more unstable vertices. The sandpile model arose from physics as a lattice model for self-organised criticality [1]. Independently it was introduced for general graphs in combinatorics literature under the name chip-firing game [2].
It is fascinating that such a simple model connects to a wide range of different mathematics. An early algebraic momentum came from the realisation that the sandpile model attaches to a graph \(G\) a finite Abelian sandpile group [3]. This group is formed by the recurrent states in the sandpile model, and its size equals the number of spanning trees of \(G\). The group appears as the Jacobian or Picard group in arithmetic geometry and in the discrete study of algebraic curves and Riemann surfaces [4], [5]; around the same circle of ideas the sandpile model is related to a Riemann-Roch theorem on graphs [6]. The sandpile model on a grid graph with a very large number of initial grains produces fractal structures whose emergence is still an open mathematical question, for some progress see [7]. The model is closely intertwined with numerous combinatorial objects including permutations, words, tableaux, lattice paths, parking functions, polyominoes and the Tutte polynomial [8]–[13]. For a textbook introduction to the sandpile model and its many aspects we refer to [14].
The sandpile model on digraphs (directed graphs) differs from the above simply by changing the firing threshold of a vertex \(v\) from its degree to its out-degree, i.e.the number of directed edges emanating from \(v\). Similarly the fired grains are only added to \(v\)’s out-neighbours. For developments parallel to the ones cited above see for example [15]–[18]. Recent works established fascinating connections between the sandpile model on digraphs and Leavitt path algebras and their \(K\)-theory [19], [20].
Despite the multi-faceted mathematical developments around the sandpile model, to the best of our knowledge not much work exists from the perspective of homology and homotopy theory. The model has been extended to take place on cell complexes, see [14] and references therein, but there is no direct association of homology or homotopy groups. In this paper, we initiate such an approach by introducing a homology theory for sandpile dynamics, which we call avalanche homology. An avalanche in the sandpile model means firing an unstable vertex, and then performing all subsequent firings until a stable configuration is reached; very concretely a sequence of unstable vertices “avalanches" into a stable state. Equally well we can consider firing all unstable vertices simultaneously at a given time step; such a scheme is often referred to as parallel firing [21] or cluster firing [14]. In this paradigm, we call the sets of simultaneously fired vertices the firing sets. A key observation is that every subset of a firing set is also a set of vertices which fire simultaneously. This motivates our main definition, and we call the simplicial complex generated by the firing sets the avalanche complex \(\mathcal{A}(G,\mathbf{c}_0)\) of the digraph \(G\), for a given initial configuration \(\mathbf{c}_0\); avalanche homology is the simplicial homology of this complex.
Section 2 introduces in detail the sandpile dynamics, and the avalanche complex along with its basic properties for general digraphs. Of particular importance is viewing avalanche homology via the nerve of a cover in Section 2.2, which gives very efficient computations. Our main motivation in this first work is to understand the range of homologies and homotopy types of the avalanche complex for certain initial configurations on paths \(P_n\) and cycles \(C_n\). These results are proved in Section 3 and summarised in Table 1. One of our main results is Theorem 1, which shows that for cycles one need only consider the so called binary configurations. The avalanche complex for the initial configuration \(\mathbf{c}_0 = (1,\dots,1,0\dots,0)\) on a cycle \(C_n\) turns out to be the nerve complex of circular arcs [22], thus we obtain the homotopy types in Theorem 2.
Due to the dependence of the avalanche complex on the initial configuration, avalanche homology is “parametrised" by \(\mathbb{N}^n\). By starting the dynamics with different initial configurations, the avalanche complex can exhibit varied topologies on a single digraph, which in itself can be topologically trivial. We illustrate this in Section 3.3 by comparing to the recently introduced burning homology [23] and to the homology of the directed flag complex.
On one hand, our work stems from the ongoing active development of homology and homotopy theories in the world of (di)graphs [24]–[33]. Avalanche homology gives a new theory which bridges to various other fields via the sandpile model. In particular, given a simplicial homotopy type one can ask for its incarnation through the avalanche complex on some graph, and then explore connections to some of the unexpected domains referenced above. On the other hand, we are driven by topological data analysis [34]–[38], and in Section 4 we look at persistent avalanche homology. Our thesis is that the dynamics yields a natural filtration of \(\mathcal{A}(G,\mathbf{c}_0)\) one simplex at a time and it is potentially much more interesting, even mathematically, to look at this persistent homology rather than just avalanche homology which is, in a sense, the “stabilised" homology of the dynamics; we make this point of view clear in Section 4. We conclude with a discussion of open questions in Section 5.
As a final note, in this paper we are interested in the avalanche homology of directed graphs, but our framework extends naturally to the undirected case. We focus our attention on digraphs for three main reasons. Firstly, in this initial work we prove various topological results to understand the behaviour of the theory. The undirected case is combinatorially more complex due to a lack of directed flow of the fired grains, and hence the directed case seems more tractable. Secondly, the undirected case can be modelled by the directed case, simply by making every edge bidirectional. Thirdly, as already mentioned, we are interested in applications of the theory in fields such as neuroscience, where synaptic networks are naturally directed [37].
Acknowledgements↩︎
We thank Daisuke Kishimoto for pointing out the connection to the nerve of a cover in Section 2.2.
2 Sandpiles and avalanche homology↩︎
We begin by introducing the sandpile model on directed graphs, for a more detailed introduction see [14] and for further background on digraphs see [39]. Throughout we consider a digraph \(G=(V,E)\) to be simple and finite, although the framework can easily be extended to non-simple digraphs, and even infinite digraphs. We denote the directed edges in \(E\) by ordered pairs \((v,w)\), the out-neighbours of a vertex \(v\) are the vertices \(w\) such that \((v,w) \in E\), and the out-degree of \(v\) is \(\mathrm{outdeg}(v) = |\{(v,w) \;| \;w \in V\}|\). Note that we consider \(0\in\mathbb{N}\), thus our time step \(t\) in the following definition of the sandpile model starts at \(0\).
Definition 1. The sandpile model on a digraph \(G\) with \(n\) vertices is a discrete dynamical system with dynamics defined as follows:
a configuration at time \(t\in\mathbb{N}\) is a vector \(\mathbf{c}_t \in \mathbb{N}^n\), where \(\mathbf{c}_t(v)\) represents the number of grains of sand on vertex \(v\);
a vertex \(v\) is unstable at time \(t\) if \(\mathbf{c}_t(v) \geq \mathrm{outdeg}(v)\);
an unstable vertex fires by sending one grain to each out-neighbour \(w\), thus the number of grains on each out-neighbour increases by \(1\) and the grains on \(v\) decrease by \(\mathrm{outdeg}(v)\);
at each time step \(t\in \mathbb{N}\) an unstable vertex \(v\) is chosen to fire, and \(\mathbf{c}_{t+1}\) is the configuration after firing \(v\); if all vertices are stable the process terminates.
See Figure 2 for an example of the ensuing process.
The sandpile dynamics is conveniently captured by the Laplacian \[\Delta(G)=D_\mathrm{out}(G) - A(G),\] where \(A(G)\) is the adjacency matrix of \(G\) and \(D_\mathrm{out}(G)\) is the diagonal matrix with values \(\mathrm{outdeg}(v)\) on the diagonal, respective to the vertex ordering of \(A(G)\). Going from a configuration \(\mathbf{c}_t\) to \(\mathbf{c}_{t+1}\) by firing a vertex \(v_i\) is then given by \[\mathbf{c}_{t+1} = \mathbf{c}_t - \Delta^T e_i,\] where \(\Delta=\Delta(G)\) and \(e_i\) is the standard basis vector with value 1 in position \(i\) and zeros elsewhere.
In Definition 1 each firing is determined by the choice of an unstable vertex. It is also possible to fire simultaneously all vertices \(\sigma_t \subseteq V\) that are unstable at a time step \(t\); such firing is usually referred to in the literature as cluster or parallel firing [14], [21]. See Figure 3 for an example. This dynamics is again conveniently given by \[\label{eq:parallel95firing95dynamics} \mathbf{c}_{t+1} = \mathbf{c}_t - \Delta^T \chi_{\sigma_t},\tag{1}\] where \(\chi_{\sigma_t} = \sum_{j} e_j\) and \(e_j\) is the standard basis vector corresponding to the vertex \(v_j \in \sigma_t\). We capture the parallel firing dynamics of 1 for a given digraph and an initial configuration in the following definition.
Definition 2. Let \(\mathbf{c}_0\) denote the initial configuration on a digraph \(G\), and consider the sandpile model on \(G\) using the parallel firing procedure. Define \[\text{Sp}(G,\mathbf{c}_0) = \{(\mathbf{c}_t,\sigma_t)\}_{t\in\mathbb{N}},\] where \(\sigma_t \subseteq V\) is the firing set of unstable vertices of configuration \(\mathbf{c}_t\), i.e.the vertices which fire at time \(t\) taking \(\mathbf{c}_t\) to \(\mathbf{c}_{t+1}\).
A sink is a vertex \(s\) of \(G\) with no out-neighbours, i.e.\(\mathrm{outdeg}(s)=0\). Such a vertex would always trivially fire in the sandpile model. As such, sink vertices are often treated as special vertices in the sandpile model, which do not fire but instead absorb grains and remove them from the dynamics. In this paper we explicitly do not consider sink vertices to belong to the firing sets \(\sigma_t\). We depict sink vertices by .
A foundational result for the sandpile on undirected graphs states that if a sink is present the sandpile model will always stabilise [14]. A similar result holds for digraphs, with the stronger requirement that there is a directed path from every vertex to a sink. In this paper we do not require that the dynamics stabilises, and allow for it to continue infinitely.
2.1 Avalanche complex and avalanche homology↩︎
We now associate a simplicial homology to the (parallel firing) sandpile dynamics of a digraph. Recall that for any set \(V\) and any finite collection of subsets \(F = \{\sigma \;| \;\sigma \subset V\}\), the simplicial complex generated by \(F\) is obtained by downwards closing \(F\), that is, taking the set of all subsets of the sets in \(F\). We let \(\sigma \in \text{Sp}(G,\mathbf{c}_0)\) mean that the set of vertices \(\sigma\) fires at some time step \(t\) in the dynamics of Definition 2.
Definition 3. The avalanche complex of \(G\) with respect to the initial configuration \(\mathbf{c}_0\), denoted \(\mathcal{A}(G,\mathbf{c}_0)\), is generated by the firing sets \(\sigma \in \text{Sp}(G,\mathbf{c}_0)\). The avalanche homology is the simplicial homology of \(\mathcal{A}(G,\mathbf{c}_0)\).
See Figure 4 for an illustration of Definition 3. Note that if during the sandpile dynamics a subset of vertices \(\sigma \subseteq V\) fires simultaneously, then any \(\tau \subseteq \sigma\) also fires simultaneously, hence the definition of avalanche complex is well defined with respect to the underlying parallel firing model. Also note that the set of maximal firing sets with respect to inclusion is the minimal generating set for the avalanche complex, which we utilise in Section 3. However, determining the maximal firing sets requires the full information of the dynamics, whereas our definition allows sequential construction; see also Section 4. In the sandpile literature an avalanche means firing a vertex or a set of vertices, followed by stabilising the resulting configuration. In our context the dynamics \(\text{Sp}(G,\mathbf{c}_0)\) can either stabilise, or result in a periodic orbit which can be considered as an infinite non-stabilising avalanche.
For the avalanche complex to be finite, we require that if the dynamics does not stabilise then it enters a periodic orbit, where the same sequence of configurations keeps occurring. Note that for any finite digraph and a finite number of grains, there are only a finite number of possible configurations. If the dynamics does not stabilise some configuration must eventually occur twice resulting in a periodic orbit.
Remark 1. Note that we can take any finite subset of \(\text{Sp}(G,\mathbf{c}_0)\) including time steps from \(t=0\) to some \(t=t_n\), and generate a complex \(\mathcal{A}_{t_n}(G,\mathbf{c}_0)\) for this finite sub-dynamics. In general such a complex will be different from \(\mathcal{A}(G,\mathbf{c}_0)\). However, if the dynamics enters a recurring orbit, then \(\mathcal{A}_{t_n}(G,\mathbf{c}_0) \simeq \mathcal{A}(G,\mathbf{c}_0)\) where \(t_n\) is the last time step before a recurring configuration reappears. Such complexes will appear in Section 3.2 in connection to cycle graphs.
Remark 1. If we were to include sink vertices in firing sets, then since every sink vertex is always unstable it would be in every firing set. Hence, sink vertices would be cone points of the avalanche complex, causing it to always be contractible.
Let \(|\mathbf{c}_t|\) denote the total number of grains in a configuration; note that if there is no sink, then \(|\mathbf{c}_0|\) is constant during the whole dynamics. We begin with some initial observations for general digraphs. If at some time step \(t\) all the vertices \(V\) fire, the avalanche complex is the full simplex on \(V,\) yielding the following result.
Lemma 1. If \(V \in \text{Sp}(G,\mathbf{c}_0)\), then \(\mathcal{A}(G,\mathbf{c}_0)\) is contractible.
By Lemma 1 it could be wondered whether the avalanche complex is always contractible when \(|\mathbf{c}_0| \geq |V|\). This is not generally the case.
Example 1. Consider the digraph \(G\) below with the shown initial configuration. The firing sets are \[\begin{align} \sigma_0 &= \{v_1\}, \;\sigma_1 = \{v_1,v_2\}, \;\sigma_2 = \{v_2,v_3\}, \;\sigma_3 = \{v_1,v_3\}\\ \sigma_4 &= \{v_2\},\sigma_5 = \{v_3\}, \;\sigma_6 = \{v_1\}, \;\sigma_7 = \{v_2\}, \;\sigma_8 = \{v_3\}, \end{align}\] after which the dynamics reaches a stable configuration.
Figure 5: 
.
The avalanche complex is homotopy equivalent to \(S^1\). Hence the topology of \(\mathcal{A}(G,\mathbf{c}_0)\) is non-trivial despite the total number of grains exceeding the number of vertices.
If a configuration is stable, then no firings happen, so we get an empty complex. And if we only have a single grain of sand, the complex is similarly trivial.
Lemma 2. If \(\mathbf{c}_0\) is a stable configuration, then \(\mathcal{A}(G,\mathbf{c}_0)=\emptyset\).
Lemma 3. If \(|\mathbf{c}_0|\le1\), then \[\mathcal{A}(G,\mathbf{c}_0)= \begin{cases} \emptyset,& if |\mathbf{c}_0|=0,\\\emptyset,& if |\mathbf{c}_0|=1\text{ and }\mathbf{c}_0\text{ is stable},\\ \bigsqcup_k \ast & if |\mathbf{c}_0|=1\text{ and }\mathbf{c}_0\text{ is unstable}. \end{cases}\]
Proof. The first two cases follow immediately from Lemma 2. If \(|\mathbf{c}_0|=1\) and is unstable, then each firing set must consist of a single point, thus the avalanche complex is some number of disconnected points. ◻
2.2 Avalanche homology via nerve of a cover↩︎
The avalanche complex is generated by the firing sets \(\sigma_t\). Hence \(\mathcal{C}=\{\sigma_t\}_{t\in[t_n]}\) immediately yields a cover of \(\mathcal{A}(G,\mathbf{c}_0)\), where \(t_n\) is the time until stabilisation or recurrent orbit and \([t_n]=\{0,1,\ldots,t_n\}\). The nerve of \(\mathcal{C}\), \(N(\mathcal{C})\), is the simplicial complex with vertex set \(\mathcal{C}\) and with a simplex \(\{\alpha_1,\alpha_2,\dots,\alpha_q\}\) whenever \(\bigcap \sigma_{\alpha_i} \ne \emptyset\). Since all the elements in this cover are simplices, and hence all intersections \(\sigma_{\alpha_1} \cap \sigma_{\alpha_2} \cap \cdots \cap \sigma_{\alpha_q}\) are acyclic, it follows that we can view avalanche homology as the homology of \(N(\mathcal{C})\) (see for example [40]): \[H_k(\mathcal{A}(G,\mathbf{c}_0)) \approx H_k(N(\mathcal{C})), \quad \text{for all } k \geq 0.\] A priori each generating firing set of \(\mathcal{A}(G,\mathbf{c}_0)\) can contain a large number of vertices. This results in a chain complex where we would need to compute homology at very high degrees. Even though our definition of \(\mathcal{A}(G,\mathbf{c}_0)\) and avalanche homology provides the conceptually direct connection to avalanche dynamics, the above cover gives a much more condensed simplicial basis for homology computations. We confirmed this in our implementation where the homology of the nerve gave orders of magnitude faster computation, with significantly reduced memory requirements, which can be seen in Table 1.
| \(k\) | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 | 55 | 60 | 65 | 70 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Nerve (ms) | 1.20 | 1.21 | 1.25 | 1.19 | 1.28 | 1.32 | 1.28 | 1.32 | 1.36 | 1.50 | 1.46 | 1.44 | 1.61 | 1.77 |
| Avalanche (ms) | 1.13 | 3.25 | 38220 | 44848 | - | - | - | - | - | - | - | - | - | - |
3 Avalanche homology of paths and cycles↩︎
In order to understand what avalanche homology is capturing of the dynamics, in this section we consider the avalanche homology of some specific classes of simple digraphs. We prove some results on paths (with a sink) and on cycles (without a sink). We see that even on these basic digraphs we have complicated avalanche homology appearing, depending on the initial configuration.
3.1 Path digraphs↩︎
Let \(P_n\) be the directed path graph on \(n+1\) vertices \(v_1,\dots,v_{n+1}\), and edges \((v_i,v_{i+1})\) for \(i = 1,\dots,n\). The final vertex \(v_{n+1}\) is a sink, thus we do not include it in the avalanche complex. All configurations on \(P_n\)’s will be written as vectors with \(n\) elements. See Example 2.
Example 2. Consider the path \(P_5\) with \(\mathbf{c}_0=(2,0,1,0,0)\) as shown below:
Figure 6: 
.
The maximal simplices of \(\mathcal{A}(P_5,\mathbf{c}_0)\) are \((v_1,v_3)\), \((v_1,v_2,v_4)\), \((v_2,v_3,v_5)\), \((v_3,v_4)\), and \((v_4,v_5)\). The corresponding simplicial complex is illustrated below, which is homotopy equivalent to \(S^1 \vee S^1 \vee S^1\).
Figure 7: 
.
We begin with a simple result that relates \(P_n\) to smaller paths when certain vertices do not appear in the dynamics.
Lemma 4. If \(\mathbf{c}_0\) begins with \(\ell\) zeros, then \[\mathcal{A}(P_n,\mathbf{c}_0)=\mathcal{A}(\widehat{P}_{n-\ell},\widehat{\mathbf{c}}_0),\] where \(\widehat{\mathbf{c}}_0\) is obtained from \(\mathbf{c}_0\) by deleting the leading zeros, and \(\widehat{P}_{n-l}\) is obtained from \(P_n\) by deleting the first \(\ell\) vertices.
Proof. Consider the first zero in \(\mathbf{c}_0\). The corresponding vertex \(v_1\) never fires, thus \(v_1\) is not in \(\mathcal{A}(P_n,\mathbf{c}_0)\). With respect to vertex indices in \(P_n\), the firing sets are the same in the complex \(\mathcal{A}(\widehat{P}_{n-1},\widehat{\mathbf{c}}_0)\), where \(\widehat{\mathbf{c}}_0\) is obtained from \(\mathbf{c}_0\) by deleting the \(0\) in position \(1\), and \(\widehat{P}_{n-1}\) is obtained from \(P_n\) by deleting vertex \(v_1\). The result then follows by induction. ◻
Next we consider some simple results on when \(\mathcal{A}(P_n,\mathbf{c}_0)\) is contractible. A configuration \(\mathbf{c}\) is binary if each of its elements is either 1 or 0.
Lemma 5. If \(\mathbf{c}_0\) is a binary configuration where all \(1\)’s appear in a consecutive block, i.e. \[\mathbf{c}_0=(0,0,\ldots,0,1,1,\ldots,1,0,\ldots,0),\] then \(\mathcal{A}(P_n,\mathbf{c}_0)\) is contractible.
Proof. By Lemma 4 we can restrict to \(\mathcal{A}(\widehat{P}_{n-(\ell-1)},\widehat{\mathbf{c}}_0)\), where \(\ell\) is the location of the first \(1\) in \(\mathbf{c}_0\). The set of maximal simplices is \[\{(v_i,v_{i+1},\ldots,v_{i+(k-1)})\, | \, i=\ell,\ldots,n-k \},\] where \(k=|\mathbf{c}_0|\). This is a path of \((k-1)\)-simplices with each consecutive pair of simplices sharing a codimension 1 face, thus is contractible. ◻
Lemma 6. If the first \(\lceil\frac{n+1}{2}\rceil\) positions of \(\mathbf{c}_0\) are all non-zero, then \(\mathcal{A}(P_n,\mathbf{c}_0)\) is contractible.
Proof. Vertex \(v_{\lceil\frac{n+1}{2}\rceil}\) is in every maximal simplex, thus is a cone point of \(\mathcal{A}(P_n,\mathbf{c}_0)\). ◻
Lemma 7. If the last \(\lfloor\frac{n+1}{2}\rfloor\) positions of a binary configuration \(\mathbf{c}_0\) are all non-zero, then \(\mathcal{A}(P_n,\mathbf{c}_0)\) is contractible.
Proof. Every maximal simplex contains \(v_n\). To see this suppose for a contradiction \(v_n\not\in \sigma_t\) for some maximal simplex \(\sigma_t\). Then \(\sigma_t\) also cannot contain any vertices \(v_i\) for \(i<\lfloor\frac{n+1}{2}\rfloor\), since the only way for \(v_n\) to not fire is that the sandpile has fired at least \(t = \lfloor\frac{n+1}{2}\rfloor\) times, so that all grains initially in the final \(\lfloor\frac{n+1}{2}\rfloor\) positions have reached the sink. Thus the first \(\lfloor\frac{n+1}{2}\rfloor\) positions in \(\mathbf{c}_t\) must also all be zero, so are not in \(\sigma_t\). Therefore, the vertices of \(\sigma_t\) are a strict subset of the non-zero elements in \(\mathbf{c}_0\), thus \(\sigma_t\) is not maximal, so we get a contradiction. Hence, \(v_n\) is a cone point and \(\mathcal{A}(P_n,\mathbf{c}_0)\) is contractible. ◻
Note that Lemma 6 does not put any conditions on the number of grains on the latter half of the positions, these can be zero or non-zero and even non-binary, and analogously for Lemma 7. Next we consider a case where the dynamics separate into disjoint parts, see Example 3.
Lemma 8. Let \(\mathbf{c}_0\) be a binary configuration with \(|\mathbf{c}_0|>1\) and \(1\le k\le n\). If the non-zero positions of \(\mathbf{c}_0\) are exactly the equivalence class \[[i]_k=\{j\equiv i \,(mod\,\,k)\, | \, 1\le j \le n\},\;\text{ for some }1\le i\le n,\] then \(\mathcal{A}(P_n,\mathbf{c}_0)\) is homotopy equivalent to \(k\) disconnected points.
Proof. The firing sets are \(\sigma_t=\{v_j\, | \,j \equiv (i+t) \,(mod\,\,k)\text{ and }j\ge i+t\}\), the maximal firing sets being \(\sigma_0,\sigma_1,\ldots,\sigma_{k-1}\). If \(i \not\equiv j \,(mod\,\,k)\) then \(v_i\) and \(v_j\) will never fire at the same time step, thus these maximal simplices are all disjoint from each other. Therefore, \(\mathcal{A}(P_n,\mathbf{c}_0)\) consists of a sequence of \(k\) maximal and disconnected \(|\mathbf{c}_0|\)-simplices, i.e. \(k\) disconnected contractible components. ◻
Example 3. Consider the path \(P_7\) and \(\mathbf{c}_0=(1,0,0,1,0,0,1)\) shown below:
Figure 8: 
.
The non-zero positions are exactly the equivalence class \([1]_3=\{1,4,7\}\), thus \(\mathcal{A}(P_7,\mathbf{c}_0)\) is homotopy equivalent to \(3\) disconnected points, by Lemma 8. The firing sets of \(\mathcal{A}(P_7,\mathbf{c}_0)\) are \((v_1,v_4,v_7)\), \((v_2,v_5)\), \((v_3,v_6)\), \((v_4,v_7)\), \((v_5)\), \((v_6)\), and \((v_7)\), giving the avalanche complex:
Figure 9: 
.
Thus far we have not seen any results that yield avalanche homology in a degree greater than \(0\). Next we present a result where we can produce arbitrarily high \(\beta_1\), given a sufficiently long path.
Proposition 1. Let \(k\ge1\), \(n \geq k+3\) and \(\mathbf{c}_0=(1,1,\underbrace{0,\ldots,0}_{\times k},1,0,0,\ldots,0),\) then \[\mathcal{A}(P_n,\mathbf{c}_0) \simeq \bigvee_{n-k-2} S^1.\]
**Proof.* The firing sets generating \(\mathcal{A}(P_n,\mathbf{c}_0)\) are: \[\sigma_t=\begin{cases} (v_{t+1},v_{t+2},v_{t+k+3}),& ift < n-k-2,\\ (v_{t+1},v_{t+2}),& ifn-k-2\le t < n-1,\\ (v_{n}),& ift = n-1. \end{cases}\] All edges in the boundary of the 2-simplex \(\sigma_t\) are free edges, for all \(t<n-k-2\). Thus we can elementary collapse \(\sigma_t\) with its boundary edge \((v_{t+1},v_{t+k+3})\). Applying this collapse to every \(2\)-simplex \(\sigma_t\), for \(t<n-k-2\), leaves a 1-dimensional simplicial complex \(X\), which is homotopy equivalent to \(\mathcal{A}(P_n,\mathbf{c}_0)\).*
As \(X\) is 1-dimensional we know it is a wedge of \(1\)-spheres, the number of which is given by \(\beta_1(X)=edges-vertices+components\). We know \(X\) is connected, since it contains the edges \((v_i,v_{i+1})\), for all \(i<n\), thus we have \(1\) component and \(n\) vertices.
To compute the number of edges in \(X\), note that each \(2\)-simplex of \(\mathcal{A}(P_n,\mathbf{c}_0)\) contributes \(2\) edges to \(X\) (since one edge was removed in the collapse). The \(2\)-simplices are exactly \(\sigma_t\) for \(0\le t< n-k-2\), hence yielding \(2(n-k-2)\) edges. The edges \(\sigma_t\), for \(n-k-2\le t < n-1\), are also in \(X\) yielding another \(k+1\) edges. Thus the number of edges in \(X\) is \(2(n-k-2)+k+1=2n-k-3\). So \[\beta_1(X)=2n-k-3-n+1=n-k-2.\] ◻
Our next result allows us to create arbitrarily high degree homology, again given a sufficiently long path. For the proof of the next result we employ Discrete Morse Theory, for an introduction see [41], [42].
Proposition 1. If \(\mathbf{c}_0\) is a binary configuration on \(P_n\) with \(|\mathbf{c}_0|=n-1\), i.e. \(\mathbf{c}_0\) contains a single zero, then \[\mathcal{A}(P_{n},\mathbf{c}_0)\simeq\begin{cases} S^{\lfloor\frac{n}{2}\rfloor-1},& if\mathbf{c}_0(v_i)=0 \text{ for } i=\lfloor\frac{n}{2}\rfloor+1,\\ \ast,&otherwise. \end{cases}\]
**Proof.* The cases \(i\not=\lfloor\frac{n}{2}\rfloor+1\) follow by Lemmas 6 and 7.*
Consider \(i=\lfloor\frac{n}{2}\rfloor+1\). Let \(f:\mathcal{A}(P_n,\mathbf{c}_0)\rightarrow\mathbb{N}\) be given by \[f(\sigma)=\begin{cases} |\sigma|+1,& ifv_n\notin \sigma,\\ |\sigma|,& ifv_n\in \sigma. \end{cases}\] The definition of a discrete Morse function \(f\) [41] requires that for any simplex \(\sigma\) there is at most \(1\) coface (resp. face) \(\tau\) of \(\sigma\) with \(f(\tau)\le f(\sigma)\) (resp. \(f(\tau)\ge f(\sigma)\)). To see our function \(f\) satisfies this consider the sets: \[\begin{align} &\{\tau\, | \,\tau \subset \sigma \text{ and } f(\tau)\ge f(\sigma)\}= \begin{cases} \{\sigma\setminus\{v_n\}\},& if v_n\in \sigma \text{ and } \sigma\setminus\{v_n\}\in\mathcal{A}(P_n,\mathbf{c}_0),\\ \emptyset,& otherwise, \end{cases}\\ &\{\tau\, | \,\sigma \subset \tau \text{ and } f(\tau)\le f(\sigma)\}= \begin{cases} \{\sigma\cup\{v_n\}\},& if v_n\not\in \sigma\text{ and }\sigma\cup\{v_n\}\in\mathcal{A}(P_n,\mathbf{c}_0),\\ \emptyset,& otherwise.\\ \end{cases} \end{align}\] Thus we see in both cases that there is at most one coface with a smaller value and at most one face with a larger value, so \(f\) is a discrete Morse function. We can think of this function as pairing a simplex with the simplex obtained by adding or removing \(v_n\).
The critical cells of this discrete Morse function are \[\alpha=\left\{\left\lfloor\frac{n}{2}\right\rfloor+1,\ldots,n-1\right\}\,\,\,\,\,\,\text{ and }\,\,\,\,\,\,\beta=\{v_n\},\] since \(\beta\setminus\{v_n\}=\emptyset\), which is not in \(\mathcal{A}(P_n,\mathbf{c}_0)\), and \(\alpha\cup\{v_n\}\) is also not in \(\mathcal{A}(P_n,\mathbf{c}_0)\). To see this for \(\alpha\), note that \(\alpha\) is the simplex given by the firing set at time \({t=n-\lfloor\frac{n}{2}\rfloor+1}\), when the \(0\) in \(\mathbf{c}_0\) has shifted along so that \(\mathbf{c}_t(v_n)=0\), thus adding \(v_n\) to \(\alpha\) does not give a valid firing set. Hence, we have a critical \(0\)-cell and \({(\lfloor\frac{n}{2}\rfloor-1)}\)-cell, and it follows by [41] that \(\mathcal{A}(P_n,\mathbf{c}_0)\) is homotopy equivalent to \(S^{\lfloor\frac{n}{2}\rfloor-1}\). ◻
We conjecture that Proposition 1 gives the binary configuration with the highest degree homology.
Conjecture 1. If \(\mathbf{c}_0\) is a binary configuration, then for \(\mathcal{A}(P_n,\mathbf{c}_0)\) we have \(\beta_i=0\) for all \(i>\lfloor\frac{n}{2}\rfloor-1\).
We have computationally verified Conjecture 1 for all binary configurations on all paths \(P_n\) for \(n<20\). However, the conjecture does not hold if we relax the binary condition on the initial configuration, a counterexample is \(\mathcal{A}(P_7,(5,0,1,1,1,1,1))\), which has \(\beta_4=1.\)
3.2 Cycle digraphs↩︎
Next we consider the directed cycles \(C_n\) on \(n\) vertices and no sinks, see Example 4. As \(C_n\) has no sink and every vertex has out-degree \(1\), if \(|\mathbf{c}_0|>0\) then the sandpile will never stabilise. However, it will always reach some recurrent orbit, where no new firing sets occur, and hence \(\mathcal{A}(C_n,\mathbf{c}_0)\) is finite. We index the vertices \(v_1,\ldots,v_n\) of \(C_n\) such that the in- and out-neighbours of \(v_i\) are \(v_{i-1\,(mod\, n)}\) and \(v_{i+1\,(mod\, n)}\), respectively, and for notational simplicity we drop the \((mod\,n)\) henceforth.
Example 4. Consider the cycle \(C_4\) with \(\mathbf{c}_0\) as shown below:
Figure 10: 
.
The firing sets \((v_1,v_2,v_3)\), \((v_2,v_3,v_4)\), \((v_3,v_4,v_1)\) and \((v_4,v_1,v_2)\) generate the complex \(\mathcal{A}(C_4,\mathbf{c}_0)\). Hence it is homotopy equivalent to \(S^2\).
We begin with two results that allow us to significantly reduce the configuration space that we need to consider. In Example 1 we showed that in general having more grains of sand than vertices does not imply the avalanche complex is trivial. However, for cycles we do get contractible complexes in this case.
Proposition 1. For any cycle \(C_n\), if \(|\mathbf{c}_0| \geq n\), then \(V \in \text{Sp}(G,\mathbf{c}_0)\), so \(\mathcal{A}(C_n,\mathbf{c}_0)\) is contractible.
Proof. Consider time \(t=n\). If \(\sigma_n=V\) the result follows from Lemma 1. If \(\sigma_n\not=V\), then at least one vertex \(v_i\) is stable. Thus \(v_{i-1}\) was stable at time \(n-1\), otherwise it would have fired and added a grain of sand to \(v_i\). Continuing inductively we see that every vertex must have been stable for some time \(t\).
Once a vertex in \(C_n\) has been stable it can only have \(0\) or \(1\) grains of sand at any subsequent time step, since it will always lose a grain if non-zero and never gain more than \(1\) grain from a single firing set, as it only has one in-neighbour. Thus \(|\mathbf{c}_{n+1}|\le n\), since by time \(n+1\) every vertex has been stable, thus has at most \(1\) grain of sand. So either \(|\mathbf{c}_{n+1}|=n\) and \(\sigma_{n+1}=V\), resulting in contractible \(\mathcal{A}(C_n,\mathbf{c}_0)\), or \(|\mathbf{c}_0|=|\mathbf{c}_{n+1}|<n\) yielding a contradiction. ◻
Our next result allows us to limit our consideration of the configuration space to binary configurations, as all other configurations are equivalent to some binary configuration, with respect to avalanche homology.
Theorem 1. If \(\mathbf{c}_0\) is a non-binary configuration, then there is a binary configuration \(\widehat{\mathbf{c}}_0\), such that \(\mathcal{A}(C_{n},\mathbf{c}_0)=\mathcal{A}(C_{n},\widehat{\mathbf{c}}_0)\).
Proof. If \(|\mathbf{c}_0|\ge n\), then \(\mathcal{A}(C_{n},\mathbf{c}_0)\) is the \(n\)-simplex by the proof of Proposition 1, thus equal to \(\mathcal{A}(C_{n},\widehat{\mathbf{c}}_0)\), where \(\widehat{\mathbf{c}}_0\) is the vector of all \(1\)’s.
Consider \(|\mathbf{c}_0|<n\). First note that by the argument in the proof of Proposition 1, there is some \(k>0\) such that \(\mathbf{c}_k\) is binary. Next note that \(\sigma_t\subseteq\sigma_{t+n}\), for all \(t\), since if \(v_i\) fires at time \(t\) it sends a grain to \(v_{i+1}\) which fires at time \(t+1\), and continuing inductively, at time \(t+n\) vertex \(v_{i+n(mod\,n)}=v_i\) fires. Thus every vertex which fires at time \(t\) also fires at time \(t+n\). This implies \(\mathcal{A}(C_n,\mathbf{c}_0)=\mathcal{A}(C_n,\mathbf{c}_t)\) for all \(t\), thus the result follows by setting \(\widehat{\mathbf{c}}_0=\mathbf{c}_k\). ◻
We call a simplicial complex pure if all maximal simplices are of the same dimension. It is not always true that the avalanche complex is pure, see Figure 4 and Example 2. However, for cycles the avalanche complex is always pure.
Proposition 1. For every initial configuration \(\mathbf{c}_0\), the complex \(\mathcal{A}(C_n,\mathbf{c}_0)\) is pure of dimension \(\min(|\mathbf{c}_0|,n)-1\).
**Proof.* If \(|\mathbf{c}_0|\ge n\), then \(\mathcal{A}(C_n,\mathbf{c}_0)\) is an \((n-1)\)-simplex, thus pure. If \(|\mathbf{c}_0|<n\), then \(\mathcal{A}(C_{n},\mathbf{c}_0)=\mathcal{A}(C_{n},\widehat{\mathbf{c}}_0)\), for some binary configuration \(\widehat{\mathbf{c}}_0\), by Theorem 1. Every maximal simplex of \(\mathcal{A}(C_{n},\widehat{\mathbf{c}}_0)\) has dimension \(|\mathbf{c}_0|-1\). ◻*
The following result is the cycle equivalent of Lemma 8.
Lemma 9. Let \(\mathbf{c}_0\) be a binary configuration with \(|\mathbf{c}_0|>1\) and \(1\le k\le n\). If the non-zero positions of \(\mathbf{c}_0\) are exactly the equivalence class \[[i]_k=\{j\equiv i \,(mod\,\,k)\, | \, 1\le j \le n\},\;\text{ for some }1\le i\le n,\] then \(\mathcal{A}(C_n,\mathbf{c}_0)\) is homotopy equivalent to \(k\) disconnected points.
Proof. If \(i \not\equiv j \,(mod\,\,k)\) then \(v_i\) and \(v_j\) will never fire at the same time step. For a given time step \(t\), the vertices \(\{v_j\, | \,j \equiv (i+t) \,(mod\,\,k)\}\) will form a single simplex, thus \(\mathcal{A}(P_n,\mathbf{c}_0)\) consists of \(k\) disconnected contractible components. ◻
If we instead consider the positions of the zeros, then we get the following conjecture which is analogous to Lemma 9. Conjecture 1 has been computationally verified for all such configurations on all \(C_n\) for \(n<29\).
Conjecture 1. Let \(\mathbf{c}_0\) be a binary configuration with \(|\mathbf{c}_0|>1\) and \(1\le k\le n\). If the zero positions of \(\mathbf{c}_0\) are exactly the equivalence class \[[i]_k=\{j\equiv i \,(mod\,\,k)\, | \, 1\le j \le n\},\;\text{ for some }1\le i\le n,\] then \(\mathcal{A}(C_n,\mathbf{c}_0)\simeq S^{k-2}\).
We have evaluated the cases of \(C_n\) where \(|\mathbf{c}_0|\ge n\), next we consider small values of \(|\mathbf{c}_0|\), in particular when \(|\mathbf{c}_0|=2\).
Proposition 1. Consider \(|\mathbf{c}_0|=2\) with \[\mathbf{c}_0=(\dots,0,1,\underbrace{0,\ldots,0}_{\times k-1},1,0,\ldots),\] i.e. there are \(k-1\) zeros between the ones, then \[\mathcal{A}(C_{n},\mathbf{c}_0)\simeq\bigsqcup_{\gcd(n,k)}\begin{cases} \ast,& ifk=\frac{n}{2},\\ S^1,& if k\not=\frac{n}{2}. \end{cases}\]
**Proof.* The connected components of \(\mathcal{A}(C_{n},\mathbf{c}_0)\) are the sets \(\{v_{i},v_{i+k},v_{i+2k},\ldots\}\), for all \(1\le i\le n\). These are in bijection with the cosets of the subgroup generated by \(k\) of the additive group \(\mathbb{Z}_n\). By Lagrange’s theorem, the number of cosets is equal to the order of \(\mathbb{Z}_n\), which is \(n\), divided by the order of the subgroup generated by \(k\), which is \(\frac{n}{\gcd(n,k)}\) [43]. Thus the number of cosets, and also the number of connected components, is \(\frac{n}{\frac{n}{\gcd(n,k)}}=\gcd(n,k)\).*
Each component is a sequence of edges \(\{v_i,v_{i+k (\text{mod}\,n)}\}\), thus if the component contains more than \(2\) vertices, so \(k\not=\frac{n}{2}\), each component is a \(1\)-sphere. If \(k=\frac{n}{2}\), then each component is a single edge, thus contractible. ◻
Corollary 1. If \(n\) is prime and \(|\mathbf{c}_0|=2\), then \(\mathcal{A}(C_{n},\mathbf{c}_0)\simeq S^1\).
If we consider configurations for consecutive \(1\)’s on the cycle, then we uncover an interesting connection to nerve complexes of circular arcs, studied in [22]. The nerve complex \(\mathcal{N}(n,k)\) is defined as the simplicial complex with vertex set \(\{0,\ldots, n-1\}\), and its set of maximal simplices is \(\{[i, i+k]_n\,|\,i = 0,\ldots, n - 1\}\), where \([i, i+k]_n\) is the image of the set \(\{i,i+1,\ldots, i+k\}\) under the modulo \(n\) operation. Thus this is exactly the avalanche complex \(\mathcal{A}(C_n,\mathbf{c}_0^{k,n})\), where \(\mathbf{c}_0^{k,n}=(\underbrace{1,\ldots,1}_{\times k},\underbrace{0,\ldots,0}_{\times (n-k)}).\)
In [22] a full classification of the homotopy types of \(\mathcal{N}(n,k)\) is given, thus we immediately obtain the following result for the avalanche complex. A pictorial representation of the homology resulting from Theorem 2 can be seen in Figure 11.
Theorem 2. If \(\mathbf{c}_0^{k,n}=(\underbrace{1,\ldots,1}_{\times k},\underbrace{0,\ldots,0}_{\times (n-k)}),\) then \[\mathcal{A}(C_n,\mathbf{c}_0^{k,n})\simeq \begin{cases} \bigvee_{n-k}S^{2\ell},& if k-1=\frac{n\ell}{\ell+1},\\ S^{2\ell+1},& if \frac{n\ell}{\ell+1}<k-1<\frac{n(\ell+1)}{\ell+2} \end{cases},\] where \(\ell\in\mathbb{N}\) with \(0\le \ell\le \frac{n-1}{2}\).
As a direct corollary of Theorem 2 we get the case when the binary configuration has a single \(0\), which by Proposition 1 is equivalent to any configuration with \(|\mathbf{c}_0|=n-1\).
Corollary 2. Let \(n \geq 3\) and \(|\mathbf{c}_0|=n-1\), then \(\mathcal{A}(C_n,\mathbf{c}_0)\simeq S^{n-2}\).
Our final result on \(C_n\) is the cycle version of Proposition 1, where we have \(|\mathbf{c}_0|=3\) with at least two of the \(1\)’s consecutive. The arguments in the proof can exemplified via Figure 12.
Proposition 1. If \(n > 4\) and \(\mathbf{c}_0=(1,1,\underbrace{0,\ldots,0}_{\times k},1,0,0,\ldots,0),\) then \[\mathcal{A}(C_{n},\mathbf{c}_0)\simeq\begin{cases} S^1,& if k=0\text{ or }k=n-3,\\ S^1,& if n is odd and k=\frac{n-3}{2},\\ \bigvee_{\frac{n}{2}+1}S^1,& if n is even and k\in\{\frac{n}{2}-2,\frac{n}{2}-1\},\\ \bigvee_{n+1}S^1,& otherwise. \\ \end{cases}\]
**Proof.* If \(k=0\) or \(k=n-3\) the result follows from Theorem 2.*
In all other cases, we apply an analogous argument to the proof of Proposition 1. The maximal simplices of \(\mathcal{A}(C_{n},\mathbf{c}_0)\) are \(\{(v_{i},v_{i+1},v_{i+k+2})\, | \, 1\le i\le n\}\). The \(1\)-simplex \((v_i,v_{i+1})\) only appears in a single 2-simplex, i.e.is a free face. Thus we can elementary collapse each 2-simplex \((v_{i},v_{i+1},v_{i+k+2})\) with \((v_i,v_{i+1})\). If we collapse every 2-simplex we are left with a 1-dimensional connected simplicial complex \(X\), thus \(\beta_1=edges-vertices+components\). The edges of \(X\) are exactly \(A\cup B\), where \[A=\{(v_i,v_{i+k+2})\, | \,1\le i\le n\}\,\,\,\,\,\text{ and }\,\,\,\,\,B=\{(v_{i+1},v_{i+k+2})\, | \,1\le i\le n\}.\] We have \(n\) vertices, and \(1\) component, thus by inclusion-exclusion \[\beta_1=|A|+|B|-|A\cap B|-n+1.\]
If \(n\) is odd and \(k=\frac{n-3}{2}\), then the number of trailing zeros in \(\mathbf{c}_0\) is \(n-k-3=\frac{n-3}{2}\), thus the distance between vertices \(v_{i+1},v_{i+k+2}\) and between vertices \(v_{i+k+2},v_i\) is the same, so \(A=B\) and \(|A|=n\) thus \(\beta_1=n+n-n-n+1=1\)
Let \(n\) be even and \(k=\frac{n}{2}-1\). Since \(v_{i+1}\) and \(v_{i+k+2}=v_{i+\frac{n}{2}}\) are antipodal, the firing sets \((v_{i+1},v_{i+k+2})\) are exactly the \(\frac{n}{2}\) antipodal pairs, so \(|B|=\frac{n}{2}\). By the same argument with respect to non-antipodality of \((v_i,v_{i+k+2})\), \(|A|=n\) and \(A\cap B=\emptyset\), thus \(\beta_1=n+\frac{n}{2}-n+1=\frac{n}{2}+1\). The argument is analogous for \(k=\frac{n}{2}-2\).
Otherwise, \(|A|=|B|=n\) and \(A\cap B=\emptyset\), so \(\beta_1=n+1\). ◻
For a digraph \(G\) on \(n\) vertices, the avalanche homology is “parametrised" by \(\mathbf{c}_0\), as each initial configuration is simply a point in \(\mathbb{N}^n\). Thus we can ask how the space \(\mathbb{N}^n\) decomposes into different domains based on the topology of \(\mathcal{A}(G,\mathbf{c}_0)\). In particular, for the cycles we pose the following question:
Question 1. How does the homotopy types or homology of \(\mathcal{A}(C_n,\mathbf{c}_0)\) decompose \(\mathbb{N}^n\)?
A similar question can be asked for the paths \(P_n\), and for any other class of digraphs. For example, for \(C_4\) the results of this section give us:
if \(|\mathbf{c}_0|>3\), then \(\mathcal{A}(C_4,\mathbf{c}_0)\simeq*\) (Proposition 1);
if \(|\mathbf{c}_0|=3\), then \(\mathcal{A}(C_4,\mathbf{c}_0)\simeq S_2\) (Corollary 2);
if \(|\mathbf{c}_0|=2\) with consecutive non-zero positions, then \(\mathcal{A}(C_4,\mathbf{c}_0)\simeq S_1\)
(Proposition 1);if \(|\mathbf{c}_0|=2\) with non-consecutive non-zero positions, then \(\mathcal{A}(C_4,\mathbf{c}_0)\simeq \bigsqcup_2 \ast\)
(Proposition 1);if \(|\mathbf{c}_0|=1\), then \(\mathcal{A}(C_4,\mathbf{c}_0)\simeq \bigsqcup_4 \ast\) (Lemma 3);
if \(|\mathbf{c}_0|=0\), then \(\mathcal{A}(C_4,\mathbf{c}_0)=\emptyset\) (Lemma 3).
Thus we obtain a partition of \(\mathbb{N}^4\). The configuration \((1,1,1,1)\) is contractible, and we can visualise the remaining binary configurations by assuming, without loss of generality due to rotational symmetry, that \(v_4\) has zero grains of sand; the homotopy types of \(\mathcal{A}(C_4,\mathbf{c}_0)\) are shown in Figure 13 (a) for each \(\mathbf{c}_0=(v_1,v_2,v_3,0)\). The rotational symmetry of cycles gives certain symmetry to Question 1 and the following result is immediate.
Lemma 10. Let \(\pi(\mathbf{c}_0)\) be a cyclic permutation of an initial configuration \(\mathbf{c}_0\). Then \(\mathcal{A}(C_n,\mathbf{c}_0) = \mathcal{A}(C_n,\pi(\mathbf{c}_0)).\)
As the dimensionality increases, so does exponentially the number of different initial configurations. It would be interesting to know whether the homotopy types or homologies of \(\mathcal{A}(G,\mathbf{c}_0)\) for some digraph \(G\) are different between any neighbouring configurations, or whether there might exist connected domains yielding the same topology. We illustrate this question in Figure 13 (b) for the cycle \(C_n\); the figure shows the conceptual idea by collapsing \(\mathbb{N}^n\) on the plane. By Proposition 1 we know that for \(\mathbf{c}_0 = (1,1,\dots,1)\) and for any configuration with \(|\mathbf{c}_0| \geq n\) the complex \(\mathcal{A}(G,\mathbf{c}_0)\) is contractible, as depicted by the blue region. By Corollary 2 all projections of \(\mathbf{c}_0\) to coordinate axes yield \(S^{n-2}\). We have covered some cases in this section for the white region, but a full answer to Question 1 is open.
A natural question to ask with graph homology theories is how they behave under certain graph operations. Whilst we leave this as an open question in general, our next result demonstrates that the question maybe be tractable to some degree; see also Figure 14.
Proposition 1. Consider \(C_n\) and initial configuration \(\mathbf{c}_0=(c_1,c_2,\ldots,c_n)\). Let \(C_n^{\vee}\) be the wedge sum of \(C_n\) with itself, i.e.two copies of \(C_n\) glued together at \(v_1\) of each graph. Let \[\mathbf{c}_0^\vee=(2c_1,c_2,\ldots,c_n,c_2,c_3,\ldots,c_n),\] i.e.the same number of grains on each cycle as before and double on the glued vertex \(v_1\). Then \[\mathcal{A}(C_n^\vee,\mathbf{c}_0^\vee) \simeq \mathcal{A}(C_n,\mathbf{c}_0).\]
**Proof.* Let \(v_1,v_2,\ldots,v_n\) be the vertices of one cycle and \(v_1,w_2,\ldots,w_n\) the vertices of the other. Every maximal simplex \(M_i\) can be split into \(M_i=V_i\cup W_i\), i.e.the vertices of one cycle and the vertices of the other. As the configurations on the cycles are symmetric, the only maximal simplex that contains \(W_i\) is \(M_i\), thus we can collapse \(M_i\) with \(W_i\). Doing so for all maximal simplices makes the \(V_i\) the maximal simplices, which are exactly the maximal simplices of \(\mathcal{A}(C_n,\mathbf{c}_0)\), thus the two complexes are homotopy equivalent. ◻*
If we start with two cycles with the same configuration but located asymmetrically around the cycles, our preliminary observation is that the firing sets initially behave rather irregularly, but will eventually synchronise with symmetric firing sets rotating along the cycles. We conjecture that wedges of more than two cycles, and not necessarily with equal number of vertices, with asymmetric initial configurations might produce a rich variety of homotopy types.
3.3 Comparison to other (di)graph homologies↩︎
Recently, the burning homology of finite undirected graphs was introduced [23]. Similar in spirit to our work, graph burning is a discrete time process on a graph \(G\), where each vertex is either burned or unburned. At every time step \(t\) an unburned vertex is chosen as the fire source and burned. At time \(t+1\) the unburned neighbours of burned vertices are burned. Once a vertex is burned it stays in this state until the end of the process, and once all vertices are in the burned state the process ends.
In [23] the burning process is defined in terms of an ordered sequence of vertices \(S_G = (v_1,v_2,\dots,v_n)\) representing a sequence of fire sources. Each such sequence, that gives a valid burning process on \(G\), hence defines a subset of vertices. These sets are then taken as the maximal simplices generating a simplicial complex, the burning configuration space of \(G\), and the burning homology is the homology of this complex.
Table ¿tbl:tab:burning? displays the non-trivial integral burning homologies for paths \(P_n\) and the avalanche homology of undirected paths. We can see that avalanche homology exhibits much higher homological expressivity.
Another simplicial homology arises from the directed flag complex of a digraph \(G\) (see for example [25], [36]). An \(n\)-simplex is given by an ordered sequence of vertices \((v_0,v_1,\dots,v_n)\) such that any ordered pair \((v_i,v_j)\), \(i < j\), is a directed edge of \(G\), hence the simplices are directed cliques. Any path \(P_n\) as a directed flag complex is just a sequence of 1-simplices, hence contractible, while any cycle \(C_n\) is homotopy equivalent to \(S^1\). We have shown in Section 3 that in contrast both paths and cycles can have a wide range of avalanche homologies.
| \(P_1\) | \(P_2\) | \(P_3\) | \(P_4\) | \(P_5\) | \(P_6\) | |
|---|---|---|---|---|---|---|
| \(H_0\) | \(\Z\) | \(\Z^2\) | \(\Z^2\) | \(\Z\) | \(\Z\) | \(\Z\) |
| \(H_1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(\Z\) | \(0\) |
| \(G\) | \(\bc_0\) | \(\beta_0\) | \(\beta_1\) | \(\beta_2\) | \(\beta_3\) | \(\beta_4\) |
|---|---|---|---|---|---|---|
| \(P_6\) | \((1, 7, 0, 0, 2, 0)\) | \(1\) | \(1\) | \(1\) | \(0\) | \(0\) |
| \(P_6\) | \((4, 5, 0, 2, 3, 0)\) | \(1\) | \(0\) | \(0\) | \(1\) | \(0\) |
| \(P_6\) | \((7, 1, 2, 2, 2, 1)\) | \(1\) | \(0\) | \(0\) | \(0\) | \(1\) |
4 Persistent avalanche homology↩︎
At each time step \(t\) of the dynamics \(\text{Sp}(G,\mathbf{c}_0)\) we add at most one simplex to the complex \(\mathcal{A}(G,\mathbf{c}_0)\), coming from the firing set \(\sigma_t\). This added simplex may or may not have an effect on the homology of the evolving avalanche complex. The dynamics naturally induces a filtration by subcomplexes
\[\label{eq:filtration} \mathcal{A}_0(G,\mathbf{c}_0) \hookrightarrow \mathcal{A}_1(G,\mathbf{c}_0) \hookrightarrow \mathcal{A}_2(G,\mathbf{c}_0) \hookrightarrow \cdots,\tag{2}\] where for each time step \(i\) the avalanche complex \(\mathcal{A}_{i}(G,\mathbf{c}_0)\) is generated by the firing sets in \(\{\sigma_t\}_{t \leq i}\).
The avalanche homology in degree \(k\) (over a coefficient field \(K\)) is the colimit of the associated diagram of homology vector spaces \[\label{eq:av95pers95module} H_k(\mathcal{A}_0(G,\mathbf{c}_0)) \rightarrow H_k(\mathcal{A}_1(G,\mathbf{c}_0)) \rightarrow H_k(\mathcal{A}_2(G,\mathbf{c}_0)) \rightarrow\cdots.\tag{3}\] However, from the point of view of the dynamics and the homological changes incrementally induced in time steps, we see it as more interesting to view 3 as the persistence module \(\mathcal{P}(G,\mathbf{c}_0)\) for persistent avalanche homology of \(G\), and study the more refined homological information it contains.
Indeed, Figure 15 demonstrates the persistent avalanche homology for a complex homotopy equivalent to \(S^1\); the associated persistence barcode reveals the onset of homological changes. Moreover, two initial configurations yielding the same avalanche homology may have differing persistent avalanche homology, see the persistence diagrams in Figure 16.
Remark 1. Given a digraph \(G\) and an initial configuration \(\mathbf{c}_0\), consider the number of maximal simplices \(m_i\) at filtration value \(i\), i.e.of the complex \(\mathcal{A}_i(G,\mathbf{c}_0)\) in 2 . The sequence \(M=(m_0,m_1,m_2,\ldots,m_k)\) is a parking function, i.e.\(m_i\le i\) for all \(i\), since we add at most \(1\) new maximal simplex at each step. A parking function is any sequence which when rearranged into increasing order satisfies this property; they have many interesting links to sandpiles, see [14].
Persistence theory encompasses many metrics between persistence modules and persistence diagrams/barcodes. Their application to the persistent avalanche homology gives a useful tool to measure homological distances between dynamics on different digraphs, see Figure 16 for an illustration. Moreover, there is an isomorphism \(\mathcal{P}(G,\mathbf{g}_0) \simeq \mathcal{P}(H,\mathbf{h}_0)\) if and only if the bottleneck distance between the associated barcodes is zero [44]. Hence the distance comparisons detect deviations from isomorphism, and to re-iterate, these deviations can be linked to at most one firing set at each filtration step. We see exploring the interplay between persistent homology and avalanche dynamics as a fruitful avenue, which we leave for further study.
A natural question also to ask is whether there exists any stability theorem for persistent avalanche homology. While we do not attempt it in this paper, we illustrate the difficulty of such a result due to the discrete nature of the constructions. The smallest change we can make to an initial configuration is a whole grain of sand, and the smallest change to a digraph is the removal of an edge or a vertex. By the results of Section 3, we know that a single grain of sand can have a large effect on the topology. For example, when \(|\mathbf{c}_0|=n-1\) we know \(\mathcal{A}(C_n,\mathbf{c}_0)\simeq S^{n-2}\) (by Proposition 2), yet adding a single grain of sand to the initial configuration results in a contractible complex by Proposition 1. Figure 16 shows that adding a single grain of sand causes a significant change to the persistence diagram. A tentative stability theorem would take the form \(d_?((G,\mathbf{g}_0),(H,\mathbf{h}_0)) \leq d_I(\mathcal{P}(G,\mathbf{g}_0), \mathcal{P}(H,\mathbf{h}_0))\), where \(d_I\) denotes the interleaving distance between persistence modules, or equivalently the bottleneck distance between the persistence diagrams/barcodes by the isometry theorem [45]. An important, and potentially difficult, consideration is identifying an appropriate metric \(d_?\) between digraphs and initial configurations.
5 Discussion and open questions↩︎
In this paper we have introduced the theory of avalanche homology and glimpsed the complex topology and combinatorics related to it. Yet many open questions and avenues of investigation remain.
We proved topological results for paths and cycles, for a selection of initial configurations. We have seen some interesting combinatorics in obtaining the homotopy types and avalanche homologies of these graphs, and we believe similar technologies remain valid in extending results to other initial configurations and to other classes of graphs, such as tournaments. In particular, as the avalanche complex arises from the sandpile dynamics on a digraph, one needs to keep explicit track of the firing sets generating simplices and the combinatorics this entails.
We have seen that, even with simple digraphs, the avalanche homology can produce a wide range of Betti numbers. Moreover, all of our results and examples so far have been wedges of spheres, perhaps not surprising given the prevalence of wedges of spheres in combinatorial topology [41]. We pose the following question:
Question 2. Given any wedge of spheres \(X\), does there exist a weakly connected digraph \(G\) and an initial configuration \(\mathbf{c}_0\) such that \(\mathcal{A}(G,\mathbf{c}_0)\simeq X\). Thus, can every combination of Betti numbers be obtained as the avalanche homology of some digraph.
We have computationally verified that different combinations of Betti numbers can be obtained as wedges of spheres, see for example Table ¿tbl:tab:burning? (b). This prompts the natural question whether we can create avalanche complexes which are not wedges of spheres. Furthermore, it has been observed that torsion can occur in some graph homology theories [46]–[48], thus motivating the related question whether we can find torsion in avalanche complexes.
We have focused on directed graphs. The avalanche homology of undirected graphs requires a separate study. The undirected case seems more unwieldy to some degree, since the firing sets can “oscillate" due to the lack of directionality, but we believe results can be obtained on the homotopy types of some simple classes of graphs, similar to those in Section 3. For example, on the complete graph with a sink where the initial configuration is \(\mathbf{c}_0 = [n]\), or any permutation of it, \(\mathcal{A}(K_n,\mathbf{c}_0)=\bigsqcup_{n}\ast\), which follows since every vertex will fire exactly once.
From the point of view of topological data analysis of real network data, further work on persistent avalanche homology of Section 4 is crucial. We have seen in Section 2.2 that the required computational resources can be drastically reduced by using the nerve complex. Moreover, an advantage of avalanche homology is that we are not limited by the size of the graph, but by the size of the dynamics. By carefully selecting the initial configuration we can compute the avalanche homology on very large graphs, for which we are unable to compute other homology theories, such as that of the directed flag complex.
Finally, a topic of much interest in the study of sandpile dynamics is the distribution of avalanche sizes, which generally follows a power law, see [14] and [1]. This distribution is linked to the distribution of simplices in avalanche complexes, thus this distribution may also follow a power law.
Code availability↩︎
Code to compute the avalanche homology is available at https://github.com/JasonPSmith/AvalancheHomology, including a tutorial notebook and a notebook containing all computations used within this article. The code utilises GUDHI [49] for homology computations.