# Burning and duality

## 7.3. Superstables and recurrents

Let $c \in \text{Config}(G)$. Then *script-firing* by the script $\sigma$ results in the configuration $c' = c - \tilde{L} \sigma$. If $c$ is a sandpile, we say the script-firing is *legal* for $c$ if $c' \geq 0$; in other words, after the script is fired, no vertices have a negative amount of sand. Note that this is weaker than our earlier notion of a firing script arising from a legal sequence of vertex firings: a firing script is legal for $c$ provided that the final configuration is a sandpile—there may be no legal sequence of firings that implements the script. We say a sandpile $c$ has *no legal script-firings* if there is no firing script $\sigma \gneq 0$ that is legal for $c$.

**Definition 7.10.** A sandpile $c$ is *superstable* if it has no legal script-firings.

**Exercise 7.11.** Give an example of a stable sandpile that is not superstable.


**Theorem 7.12.** The following are equivalent for a sandpile $c$ :
1. $c$ is recurrent
2. $c_{\text{max}} - c$ is superstable
3. $c + \tilde{L}\sigma$ is unstable for all $\sigma \gneq 0$
4. $c + \tilde{L}\sigma$ is unstable for all $0 \lneq \sigma \leq \sigma_\textbf{b}$

> If $b$ is a burning sandpile, we call $\sigma_\textbf{b} := \tilde{L}^{-1}b$ its *(burning) script*.

**Remark 7.13.** Theorem 7.12 implies a duality between recurrents and superstables: $$\text{$c$ is recurrent if and only if $c_{\text{max}} - c$ is superstable}$$ Note that it easily follows that $c$ is superstable if and only if $c_{\text{max}} - c$ is recurrent, as well.

**Examples.** 

In diamond graph,

| recurrents | (0,2,1) | (1,2,0) | (1,2,1) | (2,0,1) | (2,1,0) | (2,1,1) | (2,2,0) | (2,2,1) |
|:------------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
| superstables | (2,0,0) | (1,0,1) | (1,0,0) | (0,2,0) | (0,1,1) | (0,1,0) | (0,0,1) | (0,0,0) |

**Lemma 7.14.** If $\tilde{L}\sigma \geq 0$, then $\sigma \geq 0$.
> $$
\tilde{L}_{ij} =
\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}
$$

**Proof.** Suppose $\tilde{L}\sigma \geq 0$. Let $N := \{v \in \tilde{V} : \sigma(v) < 0\}$ and assume that $N \not= \emptyset$.
Since $\tilde{L}$ is nonpositive off the diagonal and $\sigma(w) \geq 0$ for $w \notin N$,
\begin{align*}
0 \leq \sum_{v\in N} (\tilde{L}\sigma)(v) &= \sum_{v\in N} \sum_{w\in \tilde{V}} \tilde{L}_{vw} \sigma(w) \\\\
&= \sum_{v\in N} \sum_{w\in N} \tilde{L}_{vw} \sigma(w) + \sum_{v\in N} \sum_{w\notin N} \tilde{L}_{vw} \sigma(w)\\\\
&\leq \sum_{v\in N} \sum_{w\in N} \tilde{L}_{vw} \sigma(w) \\\\
&= \sum_{w\in N} \left(\sum_{v\in N} \tilde{L}_{vw}\right) \sigma(w).
\end{align*}

However, since the sum of the elements in any column of $\tilde{L}$ is nonnegative and positive elements occur only along the diagonal, if $w \in N$, then $\sum_{v\in N} \tilde{L}_{vw} \geq 0$. So the above calculation implies that $\sum_{v\in N} \tilde{L}_{vw} = 0$ for all $w \in N$. It follows that no vertex in $N$ is connected to a vertex not in $N$, including the sink vertex. Since $s$ is globally accessible in $G$, this is a contradiction. So we must have $N = \emptyset. \quad \square$

**Proof of Theorem 7.12.**
> 1. $c$ is recurrent
> 2. $c_{\text{max}} - c$ is superstable
> 3. $c + \tilde{L}\sigma$ is unstable for all $\sigma \gneq 0$
> 4. $c + \tilde{L}\sigma$ is unstable for all $0 \lneq \sigma \leq \sigma_\textbf{b}$

**[(1) $\Rightarrow$ (2)]** Suppose that $c$ is recurrent, and for the sake of contradiction, suppose that $c_{\text{max}} - c$ is not superstable. Then there exists $\sigma \gneq 0$ such that $c_{\text{max}} - c - \tilde{L}\sigma \geq 0$. By the definition of recurrent, there exists a sandpile $m \geq c_{\text{max}}$ such that $m \rightsquigarrow (m)^\circ=c$. Letting $\tau$ be the corresponding firing script, we have $$0 \leq c_{\text{max}} - c - \tilde{L}\sigma = c_{\text{max}} - (m - \tilde{L}\tau) - \tilde{L}\sigma = c_{\text{max}} - m + \tilde{L}(\tau - \sigma)$$ It follows that $\tilde{L}(\tau - \sigma) \geq m - c_{\text{max}} \geq 0$, and hence, by Lemma 7.14, $\tau - \sigma \geq 0$. Moreover, we see that $c_{\text{max}} \geq m - \tilde{L}(\tau - \sigma)$, so $m - \tilde{L}(\tau - \sigma)$ is stable. By the [least action principle (Theorem 6.7)](https://hackmd.io/@wen117/0628), we have $\tau - \sigma \geq \tau$, yielding $\sigma \leq 0$, a contradiction. $\quad \square$

**[(2) $\Rightarrow$ (3)]** If $c_{\text{max}} - c$ is superstable and $\sigma \gneq 0$, then firing $\sigma$ must produce a negative vertex: $(c_{\text{max}} - c - \tilde{L}\sigma)(v) < 0$ for some $v \in \tilde{V}$. It follows that $c_{\text{max}}(v) < (c + \tilde{L}\sigma)(v)$; so $v$ is unstable in $c + \tilde{L}\sigma. \quad \square$

**[(3) $\Rightarrow$ (4)]** Obvious. $\quad \square$

**[(4) $\Rightarrow$ (1)]** Suppose $c + \tilde{L}\sigma$ is unstable for all $0 \lneq \sigma \leq \sigma_\textbf{b}$ and $c$ is a nonrecurrent sandpile. Let $\textbf{b}$ be the burning sandpile for $G$ with burning script $\sigma_\textbf{b}$. Let $v_1, \ldots, v_k$ be a legal firing sequence that stabilizes $c + \textbf{b}$:
$$c + \textbf{b} \overset{v_1,\cdots,v_k}{\longrightarrow} (c + \textbf{b})^\circ$$ Then $\sigma := \sum_{i=1}^k v_i \not= \sigma_\textbf{b}$ since $c$ is not recurrent by [Theorem7.5 (3)](https://hackmd.io/@wen117/0702). Define $\tau := \sigma_\textbf{b} - \sigma$, and note that $0 \lneq \tau \leq \sigma_\textbf{b}$ by [Theorem7.5 (5)](https://hackmd.io/@wen117/0702). However, \begin{split}
c + \tilde{L}\tau &=c + \tilde{L}(\sigma_\textbf{b} - \sigma)\\\\ &= c + \tilde{L}\sigma_\textbf{b} - \tilde{L}\sigma \\\\ &=c + \textbf{b} - \tilde{L}\sigma \\\\&= (c + \textbf{b})^\circ
\end{split} which has no unstable vertices. $\quad \square$

---

## 7.4. Forbidden subconfigurations

It is sometimes possible to determine that a configuration is not recurrent by looking locally. For instance, Figure 2 displays a portion of a configuration $c$ on an undirected graph. We will see shortly that simply by looking at this portion of $c$, one can tell it is not recurrent.

$\quad$
Let $G = (V, E, s)$ be a sandpile graph with sink $s$.

**Definition 7.16.** Let $c$ be a configuration on $G$ and let $W$ be a nonempty subset of $\tilde{V}$. The *subconfiguration* of $c$ corresponding to $W$ is
$$c|_W := \sum_{w\in W} c(w) w$$ The subconfiguration $c|_W$ is a *forbidden subconfiguration (FSC)* if
$$c(v) < \text{indeg}_W(v) := | \{w \in W : (w, v) \in E\} |$$ for all $v \in W$.

$\quad$
**Proposition 7.17.** If $c$ is recurrent, then it has no FSC.
$\quad$

**Example 7.18.** The set $W = \{u, v, w\}$ is an FSC for the configuration pictured in Figure 2. Hence, the configuration cannot be recurrent.

$\quad$
**Example 7.19.** There is no converse to Proposition 7.17 for directed graphs, in general. For instance, consider the graph in Figure 3 with sink $s$ and edge $(u, v)$ of multiplicity 2. The configuration $c = 1 \cdot u + 0 \cdot v$ is stable, is not recurrent, and has no FSC.

$\quad$
**Theorem 7.20.** Let $G = (V, E, s)$ be a sandpile graph with no selfish vertices. Then a stable sandpile on $G$ is recurrent if and only if it has no forbidden subconfigurations.
> **Definition 7.2.** A vertex $v \in \tilde{V} = V \setminus \{s\}$ is *selfish* if $\text{indeg}_{\tilde{V}}(v) > \text{outdeg}(v)$.

---