Séminaire Lotharingien de Combinatoire 77 (2018), Article B77g

DECOMPOSING RECURRENT STATES OF THE ABELIAN SANDPILE MODEL

MARK DUKES AND THOMAS SELIG

Abstract. The recurrent states of the Abelian sandpile model (ASM) are those states that appear infinitely often. For this reason they occupy a central position in ASM research. The set of stable configurations on a graph form a Markov chain whereby a transition from a configuration c to another c′ occurs if the addition of a grain to c and the resulting sequence of topplings (if any) yields the state c′. Checking whether a stable configuration is recurrent is a far from trivial task and requires Dhar’s criterion, an algorithmic process, to be used. We present several new results for classifying recurrent states of the Abelian sandpile model on graphs that may be decomposed in a variety of ways. These results represent an enormous computational saving with respect to Dhar’s criterion. Furthermore, they allow us to classify, for certain families of graphs, recurrent states in terms of the recurrent states of its components. We use these decompositions to give recurrence relations for the generating functions of the level statistic on the recurrent configurations. We also interpret our results with respect to the sandpile group.

1. Introduction

The Abelian sandpile model (ASM) has attracted a considerable amount of attention down through the years, and remains a constant source of new and interesting research topics. Perhaps the most recent of these is its relation to the discrete Riemann–Roch formula for graphs [3]. One fundamental aspect of ASM research concerns the classification of the recurrent states of the model; those states that appear infinitely often in the long-time running of the model.

In order to calculate this important set of recurrent states of the ASM on a given graph one appeals to Dhar’s criterion [12], an algorithmic procedure for checking when a stable configuration on a graph is recurrent. Dhar’s criterion is a global one in the sense that it induces a wave of topplings to occur throughout a graph and it is indifferent to some sort of regular structure that may be inherent within the graph. Consequently, the computations required to go through all possible stable configurations on a graph and check whether the criterion holds for each can take a significant amount of time.

In this paper we present several new results classifying recurrent states of the ASM on graphs which may be decomposed in a variety of ways. The computational benefit of our

Key words and phrases. Abelian sandpile model, recurrent states, graph decomposition, level polynomial, Tutte polynomial.

Supported by the EPSRC grant EP/M015874/1: New combinatorial perspectives on the Abelian sandpile model.

results to the classification problem can be immense. The level statistic of a sandpile configuration, a quantity that is equal (up to an additive constant) to the sum of its heights, is studied with respect to these decompositions.

Alongside our classification results we give the generating functions of the level statistic (to be defined) on these graph decompositions, which we believe to represent a significant contribution in terms of computational savings. We then show the effect of these graph decompositions on the sandpile group, which is the set of recurrent states equipped with an Abelian addition operation. These results also have an added benefit in that they provide a combinatorial setting in which to interpret set products of configurations that are almost recurrent states (up to some additive vector). The studied decompositions in components of the graph are also lifted to product decompositions of the sandpile group of the whole graph into the sandpile group of the components. We almost interpret these decompositions in terms of set products of configurations (see Section 5 for details).

The motivation behind the current paper is twofold. First, we are interested in generalizing results of the first author for recurrent configurations of the sandpile model on the complete bipartite graph, and understanding how altering the graph (e.g. a doubling of edges) changes the combinatorial interpretation of the recurrent states as parallelogram polyominoes [13, 1, 2]. Second, we are interested in understanding the sandpile model on graphs that have some notion of a ‘decomposition point’, a vertex or edge that might afford product-style theorems to sets of recurrent states. The purpose behind this second goal is to attribute a meaning to products of combinatorial objects that represent recurrent states. Being able to explain this has the advantage that constructions on these objects (e.g. restricted lattice paths in the case of [13]) and statistics upon them can be interpreted in terms of a toppling analysis on an appropriate graph. Several other authors have considered decompositions on graphs in relation to the sandpile group and these include Lorenzini [17], Jacobson et al. [15], Berget et al. [4], and Levine [16]. In particular, Lorenzini [17] observed our Theorem 5.2 in the remark following the proof of his Proposition 1.

We now introduce the Abelian sandpile model on a graph and review some notation that is necessary in order for us to present our results. Let G = (V, E) be a finite, connected, loop-free, undirected multigraph with vertex set V = {v_{0}, …, v_{n}}. Let d_{i} = d_{i}^{G} = deg(v_{i}) be the degree of the vertex v_{i} in G. We will consider the sandpile model on the graph G in which a distinguished vertex, v_{0} say, acts as a sink. We will indicate which vertex of a graph is being treated as a sink by writing it as a pair, e.g. (G, v_{0}).

Let ℤ_{+} be the set of non-negative integers. A configuration on (G, v_{0}) is a vector c = (c_{1}, …, c_{n}) ∈ ℤ_{+}^{n} that assigns the number c_{i} to vertex v_{i}. We think of c_{i} as representing the number of grains of sand at the vertex v_{i}. Denote by Config_{v_{0}}(G) the set of all configurations on (G, v_{0}). Let α_{i} ∈ ℤ_{+}^{n} be the vector with 1 in the i-th position and 0 elsewhere. Throughout this paper, we will find it useful to refer to sets of vertices in V and will use the following notation: given i, j ∈ ℤ_{+} with i ≤ j, let V_{[i,j]} = {v_{i}, v_{i+1}, …, v_{j}}. Also, for some subset W ⊆ V, we let G[W] be the subgraph of G with vertex set W and edge set the edges of G with both endpoints in W.

We will say that a vertex v_{i} in a configuration c = (c_{1}, …, c_{n}) ∈ Config_{v_{0}}(G) is stable if c_{i} < d_{i}. Otherwise it is called unstable. A configuration is called stable if all its non-sink vertices are stable, and we denote Stable_{v_{0}} (G) the set of all stable configurations on (G, v_{0}).

Unstable vertices may topple. We define the toppling operator T_{i} corresponding to the toppling of an unstable vertex v_{i} ∈ V in a configuration c ∈ Config_{v_{0}}(G) by:

T_{i}(c) := c − d_{i}α_{i} + ∑_{j:{v_{i},v_{j}}∈E} α_{j},  (1)

where the sum is over all vertices adjacent to v_{i}, counted with multiplicity.

Performing this toppling may cause other vertices to become unstable, and we may topple these also. One can show that starting from some unstable configuration c and toppling successively unstable vertices, we eventually reach a stable configuration c′ (think of the sink as absorbing grains). Moreover, this configuration c′ does not depend on the sequence in which vertices are toppled. We write c′ = σ(c) and call it the stabilization of c.

We now define a Markov chain on the set of stable configurations of a graph (G, v_{0}). Let μ = (μ_{1}, …, μ_{n}) be a probability distribution on {1, …, n} such that μ_{i} > 0 for all i ∈ {1, …, n}. At each step of the Markov chain we add a grain at the vertex v_{i} with probability μ_{i} and stabilize the resulting configuration. Formally the transition matrix Q is given by:

for all c, c′ ∈ Stable_{v_{0}} (G) , Q(c, c′) = ∑_{i=1}^{n} μ_{i}𝟙_{σ(c+α_{i})=c′}.

The recurrent states for the Markov chain are the set of configurations which appear infinitely often in the long-time running of the model. Given a graph (G, v_{0}), we let Rec_{v} (G) be the set of recurrent states on the graph G in which the vertex v acts as the sink. We omit the subscript when it is clear which vertex is acting as the sink.

Proposition 1.1. A configuration c ∈ Config_{v_{0}}(G) is recurrent if there exists some configuration a ∈ Config_{v_{0}}(G), satisfying a_{i} ≥ d_{i} for all i ∈ {1, …, n}, such that c = σ(a).

An orientation O of G is an orientation of every edge of E. If H is a subgraph of G, then O|_{H} will denote the restriction of the orientation O to the edges of H. An orientation is acyclic if it contains no directed cycles. A vertex v ∈ V is a source of the orientation O if it has no incoming edges. It is easy to check that an acyclic orientation has at least one source. The following result was first stated in these terms by Biggs [6], although the author credits a previous paper [14] as having equivalent results.

Theorem 1.2. Let c ∈ Stable_{v_{0}} (G). Then c is recurrent if, and only if, there exists an acyclic orientation O of G, such that

(a) The sink v_{0} is the unique source of O. We say that O is sink-rooted.

(b) We have:

c_{i} ≥ out_{i}(O) for all 1 ≤ i ≤ n,  (2)

where out_{i}(O) is the number of outgoing edges from the vertex v_{i} in the orientation O.

Proposition 1.1 and Theorem 1.2 provide two characterizations of recurrent states. A further characterization, in terms of the so-called burning algorithm (see [19]) will be given in the proof of Theorem 3.2. However, it is in general difficult to describe all the recurrent states for a given graph (G, v_{0}). Using the matrix-tree theorem, one can show that the number of recurrent states equals the number of spanning trees of the graph [19]. There are various bijective proofs of this result: in [19] the author provides a non-canonical bijection between recurrent states and spanning trees, while the authors of [5] and [8] both provided refined versions which enumerate recurrent configurations according the the level statistic.

This statistic is a popular statistic on sandpile configurations, and we will study it in conjunction with some of our decomposition theorems. Given a recurrent configuration c ∈ Rec_{v_{0}} (G), define the level of c to be

level_{v_{0}} (c) := d_{v_{0}} − |E| + ∑_{v∈V_{[1,n]}} c_{v},  (3)

where |E| denotes the number of elements in the set E. From [18, Thm. 3.5] we have that if G = (V, E) is a graph and c ∈ Rec_{v_{0}} (G), then 0 ≤ level_{v_{0}} (c) ≤ |E| − |V |. Consequently the level of a recurrent configuration is always a non-negative integer. We define the level polynomial of a graph G to be the generating function of the level statistic over the set of recurrent configurations on that graph;

Level_{G,v_{0}} (x) := ∑_{c∈Rec_{v_{0}}(G)} x^{level^{v_{0}}(c)}.  (4)

Recall that the Tutte polynomial of a (connected) graph G = (V, E) is defined by

T_{G}(x, y) := ∑_{S⊆E}(x − 1)^{cc(S)−1}(y − 1)^{cc(S)+|S|−|V |},  (5)

where for S ⊆ E, cc(S) denotes the number of connected components of the subgraph (V, S).

The level and Tutte polynomials of a graph are related by the following well-known result that was initially proven by López [18], following a conjecture by Biggs. Subsequent combinatorial (bijective) proofs have been given, for instance by Cori and Le Borgne [8], and Bernardi [5].

Theorem 1.3. Let G be a graph. Then we have Level_{G,v_{0}} (x) = T_{G}(1, x). In particular, the level polynomial is independent of the choice of sink.

Theorem 1.3 makes some of the results of this paper such as Corollaries 3.4 or 4.2 entirely natural in terms of spanning trees of the graph. However, the structure inherent to the sandpile model, both in the case of the Markov chain transitions previously mentioned in this section and of the additive structure of the sandpile group introduced in Section 5, is much more explicit in terms of the recurrent states than it is in terms of the spanning trees. As such, the focus of this paper is very much on the explicit description of the recurrent states of the graph with respect to the decompositions studied, which is more difficult.

Example 1.4. Let G be the graph in Figure 1, where the vertex v_{0} acts as the sink.

We have Stable_{v_{0}} (G) = {(0, 0), (0, 1), (1, 0), (1, 1)}. By Theorem 1.2, the configuration (0, 0) cannot be recurrent. Indeed, any direction given to the edge (v_{1}, v_{2}) would result in one of those two vertices having an outgoing edge, which would contradict Condition (2) (the inequality in Theorem 1.2). For the configuration (0, 1), we build a sink-rooted, acyclic orientation which satisfies Condition (2) by directing the edges from v_{0} to v_{1}, from v_{0} to v_{2},

\begin{matrix}v_{1} \\ v_{2} \\ v_{0} \\ G \end{matrix}

Figure 1. The graph G: the sink v_{0} is represented by a square, the non sink vertices v_{1}, v_{2} by circles. The squares and circles will become important later in the paper when non-sink vertices may become sink vertices.

and from v_{2} to v_{0}, as illustrated in Figure 2. Thus, by Theorem 1.2, the configuration (0, 1) is recurrent.

01

Figure 2. The configuration (0, 1) with the corresponding orientation.

By symmetry, the configuration (1, 0) is also recurrent. Finally, note that the orientation of Figure 2 also satisfies Condition (2) for the configuration (1, 1), which is therefore recurrent. Finally, we conclude that

Rec_{v_{0}} (G) = {(0, 1), (1, 0), (1, 1)}.

We may deduce from this the level polynomial for the graph G. We get Level_{G,v_{0}} (x) = x + 2. This may also be deduced from Theorem 1.3 since the Tutte polynomial of G is given by T_{G}(x, y) = x^{2} + x + y, so that T_{G}(1, x) = x + 2.

The process by which we determined that the configuration (1, 1) is also recurrent in Example 1.4 above leads to an interesting generalization. Given a graph (G, v_{0}), there is a natural partial order ⪯ on the set Config_{v_{0}}(G) of all configurations by setting c ⪯ c′ if, and only if, c_{i} ≤ c′_{i} for all i ∈ {1, …, n}.

Now notice that, if we have a recurrent configuration c = (c_{1}, …, c_{n}) and an orientation O which satisfies Condition (2), then the same orientation O also satisfies the condition for the configuration c + α_{i}, for any i ∈ {1, …, n}. This is also immediate from the definition of the Markov chain, since there is a positive probability of adding a grain at the vertex v_{i}, thus Q(c, c + α_{i}) > 0. This leads to the following result.

Proposition 1.5. For any graph G, the configuration c^{max} := (d_{1}−1, …, d_{n}−1) is recurrent. It is the maximal recurrent configuration for the partial order ⪯. Moreover, for any c = (c_{1}, …, c_{n}), the interval [c, c^{max}] of the poset (Rec_{v_{0}} (G) , ⪯) is given by

[c, c^{max}] = {c_{1}, c_{1} + 1, …, d_{1} − 1} × … × {c_{n}, c_{n} + 1, …, d_{n} − 1}.

There is a well established characterization of recurrent states of the sandpile model on the complete graph in terms of parking functions. We will make use of this in later sections, but will state it here since it serves as a good reference for considering small examples throughout the paper.

Definition 1.6. A parking function of size n is a sequence of non-negative integers (a_{1}, …, a_{n}) such that, when they are rearranged in weakly increasing order as (b_{1}, …, b_{n}), we have b_{i} < i for all 1 ≤ i ≤ n.

Theorem 1.7. The set Rec_{v_{0}} (K_{n}) is characterized by the following set

Rec_{v_{0}} (K_{n}) = {(n−2−a_{1}, …, n−2−a_{n−1}) : (a_{1}, …, a_{n−1}) if a parking function of size n}.

Parking functions can be easily written down from permuting the heights of horizontal steps of Dyck paths/sequences. Let Dyck_{n} = {(a_{1}, …, a_{n}) : a_{i} ∈ {0, …, i − 1} and a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{n}}. For example,

Dyck_{3} = {(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 1), (0, 1, 2)}.  (6)

Using Theorem 1.7 in conjunction with the notion of Dyck paths/sequences allows us to write down an explicit expression for Rec_{v_{0}} (K_{n}):

Rec_{v_{0}} (K_{n}) = {(n − 2 − a_{π(1)}, …, n − 2 − a_{π(n−1)}) : π ∈ Sym_{n−1}, (a_{1}, …, a_{n−1}) ∈ Dyck_{n−1}}. (7)

Example 1.8. We have

Rec_{v_{0}} (K_{4}) = {(2 − a_{π(1)}, 2 − a_{π(2)}, 2 − a_{π(3)}) : π ∈ Sym_{3} and (a_{1}, a_{2}, a_{3}) ∈ Dyck_{3}}. (8)

Using the list in Equation (6), we have

Rec_{v_{0}} (K_{4}) ={(2, 2, 2), (2, 2, 1), (2, 1, 2), (1, 2, 2), (2, 2, 0), (2, 0, 2), (0, 2, 2), (2, 1, 1),
(1, 2, 1), (1, 1, 2), (2, 1, 0), (2, 0, 1), (1, 2, 0), (1, 0, 2), (0, 1, 2), (0, 2, 1)}. (9)

Example 1.9. To determine Rec_{v_{0}} (K_{5}), we list all 14 elements of Dyck_{4}:

Dyck_{4} ={(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3), (0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3),
(0, 0, 2, 2), (0, 0, 2, 3), (0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3), (0, 1, 2, 2), (0, 1, 2, 3)}

Using this we have

Rec_{v_{0}} (K_{5}) = {(3 − a_{π(1)}, 3 − a_{π(2)}, 3 − a_{π(3)}, 3 − a_{π(4)}) : π ∈ Sym_{4} and (a_{1}, a_{2}, a_{3}) ∈ Dyck_{4}}.

There will be 125 of these sequences, and we do not list them here.

Note that in general there are n^{n−2} parking configurations on K_{n}, so the set of recurrent configurations may be huge.

2. Recurrent states under edge duplication

In this section we will show how recurrent states of the sandpile model on a graph change when every edge of a graph is replaced with k copies of itself. Let G = (V, E) be a graph. For a positive integer k we define G^{(k)} to be the multigraph G where every edge of E is replaced with k copies of itself. That is G^{(k)} = (V, E^{(k)}), where E^{(k)} is the multiset ⋃_{e∈E}{e_{1}, …, e_{k}},

with e_{j} = e for all j ∈ {1, …, k}.

Theorem 2.1. Let c = (c_{1}, …, c_{n}) ∈ Config_{v_{0}}(G). Then the following are equivalent:

(a) c ∈ Rec_{v_{0}} (G^{(k)}).

(b) c̃:= (⌊c_{1}/k⌋, …, ⌊c_{n}/k⌋) ∈ Rec_{v_{0}} (G).

Proof. We first show that (a) ⇒ (b). Assume that c ∈ Rec_{v_{0}} (G^{(k)}). By Theorem 1.2, there exists a sink-rooted acyclic orientation O^{(k)} on G^{(k)}, such that:

c_{i} ≥ out_{i} (O^{(k)}) for all 1 ≤ i ≤ n.  (10)

Now since O^{(k)} is acyclic, for any edge e ∈ E, the corresponding edges e_{1}, …, e_{k} ∈ E^{(k)} must all be oriented in the same direction (if two are oriented in opposite directions, those two edges create a directed cycle). By giving the edge e the same orientation as that of the corresponding edges e_{1}, …, e_{k}, this allows us to define an orientation O on G, such that

out_{i} (O^{(k)}) = k · out_{i}(O) for all 1 ≤ i ≤ n.  (11)

Moreover, it is easy to check that since the orientation O^{(k)} is sink-rooted and acyclic, so is the orientation O. Finally, we have:

out_{i}(O) = \frac{1}{k} out_{i} (O^{(k)}) ≤ \frac{1}{k}c_{i} = \frac{c_{i}}{k} for all 1 ≤ i ≤ n,

by using (11) followed by (10). Since out_{i}(O) is an integer, this implies that

out_{i}(O) ≤ ⌊\frac{c_{i}}{k} ⌋ = c̃_{i} for all 1 ≤ i ≤ n.

Since O is a sink-rooted acyclic orientation of G satisfying the above, it follows from Theorem 1.2 that c̃ ∈ Rec_{v_{0}} (G).

We now show that (b) ⇒ (a). Assume that c is such that c̃ ∈ Rec_{v_{0}} (G). By Theorem 1.2, there exists a sink-rooted acyclic orientation O on G, such that:

c̃_{i} ≥ out_{i}(O) for all 1 ≤ i ≤ n.  (12)

Similarly to above, by orienting all edges e_{1}, …, e_{k} of E^{(k)} corresponding to an edge e of E in the same direction as e, we get a sink-rooted acyclic orientation O^{(k)} on G^{(k)} satisfying Equation (11). It follows that:

c_{i} ≥ k · ⌊\frac{c_{i}}{k} ⌋ = k · c̃_{i} ≥ k · out_{i}(O) = out_{i} (O^{(k)}) for all 1 ≤ i ≤ n,

and as before, Theorem 1.2 implies that c ∈ Rec_{v_{0}} (G^{(k)}). □

From Theorem 2.1 we can deduce the following formula for the level polynomial of the graph G^{(k)}.

Corollary 2.2. Let k be a positive integer. We have:

Level_{G^{(k)},v_{0}} (x) = (1 + x + … + x^{k−1})^{|V |−1} · Level_{G,v_{0}} (x^{k}) .

In particular, |Rec_{v_{0}} (G^{(k)})| = k^{(|V |−1)}|Rec_{v_{0}} (G) |.

Proof. Let c ∈ Config_{v_{0}}(G^{(k)}), and c̃ := (⌊c_{1}/k⌋, …, ⌊c_{n}/k⌋). Define a_{i} := c_{i} − k⌊c_{i}/k⌋ for i ∈ {1, …, n}. Standard floor inequalities show that a_{i} ∈ {0, …, k − 1} for all 1 ≤ i ≤ n.

Thus Theorem 2.1 can be re-stated as follows: c = (c_{1}, …, c_{n}) ∈ Rec_{v_{0}} (G^{(k)}) if, and only if, there exists a unique pair (γ, r) with γ = (γ_{1}, …, γ_{n}) ∈ Rec_{v_{0}} (G) , r = (r_{1}, …, r_{n}) ∈ {0, …, k − 1}^{n} such that c_{i} = kγ_{i} + r_{i} for all 1 ≤ i ≤ n.

If c = (c_{1}, …, c_{n}) ∈ Rec_{v_{0}} (G^{(k)}) then we can write

level_{v_{0}} (c) = d_{v_{0}}^{G^{(k)}} − |E^{(k)}| + ∑_{i=1}^{n} c_{i} = kd_{v_{0}}^{G} − k|E| + ∑_{i=1}^{n}(kγ_{i} + r_{i}) = k · level_{v_{0}} (γ) + ∑_{i=1}^{n} r_{i}.

Therefore, we can compute:

Level_{G^{(k)},v_{0}} (x) = ∑_{c∈Rec_{v_{0}}(G^{(k)})} x^{level^{v_{0}}(c)} = ∑_{\begin{matrix}γ∈Rec_{v_{0}}(G) \\ 0≤r_{1},...,r_{n}<k \end{matrix}} x^{(k·level_{v_{0}}(γ)+r_{1}+...+r_{n})}

= ( ∑_{0≤r_{1},...,r_{n}<k} (x^{r_{1}}) … (x^{r_{n}})) · ( ∑_{γ∈Rec_{v_{0}}(G)} (x^{k})^{level^{v_{0}}(γ)})

= (1 + x + … + x^{k−1})^{n} · Level_{G,v_{0}} (x^{k}) .

□

Example 2.3. We develop an example to show some of the computational gains which can be made through applying Theorem 2.1 and its corollary. Consider the graph G from Figure 3 below. We wish to determine the recurrent configurations of G^{(2)}.

v_{1} v_{2} v_{0} G v_{1} v_{2} v_{0} G^{(2)}

Figure 3. The graphs G and G^{(2)}.

We can show that Rec_{v_{0}} (G) = {(0, 1), (1, 0), (1, 1), (2, 0), (2, 1)}. Now Theorem 2.1 tells us that c = (c_{1}, c_{2}) ∈ Rec_{v_{0}} (G^{(2)}) if, and only if, there exists a unique pair (γ, α) with γ = (γ_{1}, γ_{2}) ∈ Rec_{v_{0}} (G) , α = (α_{1}, α_{2}) ∈ {0, 1}^{2} such that c_{i} = kγ_{i} + α_{i} for all i = 1, 2.

In words, recurrent configurations on G^{(2)} are obtained from recurrent configurations on G by multiplying them by two and adding up to one grain at each vertex. This is made clear in Table 1.

This table allows us to determine Rec_{v_{0}} (G^{(2)}). We may also compute the level polynomials. We get

Level_{G,v_{0}} (x) = x^{2} + 2x + 2,

and thus, by Corollary 2.2

Level_{G^{(k)},v_{0}} (x) = (1 + x)^{2} · ((x^{2})^{2} + 2 (x^{2}) + 2) = x^{6} + 2x^{5} + 3x^{4} + 4x^{3} + 4x^{2} + 4x + 2,

Recurrent  Corresponding recurrent
configurations on G configurations on G^{(2)}
(0, 1)  (0, 2)
(0, 3), (1, 2), (1, 3)
(1, 0)  (2, 0)
(2, 1), (3, 0), (3, 1)
(1, 1)  (2, 2)
(2, 3), (3, 2), (3, 3)
(2, 0)  (4, 0)
(4, 1), (5, 0), (5, 1)
(2, 1)  (4, 2)
(4, 3), (5, 2), (5, 3)

Table 1. The correspondence between recurrent configurations on G and on G^{(2)}.

which can also be computed directly using the second column of Table 1.

3. Recurrent states on graphs having cut vertices

In this section we show how the recurrent states on a graph which contains a cut vertex may be decomposed into recurrent states on the two different parts of the graph which meet at this cut vertex. We then build on this result by showing that a graph whose set of cut vertices have a tree like structure has a recurrent configuration set that can be decomposed in a similar manner.

Definition 3.1. Let G = (V, E) be a finite, connected graph. We say that v ∈ V is a cut vertex of G if removing the vertex v and all edges incident to v makes G disconnected.

Theorem 3.2. Let G = (V, E) be a finite, connected graph, on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that v_{n} is a cut vertex of G. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n,n+m]}]. Given c = (c_{1}, …, c_{n+m}) ∈ Config_{v_{0}}(G), let c^{(1)} := (c_{1}, …, c_{n−1}, c_{n} − d_{n}^{H_{2}}) and c^{(2)} := (c_{n+1}, …, c_{n+m}), where d_{n}^{H_{2}} is the degree of the vertex v_{n} in the graph H_{2}. Then

c ∈ Rec_{v_{0}} (G) if and only if c^{(1)} ∈ Rec_{v_{0}} (H_{1}) and c^{(2)} ∈ Rec_{v_{n}} (H_{2}) .

\begin{matrix}v_{0} \\ v_{n} \\ H_{1} \\ H_{2} \end{matrix}

Figure 4. The graph G with its cut vertex v_{n}.

Remark 3.3. Theorem 3.2 is obvious in terms of the spanning trees of the graph. Indeed, the spanning trees of such a graph G are simply given by the “independent” products of spanning trees of H_{1} and H_{2}. The difficulty here is to describe such decompositions in terms of the recurrent states.

Proof. First let us assume that c^{(1)} ∈ Rec_{v_{0}} (H_{1}) and c^{(2)} ∈ Rec_{v_{n}} (H_{2}). Then there exists a sink-rooted acyclic orientation O_{1} of H_{1}, and an acyclic orientation O_{2} of H_{2} whose unique source is the vertex v_{n}, such that:

c_{i}^{(1)} ≥ out_{i}(O_{1}), for all 1 ≤ i ≤ n, and c_{j}^{(2)} ≥ out_{j}(O_{2}), for all n + 1 ≤ j ≤ n + m.

Since the edges of the graphs H_{1} and H_{2} form a partition of the edges of G, we may define an orientation O := O_{1} ∪ O_{2} of G. By construction, O is sink-rooted and acyclic.

For i ∈ {1, …, n − 1}, we have:

c_{i} = c_{i}^{(1)} ≥ out_{i}(O_{1}) = out_{i}(O).

Similarly, for j ∈ {n + 1, …, n + m}, we have:

c_{j} = c_{j}^{(2)} ≥ out_{j}(O_{2}) = out_{j}(O).

Finally, at the vertex v_{n}, we have:

c_{n} = c_{n}^{(1)} + d_{n}^{H_{2}} ≥ out_{n}(O_{1}) + d_{n}^{H_{2}} = out_{n}(O_{1}) + out_{n}(O_{2}) = out_{n}(O),

since v_{n} is a source of the orientation O_{2}. Thus the orientation O satisfies Condition (2), and by Theorem 1.2, the configuration c is recurrent.

To show the converse, we first recall some results concerning the so-called burning algorithm (see [19]). This algorithm inputs a stable configuration a on a graph G = (V, E), and establishes if a is recurrent. We now describe this algorithm.

B1. Initialise by setting V_{0}^{B} = {v_{0}}. The set V_{i}^{B} will be the set of vertices burnt up to

and including time i. B2. (i) Assume for some i ≥ 0, we have constructed the set V_{i}^{B} of vertices burnt up to

and including time i. (ii) Let V_{i}^{U} be the set of vertices not yet burnt and set G_{i} := G[V_{i}^{U}]. (iii) Now set Ṽ_{i} := {v ∈ V_{i}^{U}; a_{v} ≥ d_{v}^{G_{i}}} to be the set of unstable vertices in the

configuration a restricted to G_{i}. (iv) By construction, since a is stable in the graph G, the instability of any such

vertex must arise from the burning of previous vertices.

(v) We set V_{i+1}^{B} := V_{i}^{B} ∪ Ṽ_{i}. B3. The algorithm terminates when we reach a time i such that no vertices can subse-

quently be burnt, i.e. Ṽ_{i} = ∅. It outputs V^{B} := V_{i}^{B}, which is the set of all vertices burnt beforehand.

Notice that since V_{0}^{B} ⊆ V_{1}^{B} ⊆ V_{2}^{B} ⊆ ⋯ ⊆ V, the burning algorithm does indeed terminate. Our interest lies in the following facts.

(1) The configuration a is recurrent if, and only if, V^{B} = V, i.e. the burning algorithm applied to a burns all vertices of the initial graph.

(2) Let a ∈ Rec_{v_{0}} (G). Define a total order ≺_{b} on the set of vertices V by setting v_{i} ≺_{b} v_{j} if, when applying the burning algorithm to a, either v_{i} is burned before v_{j}, or they are burned at the same time and i < j. Now define an orientation O_{b} of G by orienting the edge {v, w} from v to w if, and only if, v ≺_{b} w. Then this orientation is sink-rooted, acyclic, and satisfies:

a_{v} ≥ out_{v}^{O_{b}}, for all v ∈ V.

We now return to the proof of Theorem 3.2. Let c ∈ Rec_{v_{0}} (G). Apply the burning algorithm to c, and let O_{b} be the corresponding sink-rooted acyclic orientation as in part (2) of the above. Since the cut vertex v_{n} lies on all paths from the sink to vertices v_{k} when k ≥ n + 1, this implies that the vertex v_{n} must be burnt before any vertices with higher indices. Therefore, in the orientation O_{b}, all edges from v_{n} to vertices of H_{2} are oriented away from v_{n}.

We now define O_{1} := O_{b}|_{H_{1}} and O_{2} := O_{b}|_{H_{2}}. Due to the above, it follows that v_{n} is the unique source of the orientation O_{2}. Moreover, by construction O_{1} is sink-rooted, and both orientations are acyclic. Now let k ∈ {1, …, n + m}. We have:

if k ≤ n − 1, then c_{k}^{(1)} = c_{k} ≥ out_{k}(O) = out_{k}(O_{1});  (13)
if k = n, then c_{n}^{(1)} = c_{n} − d_{n}^{H_{2}} ≥ out_{n}(O) − d_{n}^{H_{2}} = out_{n}(O) − out_{n}(O_{2}) = out_{n}(O_{1}); (14)

if k ≥ n + 1, then c_{k}^{(2)} = c_{k} ≥ out_{k}(O) = out_{k}(O_{2}).  (15)

By Theorem 1.2, Equations (13) and (14) imply that c^{(1)} ∈ Rec_{v_{0}} (H_{1}), while Equation (15) implies that c^{(2)} ∈ Rec_{v_{n}} (H_{2}). This completes the proof of Theorem 3.2. □

Theorem 3.2 implies the following decomposition for the level polynomial of a graph with a cut vertex.

Corollary 3.4. Let G = (V, E) be a finite, connected graph, on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that v_{n} is a cut vertex of G. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n,n+m]}]. Then we have:

Level_{G,v_{0}} (x) = Level_{H_{1},v_{0}} (x) · Level_{H_{2},v_{n}} (x) .

Proof. Let c be a configuration on G. Let c^{(1)} (respectively c^{(2)}) be the configurations on H_{1} (respectively H_{2}) as defined in Theorem 3.2. Then we have:

level_{v_{0}} (c) = d_{0} − |E| + (c_{1} + … + c_{n−1}) + c_{n} + (c_{n+1} + … + c_{n+m})

= d_{0} − (|E_{1}| + |E_{2}|) + (∑_{i=1}^{n−1} c_{i}^{(1)}) + (c_{n}^{(1)} + d_{n}^{H_{2}}) + ( ∑_{i=n+1}^{n+m} c_{i}^{(2)})

= (d_{0} − |E_{1}| + ∑_{i=1}^{n} c_{i}^{(1)}) + (d_{n}^{H_{2}} − |E_{2}| + ∑_{i=n+1}^{n+m} c_{i}^{(2)})

= level_{v_{0}} (c^{(1)}) + level_{v_{n}} (c^{(2)}) , and the claim immediately follows. □

We note that Corollary 3.4 is in fact a consequence of the Specification Theorem 1.3, and the following result, due to Tutte [21].

Theorem 3.5. Let G be a graph. Assume G has a cut vertex which splits G into two components H_{1} and H_{2}. Then we have:

T_{G}(x, y) = T_{H_{1}}(x, y) · T_{H_{2}}(x, y).

The proof of Theorem 3.5 relies on the expression of the Tutte polynomial in terms of internal and external activities of spanning trees. However, our Theorem 3.2 gives a combinatorial explanation of this decomposition (at least at the specification x = 1). It is also worth noting that a similar decomposition result was given for the so-called flow polynomial, which is another specification of the Tutte polynomial, in [20].

\begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ G \end{matrix}

Figure 5. A graph G with its cut vertex v_{2}.

Example 3.6. Consider the graph G of Figure 5. The vertex v_{2} is a cut vertex. We may thus determine the recurrent configurations by combining recurrent configurations on the subgraphs H_{1} and H_{2}, adding two grains at the cut vertex v_{2}, since it has two incident edges in H_{2}. We show this in the Table 2, in which we also compute the level polynomials.

Graph  \begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ H_{1} \end{matrix}  \begin{matrix}v_{2} \\ v_{3} \\ v_{4} \\ H_{2} \end{matrix}  \begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ G \end{matrix}
Recurrent  (0, 1)  (0, 1), (1, 0), (1, 1) (0, 3, 0, 1), (0, 3, 1, 0), (0, 3, 1, 1)
configurations  (1, 0)  (0, 1), (1, 0), (1, 1) (1, 2, 0, 1), (1, 2, 1, 0), (1, 2, 1, 1)
(1, 1)  (0, 1), (1, 0), (1, 1) (1, 3, 0, 1), (1, 3, 1, 0), (1, 3, 1, 1)
(2, 0)  (0, 1), (1, 0), (1, 1) (2, 2, 0, 1), (2, 2, 1, 0), (2, 2, 1, 1)
(2, 1)  (0, 1), (1, 0), (1, 1) (2, 3, 0, 1), (2, 3, 1, 0), (2, 3, 1, 1)
Level x^{2} + 2x + 2 x + 2 x^{3} + 4x^{2} + 6x + 4
polynomial  = (x^{2} + 2x + 2) · (x + 2)

Table 2. Applying Theorem 3.2 to determine the recurrent configurations of G.

3.1. Cut vertices in graphs with an underlying tree-like structure. Theorem 3.2 showed us how to determine the recurrent configurations of the sandpile model on a graph G when it has one cut vertex that splits it into two subgraphs H_{1} and H_{2}. The subgraph H_{1} contained the sink of G, and the intersection of H_{1} and H_{2} is the cut vertex v_{n}. If one considers the graphs H_{1} and H_{2} now as vertices, then Theorem 3.2 is the result (see Figure 6) for a graph constructed on a single, rooted edge, where: the root vertex corresponds to the subgraph H_{1} containing the sink v_{0} of G; the non-root vertex corresponds to the other subgraph H_{2}; the edge corresponds to the cut vertex v_{n}. In this subsection we generalize

\begin{matrix}v_{0} \\ v_{n} \\ H_{1} \\ H_{2} \\ H_{1} \\ H_{2} \\ v_{n} \end{matrix}

Figure 6. A graph with a cut vertex can be seen as a graph constructed on a single edge.

this from the case of a single rooted edge to the case of a rooted tree. First we will need some notation to be able to discuss the associate tree-structure.

Consider a tree (T, ρ), rooted at some vertex ρ. For clarity, we will refer to vertices of the tree as nodes, to distinguish them from vertices of the graph G. Let nodes (T) denote the node set of T. Since T is rooted, every non-root node t ∈ nodes (T) \ {ρ} will have an adjacent node on the (unique) path from t to the root ρ called the parent of t and denoted by parent(t). All other nodes adjacent to t are called descendants of t, and this set is denoted desc(t). If a node has no descendants then it is called a leaf.

We now explain what we mean for a graph G to have an underlying tree-structure (T, ρ).

Definition 3.7. We will say that the graph-sink pair (G, v_{ρ}) has an underlying cv-tree structure (T, ρ) if the following holds. The graph G can be written as

G = ⋃_{t∈nodes(T)} H_{t},

where the pair (T, ρ) is a rooted tree and associated to every node t ∈ nodes (T) is a connected, loop-free, graph H_{t} = (V_{t}, E_{t}). Each graph H_{t} has a distinguished vertex v_{t} ∈ V_{t} such that:

(a) for all t ∈ nodes (T) \ {ρ}, we have V_{t} ∩ V_{parent(t)} = {v_{t}};

(b) if (t, t′) is not an edge of T, then V_{t} ∩ V_{t′} = ∅.

See Figure 7 for an illustration of the construction in Definition 3.7.

Remark 3.8. Every graph can be decomposed into blocks, where a block is a maximal 2connected subgraph. It is well-known that this block decomposition has a tree structure as in that of Definition 3.7, and is thus a special case of a cv-tree structure (the blocks of the cv-tree structure may be graphs which are not 2-connected but on which the recurrent configurations are well known, e.g. trees). In particular, Theorems 3.9 and 5.7 allow one to reduce the analysis of recurrent configurations to the 2-connected case.

\begin{matrix}H_{0} \\ H_{1} \\ H_{4} \\ H_{5} \\ H_{2} \\ H_{6} \\ H_{7} \\ 1 \\ 4 \\ 5 \\ 2 \\ 3 \\ 6 \\ v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \\ 0 \end{matrix}

Figure 7. A graph with its underlying tree structure.

Theorem 3.9. Let G = ⋃_{t∈nodes(T)} H_{t} have an underlying cv-tree structure (T, ρ). Let c ∈

Config_{v_{ρ}}(G). For any node t ∈ nodes (T), we let t_{1}, …, t_{k} be the descendants of t in T. Define the configurations c^{(t)} on Config_{v_{t}}(H_{t}) by:

c^{(t)}(v) := \begin{cases}c(v) & if v ∉ \{v_{t_{1}}, …, v_{t_{k}}\} \\ c(v) − d^{H_{t_{i}}}(v) & if v = v_{t_{i}} \end{cases}

Then c ∈ Rec_{v_{ρ}} (G) if, and only if, c^{(t)} ∈ Rec_{v_{t}} (H_{t}) for all t ∈ nodes (T).

Proof. Our proof is by induction on the number of nodes in the cv-tree nodes (T).

If |nodes (T) | = 1, then the tree t is reduced to a single (root) vertex ρ, and the configuration c^{(ρ)} is just the configuration c, since ρ has no descendants. In this case the statement is a tautology.

Next, let us suppose that we have proven our result for |nodes (T) | = k for some k ≥ 1. Let (T, ρ) be a rooted tree with k + 1 nodes, and assume that G = ⋃_{t∈nodes(T)} H_{t} has an

underlying cv-tree structure (T, ρ). Fix some leaf ℓ of T. Since ℓ has no descendants, the configuration c^{(ℓ)} is just the restriction of c to H_{ℓ}. Define G′ := ⋃_{t∈nodes(T)\{ℓ}} H_{t}, and let c′ be

the configuration on G′ defined by

c′(v) := \begin{cases}c(v) if v ≠ v_{ℓ} \\ c(v_{ℓ}) − d^{H_{ℓ}}(v_{ℓ}) if v = v_{ℓ}. \end{cases}

Now by construction, the vertex v_{ℓ} is a cut vertex of the graph G, splitting it into H_{ℓ} and G′. We may therefore apply Theorem 3.2, to get that c ∈ Rec_{v_{ρ}} (G) if, and only if, c^{(ℓ)} ∈ Rec_{v_{ℓ}} (H_{ℓ}) and c′ ∈ Rec_{v_{ρ}} (G′). But the graph G′ is constructed on a rooted tree with |nodes (T) | − 1 = k nodes, so that we may apply the induction hypothesis to c′, which combined with the above yields the desired result. □

Similarly to Corollary 3.4 in the cut vertex case, this yields a decomposition of the level polynomial for graphs with a tree-like structure.

Corollary 3.10. Let G = ⋃_{t∈nodes(T)} H_{t} be constructed on a rooted tree (T, ρ). Then we have

Level_{G,v_{ρ}} (x) = ∏_{t∈nodes(T)} Level_{H_{t},v_{t}} (x) .

4. Recurrent states on graphs with isthmuses

Having dealt with the cut vertex case, it is natural to ask ourselves what happens when the graph has an isthmus, an edge whose removal disconnects the graph.

Theorem 4.1. Let G = (V, E) be a finite, connected graph on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that the edge e = (v_{n}, v_{n+1}) is an isthmus. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n+1,n+m]}]. Let c = (c_{1}, … c_{n+m}) ∈ Config_{v_{0}}(G). Define c^{(1)} := (c_{1}, …, c_{n−1}, c_{n} −1) and c^{(2)} := (c_{n+2}, …, c_{n+m}). Then c ∈ Rec_{v_{0}} (G) if and only if c_{n+1} = d_{n+1} − 1, c^{(1)} ∈ Rec_{v_{0}} (H_{1}), and c^{(2)} ∈ Rec_{v_{n+1}} (H_{2}).

\begin{matrix}v_{0} \\ v_{n} \\ v_{n+1} \\ H_{1} \\ H_{2} \end{matrix}

Figure 8. A graph G with an isthmus (v_{n}, v_{n+1}).

It is worth noting that Theorem 4.1 was proved by Lopez [18] in the special case where the isthmus is adjacent to the sink, as part of his proof of the Specification Theorem 1.3.

As in the cut vertex case, this theorem allows us to infer the following decomposition for the level polynomial.

Corollary 4.2. Let G = (V, E) be a finite connected graph on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that the edge e = (v_{n}, v_{n+1}) is an isthmus of G. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n+1,n+m]}]. Then we have:

Level_{G,v_{0}} (x) = Level_{H_{1},v_{0}} (x) · Level_{H_{2},v_{n+1}} (x) .

This can also be inferred from Theorem 1.3. Indeed, if e is an isthmus, then T_{G}(x, y) = x · T_{G.e}(x, y), where G.e is the graph G with the edge e contracted (reduced to a single vertex). In the case of the level polynomial, this yields Level_{G,v_{0}} (x) = Level_{G.e,v_{0}} (x). Since contracting an isthmus creates a cut vertex at the contracted vertex, we can then apply Corollary 3.4 to get the desired result.

Rather than proving Theorem 4.1, we prove a generalization to the case where the edge (v_{n}, v_{n+1}) is a multi-edge. That is, the graph G is formed of two components H_{1}, H_{2} connected by k copies of the same edge, as illustrated in Figure 9 below. We call such an edge a kmulti-isthmus.

\begin{matrix}v_{0} \\ v_{n} \\ v_{n+1} \\ H_{1} \\ H_{2} \end{matrix}

Figure 9. A graph G with a 3-multi-isthmus.

Theorem 4.3. Let G = (V, E) be a finite, connected graph on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that the edge e = (v_{n}, v_{n+1}) is a k-multi-isthmus for some k ≥ 1. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n+1,n+m]}]. Let c = (c_{1}, … c_{n+m}) ∈ Config_{v_{0}}(G). Define c^{(1)} := (c_{1}, …, c_{n−1}, c_{n} − k) and c^{(2)} := (c_{n+2}, …, c_{n+m}). Then we have c ∈ Rec_{v_{0}} (G) if and only if c^{(1)} ∈ Rec_{v_{0}} (H_{1}), c^{(2)} ∈ Rec_{v_{n+1}} (H_{2}), and

d_{n+1}^{H_{2}} = d_{n+1} − k ≤ c_{n+1} ≤ d_{n+1} − 1.

Corollary 4.4. Let G = (V, E) be a finite, connected graph on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that the edge e = (v_{n}, v_{n+1}) is a k-multi-isthmus for some k ≥ 1. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n+1,n+m]}]. Then we have

Level_{G,v_{0}} (x) = (1 + x + … + x^{k−1}) · Level_{H_{1},v_{0}} (x) · Level_{H_{2},v_{n+1}} (x) .

Since Theorem 4.1 and Corollary 4.2 correspond to Theorem 4.3 and Corollary 4.4 in the special case k = 1, it is sufficient to prove the latter two results.

Proof. Define I := G[V_{[n,n+1]}] to be the subgraph of G consisting of the multi-isthmus (v_{n}, v_{n+1}). Since v_{n} and v_{n+1} are both cut-vertices, the graph G has a cv-tree structure where the blocks are H_{1}, I, H_{2} and the underlying tree is a path graph. The set Rec_{v_{n}} (I) of recurrent states of the block I is straightforward to compute:

c = (c_{n+1}) ∈ Rec_{v_{n}} (I) if, and only if, c_{n+1} ∈ {0, …, k − 1},  (16)

and Theorem 4.3 immediately follows from this and Theorem 3.9.

Moreover, from Equation (16), we get that Level_{I,v_{n}} (x) = 1 + x + ⋯ + x^{k−1}, and applying Corollary 3.10 gives us Corollary 4.4, as desired. □

\begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ G \end{matrix}

Figure 10. A graph G containing a 2-multi-isthmus (v_{2}, v_{3}).

Example 4.5. Consider the graph G of Figure 10. This graph can be decomposed into two components H_{1} and H_{2}, connected by the 2-multi-isthmus (v_{2}, v_{3}). By Theorem 4.3, the recurrent configurations are given by the products of recurrent configurations on H_{1} and H_{2} as in the cut vertex case, which we complete by putting either two or three grains of sand at the vertex v_{3}. We show this in Table 3, and also compute the corresponding level polynomials.

Graph  \begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ G \end{matrix}  \begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ H_{1} \end{matrix} \begin{matrix}v_{3} \\ v_{4} \\ v_{5} \\ H_{2} \end{matrix}
Recurrent  (0, 3, 2, 0, 1), (0, 3, 3, 0, 1)  (0, 1)  (0, 1)
configurations (1, 2, 2, 0, 1), (1, 2, 3, 0, 1)  (1, 0)  (0, 1)
(1, 3, 2, 0, 1), (1, 3, 3, 0, 1)  (1, 1)  (0, 1)
(0, 3, 2, 1, 0), (0, 3, 3, 1, 0)  (0, 1)  (1, 0)
(1, 2, 2, 1, 0), (1, 2, 3, 1, 0)  (1, 0)  (1, 0)
(1, 3, 2, 1, 0), (1, 3, 3, 1, 0)  (1, 1)  (1, 0)
(0, 3, 2, 1, 1), (0, 3, 3, 1, 1)  (0, 1)  (1, 1)
(1, 2, 2, 1, 1), (1, 2, 3, 1, 1)  (1, 0)  (1, 1)
(1, 3, 2, 1, 1), (1, 3, 3, 1, 1)  (1, 1)  (1, 1)
Level  x^{3} + 5x^{2} + 8x + 4  x + 2  x + 2
polynomial = (1 + x) · (x + 2) · (x + 2)

Table 3. Applying Theorem 4.3 to determine the recurrent configurations of G.

5. Decomposition of the sandpile group

In this section we look at how the decomposition results from Section 3 affect the so-called sandpile group.

Let (G, v_{0}) be a graph, with vertex set V = {v_{0}, …, v_{n}} and edge set E. Recall that σ : Config_{v_{0}}(G) → Stable_{v_{0}} (G) denotes the stabilization operator. We define a binary operation ⊕ on Stable_{v_{0}} (G) by:

for all c, c′ ∈ Stable_{v_{0}} (G) , c ⊕ c′ := σ (c + c′) ,  (17)

where + denotes pointwise addition in Stable_{v_{0}} (G). Dhar showed in [11] that (Rec_{v_{0}} (G) , ⊕) is an Abelian group, called the sandpile group. We denote it S(G, v_{0}).

For the proofs of this section, we will need the following characterization of recurrent states, due to Dhar [11]. We first define a configuration b ∈ Config_{v_{0}}(G) by b := ∑_{i:{v_{i},v_{0}}∈E} α_{i},

where the sum is over all vertices adjacent to the sink, counted with multiplicity. Thus the configuration b corresponds to the toppling of the sink in an initially empty configuration.

Proposition 5.1. A configuration c ∈ Config_{v_{0}}(G) is recurrent if, and only if, σ(c + b) = c. Moreover, in the stabilization of c + b every vertex in V_{[1,n]} topples exactly once.

Theorem 5.2. Let G = (V, E) be a finite, connected graph, on the vertex set

V = {v_{0}, v_{1}, …, v_{n+m}}

where m, n ≥ 1. Assume that v_{n} is a cut vertex of G. Let H_{1} := G[V_{[0,n]}] and H_{2} := G[V_{[n,n+m]}]. We have:

S(G, v_{0}) ≅ S(H_{1}, v_{0}) × S(H_{2}, v_{n}),

where the symbol ≅ denotes group isomorphism, and × is the direct product of two groups.

We require two lemmas in order to prove this theorem. Given c = (c_{1}, …, c_{n+m}) ∈ Config_{v_{0}}(G), let c^{(1)} := (c_{1}, …, c_{n−1}, c_{n} − d_{n}^{H_{2}}) and c^{(2)} := (c_{n+1}, …, c_{n+m}), where d_{n}^{H_{2}} is the degree of the vertex v_{n} in the graph H_{2}.

Lemma 5.3. For any configurations c, c′ ∈ Rec_{v_{0}} (G), we have

(c ⊕ c′)^{(2)} = c^{(2)} ⊕ c^{′(2)}.  (18)

Proof. Let c, c′ ∈ Rec_{v_{0}} (G). Then c⊕c′ is the stabilization of the configuration c+c′. Let us examine how this stabilization might occur. We may choose to first stabilize the configuration in H_{2} except perhaps at v_{n}, by making only topplings at vertices in V_{[v_{n+1},...,v_{n+m}]}. We will reach a configuration γ where all these vertices are stable. The configuration γ, restricted to V_{[v_{n+1},...,v_{n+m}]}, is exactly the same configuration we would reach in the graph (H_{2}, v_{n}) by stabilizing the configuration c^{(2)} + c^{′(2)}, that is, the configuration c^{(2)} ⊕ c^{′(2)}.

Now of all the subsequent topplings to stabilize c+c′, only the topplings of the cut vertex v_{n} will effect the configuration on V_{[v_{n+1},...,v_{n+m}]}. But the effect of toppling v_{n} on these vertices is exactly the effect of toppling the sink on the graph (H_{2}, v_{n}). Since the configuration reached on (H_{2}, v_{n}) before any such toppling is c^{(2)} ⊕ c^{′(2)}, which is recurrent, toppling the sink and then stabilizing leaves this configuration unchanged by Proposition 5.1. This completes the proof of Lemma 5.3. □

Lemma 5.4. For any configurations c, c′ ∈ Rec_{v_{0}} (G), we have

(c ⊕ c′)^{(1)} = c^{(1)} ⊕ c^{′(1)} ⊕ κ,  (19)

where κ = κ (c^{(2)}, c^{′(2)}) := (d_{n}^{H_{2}} + |c^{(2)}| + |c^{′(2)}| − |c^{(2)} ⊕ c^{′(2)}|) α_{n}, with |c| designating the total number of grains of a configuration c, and α_{n} is the configuration with one grain at the vertex v_{n} and none elsewhere.

Proof. A crucial remark that stems from the proof of Lemma 5.3 is the following. When stabilizing the configuration c + c′, if the configuration is initially stabilized in H_{2}, then the topplings of the cut vertex v_{n} have no effect in H_{2}.

Now once we have initially stabilized c + c′ in H_{2}, we may stabilize it in H_{1}. The configuration to stabilize is thus the configuration c + c′ restricted to H_{1}, to which a certain number λ of grains have been added at v_{n}. These grains are added as a result of the original stabilization in H_{2}, they are the surplus of grains toppled into v_{n} through stabilizing (c + c′)^{(2)}. Thus λ = |c^{(2)}| + |c^{′(2)}| − |(c ⊕ c′)^{(2)}|, and we have

(c ⊕ c′)|_{H_{1}} = c|_{H_{1}} ⊕ c′|_{H_{1}} ⊕ λα_{n}.

Equation (19) with κ = (λ + d_{n}^{H_{2}}) α_{n} follows from the above, with the definition c_{n}^{(1)} = c_{n} + d_{n}^{H_{2}} resulting in the adjustment by an additive constant. □

Proof of Theorem 5.2. Lemmas 5.3 and 5.4 allow us to understand the operator ⊕ on Rec_{v_{0}} (G), and in particular its behaviour when restricted to the components H_{1}, H_{2}.

The result then follows from a group theory argument that we will now explain. Lemmas 5.3 and 5.4, combined with the Decomposition Theorem 3.2, mean that we have the following situation. We have a set G = H_{1}×H_{2}, where G,H_{1} and H_{2} are all equipped with an Abelian group structure. However, the binary addition operation in G does not decompose to product addition in H_{1} and H_{2}. Rather, for (c_{1}, c_{2}), (c′_{1}, c′_{2}) ∈ G, we have

(c_{1}, c_{2}) + (c′_{1}, c′_{2}) = (c_{1} + c′_{1} + κ(c_{2}, c′_{2}), c_{2} + c′_{2}),

where the function κ is described by Lemma 5.4.

Now from [7, Chapter IV] we get that such a group G is isomorphic to the direct product H_{1} × H_{2} if there exists a function a : H_{2} → H_{1} such that for any c_{2}, c′_{2} ∈ H_{2}, we have κ(c_{2}, c′_{2}) = a(c_{2}) + a(c′_{2}) − a(c_{2} + c′_{2}). In our case, simply setting a(c_{2}) = (|c_{2}| + d_{n}^{H_{2}}) α_{n} immediately yields the desired result. □

Remark 5.5. In fact, we make a slight abuse when using the group theory arguments in this case, since the configurations κ, a(c_{2}) are not in general recurrent configurations on H_{1}. However, this difficulty can be overcome by considering the unique recurrent configurations to which they are toppling equivalent (see [10, Theorem 1]) instead.

Example 5.6. Consider the graph G of Figure 11, where the vertex v_{2} is a cut vertex splitting the graph into two isomorphic components H_{1}, H_{2}. In Example 1.4, we showed that the components H_{i} have three recurrent configurations, which implies that S (H_{1}, v_{0}) ≅ S (H_{2}, v_{2}) ≅ ℤ/3ℤ. It immediately follows from Theorem 5.2 that

S (G, v_{0}) ≅ ℤ/3ℤ × ℤ/3ℤ.

Note that this is not a straightforward consequence of simply enumerating the recurrent configurations of G, since an Abelian group with nine elements could also be (isomorphic to) ℤ/9ℤ.

As with the transition from Theorem 3.2 to Theorem 3.9, an induction argument allows us to extend Theorem 5.2 to the case of graphs with an underlying cv-tree structure.

\begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ G \end{matrix}

Figure 11. A graph G with its cut vertex v_{2}.

Theorem 5.7. Let G = ⋃_{t∈nodes(T)} H_{t} have an underlying cv-tree structure (T, ρ). We have:

S (G, v_{ρ}) ≅ ∏_{t∈nodes(T)} S (H_{t}, v_{t}) ,

where ≅ denotes group isomorphism, and ∏ the direct product of the groups involved.

Remark 5.8. It is not clear that the result of Theorem 4.1 can be cast in a useful manner in terms of the sandpile group. The enumeration result in Corollary 4.2 suggests a decomposition of the form S(G^{(k)}) = S(G) × ℤ_{k}^{n−1}, but there are some simple examples for which this both holds and does not hold.

6. Examples

In this part, we exhibit two examples which showcase the results of this paper. They illustrate the computational gains that are made with respect to determining the recurrent configurations on a graph that can be decomposed in the terms we have described.

Example 6.1. Let G be the graph in Figure 12. Let us consider the sandpile model on G wherein vertex v_{0} is the sink. Apply Theorem 3.9 to this graph. The cv-tree (T, 0) structure of G is illustrated in Figure 13. The constituent graphs of the cv-tree are

H_{i} = \begin{cases}G_{[\{v_{i},v_{4i+1},v_{4i+2},v_{4i+3},v_{4i+4}\}]} & if 0 ≤ i ≤ 4 \\ G_{[\{v_{i},v_{3i+6},v_{3i+7},v_{3i+8}\}]} & if 5 ≤ i ≤ 20, \end{cases}

and nodes (T) = {0, 1, …, 20}. Note that H_{i} is isomorphic to K_{5} (respectively K_{4}) for all i ≤ 4 (respectively 5 ≤ i ≤ 20). The recurrent states of the sandpile model on these graphs are therefore characterized by Theorem 1.7.

Theorem 3.9 tells us that c = (c_{1}, …, c_{68}) ∈ Rec_{v_{0}} (G) if, and only if, c^{(t)} ∈ Rec_{v_{t}} (H_{t}) for all 0 ≤ t ≤ 20. This latter condition is equivalent to:

\begin{cases}(c_{4i+1}^{(i)}, c_{4i+2}^{(i)}, c_{4i+3}^{(i)}, c_{4i+4}^{(i)}) ∈ Rec_{v_{0}} (K_{5}) & for all 0 ≤ i ≤ 4 \\ (c_{3i+6}^{(i)}, c_{3i+7}^{(i)}, c_{3i+8}^{(i)}) ∈ Rec_{v_{0}} (K_{4}) & for all 5 ≤ i ≤ 20. \end{cases}

The set Rec_{v_{0}} (K_{4}) is explicitly listed in Equation (9), and the set Rec_{v_{0}} (K_{5}) is described in Example 1.9.

Now since d^{H_{i}}(v_{i}) = 4 for 1 ≤ i ≤ 4, and d^{H_{i}}(v_{i}) = 3 for all 5 ≤ i ≤ 20, we may conclude with our classification of recurrent states of the sandpile model on G: c ∈ Rec_{v_{0}} (G) if and only if (i) (c_{1} − 4, c_{2} − 4, c_{3} − 4, c_{4} − 4) ∈ Rec_{v_{0}} (K_{5}), (ii) (c_{4i+1} − 3, c_{4i+2} − 3, c_{4i+3} − 3, c_{4i+4} − 3) ∈ Rec_{v_{0}} (K_{5}) for all 1 ≤ i ≤ 4, and (iii) (c_{3i+6}, c_{3i+7}, c_{3i+8}) ∈ Rec_{v_{0}} (K_{4}) for all 5 ≤ i ≤ 20. We may also compute the level polynomial for the graph G of Figure 12. By Corollary 3.10,

we have:

Level_{G,v_{0}} (x) = Level_{K_{5},v_{0}} (x)^{5} Level_{K_{4},v_{0}} (x)^{16} .

The level polynomials of the complete graphs can be computed for instance by computing their Tutte polynomials and applying Theorem 1.3. We get

Level_{K_{4},v_{0}} (x) = x^{3} + 3x^{2} + 6x + 6
Level_{K_{5},v_{0}} (x) = x^{6} + 4x^{5} + 10x^{4} + 20x^{3} + 30x^{2} + 36x + 24,

and thus

Level_{G,v_{0}} (x) = (x^{6} + 4x^{5} + 10x^{4} + 20x^{3} + 30x^{2} + 36x + 24)^{5}(x^{3} + 3x^{2} + 6x + 6)^{16}
= x^{78} + 68x^{77} + 2346x^{76} + … + 22463437455746924544.

In other words, there is one recurrent configuration with level 78, 68 recurrent configurations with level 77, and so on.

Example 6.2. Let G be the graph in Figure 14. Let us consider the sandpile model on G wherein vertex v_{0} is the sink. We apply Theorems 3.9 and 4.1 to this graph. The cv-tree (T, 0) structure of G and its constituent graphs are illustrated in Figure 15, where H_{0} and H_{1} are connected by an isthmus. Note that H_{0} and H_{2} are isomorphic to K_{5}, H_{3} is isomorphic to K_{4}^{(2)}, that is K_{4} with all edges doubled, and that H_{1} is a graph whose recurrent configurations have already been determined in Example 3.6.

Theorems 3.9 and 4.1 tell us that c = (c_{1}, …, c_{14}) ∈ Rec_{v_{0}} (G) if, and only if, c^{(t)} ∈ Rec_{v_{t}} (H_{t}) for all 0 ≤ t ≤ 3, and c_{5} = 3, since v_{5} is the vertex of the isthmus (v_{3}, v_{5}) “furthest” from the sink, and has degree four. This latter condition is equivalent to:

• (c_{1}^{(0)}, c_{2}^{(0)}, c_{3}^{(0)}, c_{4}^{(0)}), (c_{8}^{(2)}, c_{9}^{(2)}, c_{10}^{(2)}, c_{11}^{(2)}) ∈ Rec_{v_{0}} (K_{5})  (20)
• c_{5} = 3  (21)
• (c_{6}^{(1)}, c_{7}^{(1)}) ∈ Rec_{v_{5}} (H_{1})  (22)
• (c_{12}^{(3)}, c_{14}^{(3)}, c_{15}^{(3)}) ∈ Rec_{v_{0}} (K_{4}^{(2)}) .  (23)

The set Rec_{v_{0}} (K_{5}) is described in Example 1.9. Since d^{H_{1}}(v_{3}) = 1 and d^{H_{3}}(v_{4}) = 6, Equation (20) is equivalent to:

(c_{1}, c_{2}, c_{3} − 1, c_{4} − 6), (c_{8}, c_{9}, c_{10}, c_{11}) ∈ Rec_{v_{0}} (K_{5}) .

We have already computed the recurrent configurations of the component H_{1} in Example 3.6, so Rec_{v_{5}} (H_{1}) = {(0, 1), (1, 0), (1, 1), (2, 0), (2, 1)}. Since d^{H_{2}}(v_{7}) = 4, Equation (22) is equivalent to:

(c_{6}, c_{7} − 4) ∈ Rec_{v_{5}} (H_{1}) .

\begin{matrix}v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \\ v_{7} \\ v_{8} \\ v_{9} \\ v_{12} \\ v_{10} \\ v_{11} \\ v_{13} \\ v_{16} \\ v_{14} \\ v_{15} \\ v_{17} \\ v_{20} \\ v_{18} \\ v_{19} \\ v_{21} \\ v_{22} \\ v_{23} \\ v_{33} \\ v_{34} \\ v_{35} \\ v_{45} \\ v_{46} \\ v_{47} \\ v_{57} \\ v_{58} \\ v_{59} \\ v_{30} \\ v_{31} \\ v_{32} \\ v_{42} \\ v_{43} \\ v_{44} \\ v_{54} \\ v_{55} \\ v_{56} \\ v_{66} \\ v_{67} \\ v_{68} \\ v_{24} \\ v_{25} \\ v_{26} \\ v_{36} \\ v_{37} \\ v_{38} \\ v_{48} \\ v_{49} \\ v_{50} \\ v_{60} \\ v_{61} \\ v_{62} \\ v_{27} \\ v_{28} \\ v_{29} \\ v_{39} \\ v_{40} \\ v_{41} \\ v_{51} \\ v_{52} \\ v_{53} \\ v_{63} \\ v_{64} \\ v_{65} \end{matrix}

Figure 12. The graph used in Example 6.1.

Finally, the set Rec_{v_{0}} (K_{4}) is explicitly listed in Equation 9. The recurrent states of K_{4}^{(2)} are linked to those of K_{4} by Theorem 2.1, so that Equation (23) is equivalent to:

(⌊c_{12}/2⌋, ⌊c_{13}/2⌋, ⌊c_{14}/2⌋) ∈ Rec_{v_{0}} (K_{4}) .

Combining all this, we may conclude with our classification of recurrent states of the sandpile model on G: c ∈ Rec_{v_{0}} (G) if and only if

• (c_{1}, c_{2}, c_{3} − 1, c_{4} − 6), (c_{8}, c_{9}, c_{10}, c_{11}) ∈ Rec_{v_{0}} (K_{5}),

• c_{5} = 3,

• (c_{6}, c_{7} − 4) ∈ Rec_{v_{5}} (H_{1}), and

• (⌊c_{12}/2⌋, ⌊c_{13}/2⌋, ⌊c_{14}/2⌋) ∈ Rec_{v_{0}} (K_{4}).

0 1 2 3 4 5 9 13 17 6 10 14 18 7 11 15 19 8 12 16 20

Figure 13. The cv-tree (T, 0) of the graph G in Figure 12 and Example 6.1.

\begin{matrix}v_{0} \\ v_{1} \\ v_{4} \\ v_{2} \\ v_{3} \\ v_{5} \\ v_{6} \\ v_{7} \\ v_{11} \\ v_{10} \\ v_{9} \\ v_{8} \\ v_{13} \\ v_{12} \\ v_{14} \end{matrix}

Figure 14. A graph G that can be decomposed as previously described.

References

[1] J.-C. Aval, M. D’Adderio, M. Dukes, A. Hicks, and Y. Le Borgne. Statistics on parallelogram polyominoes and a q, t-analogue of the Narayana numbers. J. Comb. Theory Ser. A 123(1):271–286, 2014.

[2] J.-C. Aval, M. D’Adderio, M. Dukes, and Y. Le Borgne. Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma. Adv. Appl. Math. 73:59–98, 2016.

[3] M. Baker and S. Norine. Riemann–Roch and Abel–Jacobi theory on a finite graph. Adv. Math. 215(2):766–788, 2007.

[4] A. Berget, A. Manion, M. Maxwell, A. Potechin, and V. Reiner. The critical group of a line graph. Ann. Combin. 16:449–488, 2012.

[5] O. Bernardi. Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings. Electron. J. Comb. 15(1):#R109, 53 pp., 2008.

0 1 2 3

(a) The cv-tree structure of the graph in Figure 14.

v_{0}/v_{7} v_{1}/v_{11} v_{4}/v_{10} v_{2}/v_{9} v_{3}/v_{8} H_{0} ≅ H_{2} ≅ K_{5} v_{5} v_{6} v_{7} H_{1} v_{4} v_{13} v_{12} v_{14} H_{3} ≅ K_{4}^{(2)}

(b) The constituent graphs of the cv-tree for Figure 14. In the pentagram on the left, graph H_{0} consists of those labels to the left of the ‘/’ and graph H_{2} consists of those labels to the right of ‘/’. Both are isomorphic to K_{5}.

Figure 15. Decomposition of the graph G from Figure 14.

[6] N. Biggs. The Tutte Polynomial as a Growth Function. J. Algebraic Combin. 10(2):115–133, 1999.

[7] K. Brown. Cohomology of groups, volume 87 of Graduate Texts in Mathematics. Springer-Verlag, New York-Berlin, 1982.

[8] R. Cori and Y. Le Borgne. The sand-pile model and Tutte polynomials. Adv. Appl. Math. 30(1-2):44–52, 2003.

[9] R. Cori and D. Poulalhon. Enumeration of (p, q)-parking functions. Discrete Math. 256(3):609–623, 2002. LaCIM 2000 Conference on Combinatorics, Computer Science and Applications.

[10] R. Cori and D. Rossin. On the sandpile group of a graph. Eur. J. Combin. 21:447–459, 2000.

[11] D. Dhar. Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64:1613–1616, 1990.

[12] D. Dhar. Theoretical studies of self-organized criticality. Phys. A 369(1):29–70, 2006.

[13] M. Dukes and Y. Le Borgne. Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a q, t-Narayana polynomial. J. Comb. Theory Ser. A 120(4):816–842, 2013.

[14] C. Greene and T. Zaslavsky. On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Amer. Math. Soc. 280(1):97–126, 1983.

[15] B. Jacobson, A. Niedermaier, and V. Reiner. Critical groups for complete multipartite graphs and Cartesian products of complete graphs. J. Graph Theory 44:231–250, 2003.

[16] L. Levine. Sandpile groups and spanning trees of directed line graphs. J. Combin. Theory Ser. A 118(2):350–364, 2011.

[17] D. Lorenzini. A finite group attached to the laplacian of a graph. Discrete Math. 91:277–282, 1991.

[18] C. Merino. Chip firing and the Tutte polynomial. Ann. Comb. 1(1):253–259, 1997.

[19] F. Redig. Mathematical aspects of the Abelian sandpile model. Lecture Notes of Les Houches Summer School 2005, Mathematical Statistical Physics, Session LXXXIII. Elsevier, 2006.

[20] K. Sekine and C.Q. Zhang. Decomposition of the Flow Polynomial. Graphs Combin. 13(2):189–196, 1997.

[21] W.T. Tutte. A contribution to the theory of chromatic polynomials. Can. J. Math. 6:80–91, 1954.

School of Mathematics and Statistics, University College Dublin, Dublin 4, Ireland.

Department of Computer and Information Sciences, University of Strathclyde, Glasgow, G1 1XH, UK