## Code for experiment

Pick a vertex of $G$ at random; drop a grain of sand on that vertex and stabilize the resulting sandpile; repeat until 100 grains of sand have been dropped. The results from ten trials of this experiment are shown in Table 1.


* 4 trials, 100000 grains of sand

import random
from collections import defaultdict

# Define the graph
class Graph:
    def __init__(self):
        self.adjacency_list = {
            'v1': ['v2', 'v3', 's'],
            'v2': ['v1', 'v3', 's'],
            'v3': ['v1', 'v2'],
            's': ['v1', 'v2']
        }
        self.sandpile = {v: 0 for v in self.adjacency_list}
        self.configurations = []

    def add_sand(self, vertex):
        self.sandpile[vertex] += 1
        self.stabilize()
        self.record_configuration()

    def stabilize(self):
        unstable = [v for v, grains in self.sandpile.items() if grains >= len(self.adjacency_list[v])]
        while unstable:
            vertex = unstable.pop()
            grains = self.sandpile[vertex]
            self.sandpile[vertex] -= len(self.adjacency_list[vertex])
            for neighbor in self.adjacency_list[vertex]:
                if neighbor != 's':
                    self.sandpile[neighbor] += 1
                    if self.sandpile[neighbor] == len(self.adjacency_list[neighbor]):
                        unstable.append(neighbor)

    def record_configuration(self):
        config = tuple(self.sandpile[v] for v in sorted(self.sandpile) if v != 's')
        self.configurations.append(config)

    def experiment(self, n_drops):
        for _ in range(n_drops):
            vertex = random.choice(list(self.adjacency_list.keys())[:-1])
            self.add_sand(vertex)
        return self.sandpile, self.configurations

    def count_configurations(self):
        config_counts = defaultdict(int)
        for config in self.configurations:
            config_counts[config] += 1
        return config_counts

# Perform the experiment
graph = Graph()
final_sandpile, configurations = graph.experiment(100000)
config_counts = graph.count_configurations()

# Print the final sandpile configuration
print("Final sandpile configuration:", final_sandpile)

# Print all configurations and their counts
print("Configurations and their counts:")
for config, count in config_counts.items():
    print(f"{config}: {count} times")

# Specific configurations to check
specific_configs = [
    (2, 1, 0), (2, 1, 1), (2, 0, 1), (2, 2, 0),
    (0, 2, 1), (1, 2, 1), (1, 2, 0), (2, 2, 1)
]

# Calculate and print the proportions of the specific configurations
total_configurations = len(configurations)
print("\nSpecific configurations and their proportions:")
for config in specific_configs:
    count = config_counts[config]
    proportion = count / total_configurations
    print(f"{config}: {count} times, proportion: {proportion:.2%}")

---

## Diamond graph：Stable & Unique

* **Stable**
(Induction on $\text{deg}(c)$)
It is easy to check for any sandpile $c$ with $\text{deg}(c) \le 6$ will, through repeated firings, eventually stabilize.
Suppose any initial sandpile $c$ on $G$ with $\text{deg}(c) = k \ge 6$ will stabilize. Then for a sandpile $c'$ with $\text{deg}(c')=k+1$, if $v_1$ is unstable (similar for $v_2$), fire it we have a sandpile of degree $k$, which will stabilize by hypothesis. Hence we wish all $k$ sand on $v_3$, but by firing $v_3$ three times, $v_1$ is unstable, which leads to the same condition as before.

* **Unique**
When $v_1, v_2$ are unstable, $$(a, b, c) \stackrel{v_1}\rightsquigarrow (a-3, b+1, c+1) \stackrel{v_2}\rightsquigarrow (a-2, b-2, c+2)$$ $$(a, b, c) \stackrel{v_2}\rightsquigarrow (a+1, b-3, c+1) \stackrel{v_1}\rightsquigarrow (a-2, b-2, c+2)$$ When $v_1, v_3$ are unstable, $$(a, b, c) \stackrel{v_1}\rightsquigarrow (a-3, b+1, c+1) \stackrel{v_3}\rightsquigarrow (a-2, b+2, c-1)$$ $$(a, b, c) \stackrel{v_3}\rightsquigarrow (a+1, b+1, c-2) \stackrel{v_1}\rightsquigarrow (a-2, b+2, c-1)$$ When $v_2, v_3$ are unstable, same as the condition for $v_1, v_3$. Hence the choice of ordering in which to fire unstable vertices has no effect on the eventual stabilization of a sandpile.

---

## 6.3. Sandpile graphs

### 6.3.1. Vertex firing

Let $c$ be a configuration on $G$, and let $v \in \tilde{V}$. Firing or toppling $v$ from $c$ produces a new configuration $c'$ by the rule
$$
c' = c - \text{outdeg}(v) v + \sum_{vw \in E:w \neq s} w
$$ and we write
$$
c \stackrel{v}\to c'
$$

We think of firing $v$ as sending one grain of sand along each of the edges emanating from $v$. If the head of $e$ happens to be the sink vertex, then that sand disappears. A vertex $v \in \tilde{V}$ is stable in the configuration $c$ if $c(v) < \text{outdeg}(v)$; otherwise, it is unstable. If each vertex is stable in $c$, then $c$ is stable; otherwise, it is unstable.

If $v$ is unstable in $c$, we say that firing $v$ is legal for $c$; this means that the amount of sand on $v$ after firing $v$ would be nonnegative. We use a jagged arrow to emphasize the legality of a vertex firing, writing $c \stackrel{v}\rightsquigarrow c'$. Firing a sequence of non-sink vertices $v_1, \ldots, v_k$ from $c = c^{(1)}$ produces a sequence of configurations $$ c^{(1)} \stackrel{v_1}\to c^{(2)} \stackrel{v_2}\to \cdots \stackrel{v_k}\to c^{(k)} $$ We say $v_1, \ldots, v_k$ is a legal firing sequence for $c$ if firing $v_i$ from $c^{(i)}$ is legal for all $i$.

If $c'$ is reached from $c$ after a sequence $\sigma = v_1, \cdots, v_k$ of vertex firings, we write
$$
c \stackrel{\sigma}\to c'
$$ sometimes omitting the label, $\sigma$. If $\sigma$ is a legal firing sequence, we may write $c \stackrel{\sigma}\rightsquigarrow c'$. Further, if $c'$ is stable, it is called a stabilization of $c$. As a consequence of the least action principle described below, we shall see that every configuration has a unique stabilization. So we can speak of the stabilization of a configuration $c$, denoted $c^\circ$.

If $c, c' \in \text{Config}(G)$, then $c'$ is obtained from $c$ by firing vertex $v$ if and only if $c$ is obtained from $c'$ through a reverse-firing of $v$. More generally, a mix of vertex firings and reverse-firings constitutes a firing script, $\sigma: \tilde{V} \to \mathbb{Z}$.

A sequence of vertex firings and reverse-firings determines a firing script, although a given firing script will generally arise from many different sequences. Just as in Part 1, the configuration resulting from a sequence of vertex firings is independent of the ordering of the sequence, since these firings just involve addition and subtraction in the abelian group $\text{Config}(G)$. So we have the abelian property for vertex firing just as we did for divisors in Part 1: if $c \in \text{Config}(G)$ and $v, w \in \tilde{V}$, then there is a commutative diagram:
Further, if $v$ and $w$ are both unstable in $c$, then both firing sequences, $$c \stackrel{v}\to c' \stackrel{w}\to c''' \ \text{ and } \ c \stackrel{w}\to c'' \stackrel{v}\to c'''$$ are legal. That's because firing a vertex never removes sand from another vertex and hence can never stabilize another vertex. Nevertheless, not all rearrangements of a legal firing sequence will be legal.

It turns out that legal firing sequences are distinguished by an efficiency property with respect to stabilization──this is the least action principle described in the next section.

---

### 6.3.2 Least action principle
Figure 8 depicts a sequence of vertex firings on the triangle graph


The vertex $v_1$ is legal for $c$, and firing it produces the stable configuration $c'$. But note that the non-legal firing sequence $v_1, v_1, v_2$ transforms $c$ into the zero configuration, $\tilde{c} = 0$, which is also stable. This example shows that, in general, there may be many stable configurations reachable from a given configuration through a sequence of vertex firings. However, the following theorem shows that, just as in this example, the shortest sequence leading to a stable configuration will be legal.

**Theorem 6.7** (Least action principle)**.** Let $c \in \text{Config}(G)$, and suppose $\sigma, \tau \geq 0$ are firing scripts such that $\sigma$ arises from a legal firing sequence for $c$ and $c \stackrel{\tau}\to \tilde{c}$ with $\tilde{c}$ stable. Then $\sigma \leq \tau$.

**Proof.** Let $v_1,\cdots,v_k$ be a legal firing sequence corresponding to $\sigma$. The proof goes by induction on $k$, with the base case $k = 0$ being obvious. Suppose $k>0$. Since $v_1$ is unstable in $c$, the only way that $v_1$ could be stable in $\tilde{c}$ is if it fired at least once according to $\tau$. Fire $v_1$ to get a configuration $c'$, and let $\tau' := \tau - v_1$. Then $v_2,\ldots,v_k$ is a legal firing sequence for $c'$, and $c' \stackrel{\tau'}\to \tilde{c}$.
By induction, $\sigma - v_1 \leq \tau'$, and the result follows:
$$\sigma \leq \tau' + v_1 = \tau. \quad \square$$
**Corollary 6.8** (Uniqueness of stabilization)**.** Let $c$ be a configuration and $\sigma,\sigma' \geq 0$ firing scripts corresponding to legal firing sequences for $c$. Suppose that $c \stackrel{\sigma}\rightsquigarrow \tilde{c}$ and $c \stackrel{\sigma'}\rightsquigarrow \tilde{c}'$, with $\tilde{c}$ and $\tilde{c}'$ both stable. Then $\sigma = \sigma'$ and $\tilde{c} = \tilde{c}'$.

---

### 6.3.3. Existence of stabilizations

The previous corollary shows that stabilizations, if they exist, are unique. In this section, we show existence: every configuration can be transformed into a stable configuration through a sequence of legal vertex firings.

To do this we define an order relation on $\mathbb{Z} \tilde {V}$ in which first, a configuration is judged to be large if it has lots of sand, and second, in the case of two configurations with the same amount of sand, the smaller is the one with more sand near the sink.

**Definition 6.9.** Let $u_1, \ldots, u_n$ be an ordering of the non-sink vertices of $G$ such that $i < j$ if $d(u_i, s) < d(u_j, s)$, i.e., if $u_i$ is closer to the sink. The sandpile ordering of $\text{Config}(G) = \mathbb{Z} \tilde {V}$ is the total ordering $\prec$ defined as follows. Given distinct configurations $a, b$, let $c := a - b = \sum_{i=1}^n c_i u_i$. Then $a \prec b$ if
1. $\deg(a) < \deg(b)$, or
1. $\deg(a) = \deg(b)$ and $c_k > 0$ for the smallest $k$ such that $c_k \neq 0$.

Given a sandpile ordering $\prec$, we employ the usual conventions: writing $a \preceq b$ means $a = b$ or $a \prec b$; writing $a \succ b$ means $b \prec a$; and so on. In particular, $u_1 \prec \cdots \prec u_n$.

**Exercise 6.10.** If $c$ is a configuration with $0 \leq c$, then $0 \preceq c$, and there are only finitely many configurations $c'$ such that $0 \leq c'$ and $c' \preceq c$.

**Proof.** If $0 \leq c'$ and $c' \preceq c$, then $0 \le \deg(c') \le \deg(c)$. Since the ways to pile the $\deg(c')$ sand on vertices is finite, then it follows that there are only finitely many configurations $c'. \ \square$

**Lemma 6.11.** Let $\prec$ be a sandpile ordering, and let $c, \tilde{c} \in \mathbb{Z} \tilde {V}$. If $c \to \tilde{c}$ via a sequence of vertex firings, then $\tilde{c} \prec c$.

**Proof.** We may assume that $c \stackrel{v}\to \tilde{c}$ for some vertex $v$. If $(v, s) \in E$, then when $v$ fires, some sand is lost to the sink. So in that case $\tilde{c} \prec c$ since $\deg(\tilde{c}) < \deg(c)$. Otherwise, since the sink is globally accessible, there exists $(v, u) \in E$ for some vertex $u$ closer to the sink than $v$. When $v$ fires, the vertex $u$ receives sand and no vertex besides $v$ loses sand. Hence, $\tilde{c} \prec c$ since $\tilde{c}$ has more sand closer to the sink. $\ \square$

**Theorem 6.12** (Existence)**.** Every configuration has a stabilization.

**Proof.** If $c$ is a sandpile, i.e., if $c \geq 0$, then the fact that $c$ has a stabilization follows immediately from Lemma 6.11 and Exercise 6.10.
Given an arbitrary configuration $c$, define the sandpile $c^+$ by
$$c^+(v) = \max \{0, c(v)\}$$

for each $v \in \tilde{V}$. We have just seen that $c^+$ is stabilizable. Further, by the least action principle, every legal firing sequence for $c^+$ is finite. Since every legal firing sequence for $c$ is also a legal firing sequence for $c^+$, it follows that $c$ has no infinite legal firing sequence, and is therefore stabilizable.

**Corollary 6.13.** Let $c$ be a configuration, and suppose $\sigma$ and $\tau$ are two legal firing sequences for $c$ resulting in the same configuration $\tilde{c}$ :
$$c \stackrel{\sigma}\rightsquigarrow \tilde{c} \ \text{ and } c \stackrel{\tau}\rightsquigarrow \tilde{c}$$

Then $\sigma$ and $\tau$ are rearrangements of each other.

**Proof.** By Theorem 6.12, there is a legal firing sequence $\mu$ stabilizing $\tilde{c}$. Then the concatenated sequences $\sigma, \mu$ and $\tau, \mu$ are both legal firing sequences stabilizing $c$. By Corollary 6.8 (unique), these two concatenated sequences are rearrangements of each other; therefore, the same holds for $\sigma$ and $\tau$.

---

## 6.4. The reduced Laplacian

Just as for the divisor-theory in Part 1, the theory of sandpiles is really the study of the reduced Laplacian $\tilde{L}$, which we now recall and extend to the context of directed sandpile graphs. If $\sigma : \tilde{V} \to \mathbb{Z}$ is any firing script, then the net effect of implementing $\sigma$ is to replace a configuration $c$ by a new configuration $c'$ given by

\begin{split}
c' &= c - \sum_{v\in \tilde{V}} \sigma(v) \left(\text{outdeg}(v) v - \sum_{vw\in E:w\neq s} w\right) \\\\ &=: c - \tilde{L}(\sigma)
\end{split}

where $\tilde{L} : \tilde{M}(G) \to \mathbb{Z}\tilde{V}$ is defined implicitly via the sum in the first line. Ordering the non-sink vertices, $\tilde{V} = \{v_1, \ldots, v_n\}$, identifies $\mathbb{Z}\tilde{V}$ with $\mathbb{Z}^n$ :
$$\sum_{i=1}^n c_i v_i \in \mathbb{Z}\tilde{V} \ \longleftrightarrow \ (c_1, \ldots, c_n) \in \mathbb{Z}^n$$

Consider the basis $\{\chi_1, \ldots, \chi_n\}$ for the group of firing scripts $\tilde{M}(G)$ that is dual to the basis $\{v_1, \ldots, v_n\}$ for $\mathbb{Z}\tilde{V}$:
$$\chi_j(v_i) := \begin{cases} 1 & \text{if } i = j \\ 0 & \text{otherwise} \end{cases}$$

Then in terms of the bases $\{\chi_j\}$ and $\{v_i\}$, the reduced Laplacian $\tilde{L}$ becomes an $n \times n$ integer matrix:

\begin{split}
\tilde{L}_{ij} = \tilde{L}(\chi_j)_i &=\left( \sum_{v\in \tilde{V}} \chi_j(v) \left(\text{outdeg}(v) v - \sum_{vw\in E:w\neq s} w\right) \right)_i \\ \\
&= \left(\text{outdeg}(v_j) v_j - \sum_{v_jw\in E:w\neq s} w \right)_i \\ \\
&=\begin{cases}
\text{outdeg}(v_i) - \#(\text{loops at } v_i) & \text{if } i = j \\
-(\# \text{edges from } v_j \text{ to } v_i) & \text{otherwise}
\end{cases}
\end{split}

**Example6.14.** The reduced Laplacian for the graph $G$ from Figure7, with vertex order $u, v$ is $$\tilde{L} = \begin{pmatrix}
6 & -3 \\
-5 & 5
\end{pmatrix}$$

**Definition 6.15.** The *Laplacian lattice* $\mathcal{L}$ and the *reduced Laplacian lattice* $\tilde{\mathcal{L}}$ are the subgroups formed by the images of the Laplacian and reduced Laplacian, respectively:
$$\mathcal{L} = \text{im } L \subseteq \mathbb{Z}V \quad \text{ and } \quad \tilde{\mathcal{L}} = \text{im } \tilde{L} \subseteq \mathbb{Z}\tilde{V}$$
In the context of the Laplacian, we will usually abuse notation and write the vertex $v$ when we really mean the firing script $\chi_v$. Thus, if $v \in \tilde{V}$, then
$$\tilde{L}v = \text{outdeg}(v) v - \sum_{vw\in E:w\neq s} w$$ As an immediate consequence of the above discussion, we have the following proposition and its corollary.

**Proposition 6.16.** The configuration $c'$ is obtained from the configuration $c$ by firing $v \in \tilde{V}$ if and only if $c' = c - \tilde{L}v$. Equivalently, $c$ is obtained from $c'$ by reverse-firing $v$ if and only if $c = c' + \tilde{L}v$.

**Corollary 6.17.** The configuration $c'$ is obtained from $c$ through a sequence of vertex firings and reverse-firings if and only if $$c = c' \mod \tilde{\mathcal{L}}$$

**Example 6.18.** Continuing with the graph from Figure 7 and Example 6.14 with vertex order $u, v, s$, consider the configuration $c = 2u + 7v = (2, 7)$. Fire vertex $v$:
$$c = (2, 7) \overset{v}{\to} (5, 2)$$

The corresponding calculation via Proposition 6.16 is
$$\begin{pmatrix} 5 \\ 2 \end{pmatrix} = \begin{pmatrix} 2 \\ 7 \end{pmatrix} - \begin{pmatrix} 6 & -3 \\ -5 & 5 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

### 6.4.1. Uniqueness of the firing script
**Proposition 6.19.** Let $c, c' \in \text{Config}(G)$ with $c = c' \mod \tilde{\mathcal{L}}$. Then there exists a unique firing script $\sigma$ such that $c \overset{\sigma}{\to} c'$.

**Proof.** The firing script is $\tilde{L}^{-1}(c - c'). \quad \square$

---

## 6.5. Recurrent sandpiles

In Section 6.1 we repeatedly dropped grains of sand onto randomly chosen vertices of a graph, one at a time, allowing the sandpile to stabilize after each added grain. We observed that some stable configurations appeared many times and others appeared at most once. In this section, we explain this phenomenon.

**Definition 6.20.** A configuration $c$ on $G$ is *recurrent* if
1. $c$ is a sandpile, i.e., $c \geq 0$,
1. $c$ is stable,
1. for every configuration $a$, there exists a configuration $b \geq 0$ such that $c = (a + b)^\circ$, the stabilization of $a + b$.

The collection of all recurrent elements of $G$—the recurrents of $G$—is denoted $S(G)$.

By the end of this section , the set of recurrents will be endowed with a group structure, and $S(G)$ will be used to denote this group.

Usually, it is not easy to explicitly describe the recurrent configurations of a graph. For instance, how would one have known, a priori, that the eight configurations in Figure 6 are recurrent? In general, there is only one recurrent configuration that is immediately recognizable: the maximal stable configuration.

**Definition 6.21.** The *maximal stable configuration* on $G$ is
$$c_{\text{max}} := \sum_{v\in \tilde{V}} (\text{outdeg}(v) - 1) v$$

It is clear that $c_{\text{max}}$ is stable and that $c_{\text{max}} \geq c$ for all stable configurations $c$. It is also not hard to see that $c_{\text{max}}$ is recurrent. Indeed, given any configuration $a$, let $b = c_{\text{max}} - a^\circ$. Let $\sigma$ be a legal firing sequence that stabilizes $a$. Then $b \geq 0$ and $\sigma$ is a legal firing sequence for $a + b$. But $(a + b) \overset{\sigma}{\to} (a^\circ + b) = c_{\text{max}}$, which shows that $(a + b)^\circ = c_{\text{max}}$. In fact, the following result shows that $c_{\text{max}}$ is the key to finding all the recurrent configurations.

**Proposition 6.22.** A configuration $c$ is recurrent if and only if there exists a configuration $b \geq 0$ such that $c = (c_{\text{max}} + b)^\circ$.

**Proof.** ($\Rightarrow$) Let $c$ be a recurrent configuration. Then by definition of recurrent, $c$ is stable and there exists a configuration $b\ge 0$ such that $c = (c_{\text{max}} + b)^\circ$.
($\Leftarrow$) Suppose there exists a $b \ge 0$ such that $c = (c_{\text{max}} + b)^\circ$. Let $a$ be any configuration such that $\sigma_a$ stabilizes $a$ and say $b'=c_{\text{max}}-a^\circ +b \ge0$. Then $$a+b' \stackrel{\sigma_a}\to a^\circ +b'=c_{\text{max}}+b$$ So $(a+b')^\circ=c. \quad \square$