Combinatorial aspects of sandpile models on wheel and fan graphs
Thomas Selig
Department of Computing, School of Advanced Technology, Xi'an Jiaotong-Livepool University

We study combinatorial aspects of the sandpile model on wheel and fan graphs, seeking bijective characterisations of the model's recurrent configurations on these families.
For wheel graphs, we exhibit a bijection between these recurrent configurations and the set of subgraphs of the cycle graph which maps the level of the configuration to the number of edges of the subgraph.
This bijection relies on two key ingredients. The first consists in considering a stochastic variant of the standard Abelian sandpile model (ASM), rather than the ASM itself. The second ingredient is a mapping from a given recurrent state to a canonical minimal recurrent state, exploiting similar ideas to previous studies of the ASM on complete bipartite graphs and Ferrers graphs.
We also show that on the wheel graph with $2n$ vertices, the number of recurrent states with level $n$ is given by the first differences of the central Delannoy numbers.
Finally, using similar tools, we exhibit a bijection between the set of recurrent configurations of the ASM on fan graphs and the set of subgraphs of the path graph containing the right-most vertex of the path. We show that these sets are also equinumerous with certain lattice paths, which we name Kimberling paths after the author of the corresponding entry in the Online Encyclopedia of Integer Sequences.

§ INTRODUCTION

The sandpile model is a dynamic process whereby grains of sand move around on a graph. Informally (a formal introduction is given in Section <ref>), grains of sand are placed on the vertices of the graph (we call this a configuration).
At each step of time, a vertex $v$ is chosen at random, and a grain of sand is added to $v$. If this causes the number of grains at $v$ to exceed a certain threshold (typically the degree of $v$), $v$ is said to be unstable, and topples, sending grains of sand to its neighbours according to some toppling rules.
This may cause other vertices to become unstable, and topple in turn. There is an exit point for the system called the sink vertex, which absorbs grains, and so the process eventually stabilises.
The dynamics of the sandpile model are given by this “add grain at random, and stabilise” operation.

In the classical so-called Abelian sandpile model (ASM), the toppling rules referred to above are simple (and deterministic): when a vertex topples, it sends one grain to each of its neighbours in the graph. Later in this section we will discuss stochastic variants of this model.
The ASM was originally introduced on 2-dimensional grids by Bak, Tang and Wiesenfeld in the 1980's [3, 4] as a model exhibiting a property known as self-organised criticality. This means that over time, a system will converge to a critical state without needing to fine-tune any of its external parameters.
The model was then generalised by Dhar [21], who showed the following Abelian property from which its name is derived. If $a_v$ denotes the operator “add a grain of sand at vertex $v$ and stablilise”, then the operators $(a_v)$ commute, i.e. $a_v a_w = a_w a_v$ for all vertices $v,w$.
In graph theory, the model is sometimes referred to as the chip-firing game (see e.g. [11]). For a recent extensive review of known results on this model, we refer the reader to Klivans's excellent book on the subject [31].

Of central importance in ASM research are the so-called recurrent configurations, those that appear infinitely often in the long-time running of the model (in chip-firing terminology, these are called critical configurations).
Dhar [21] showed that the set of recurrent configurations forms an Abelian group when equipped with the addition operation “vertex-pointwise addition and stablisation”. He named this the sandpile group of the graph.
This group, also known as the critical group, graph Jacobian, or Picard group, has been widely studied in algebraic graph and matroid theory. Its most celebrated contribution is perhaps its role in developing discrete Riemann-Roch and Abel-Jacobi theory on graphs [5].
The structure of the sandpile group has also been explicitly computed on a variety of graph families, including complete graphs [18], nearly-complete graphs (complete graphs with a cycle removed) [41], wheel graphs [9] (see also [35, 36]), Cayley graphs of the dihedral group $D_n$ [20], and many more (see e.g. [15] and the references therein for a more complete list).

In enumerative and bijective combinatorics, a fruitful direction of recent ASM research has also focused on graph families, but instead of looking at the sandpile group, the focus has been on calculating the set of recurrent configurations via bijections to other more easily enumerated or generated combinatorial objects.
Examples of graph families and related combinatorial objects are:

* complete graphs [18], corresponding to parking functions;

* complete multi-partite graphs with a dominating sink [17], corresponding to generalised parking functions (called $(p_1,\ldots,p_k)$-parking functions);

* complete bipartite graphs where the sink is in one of the two components [24], corresponding to (labelled) parallelogram polyominoes (see also [1, 2, 19]);

* complete split graphs [23], correspondences to the so-called tiered parking functions and Motzkin words;

* Ferrers graphs [26, 39], corresponding to (decorated) EW-tableaux (see Section <ref> for more details);

* permutation graphs [25], corresponding to tiered trees and non-ambiguous binary trees.

In this paper, we study combinatorial aspects (in the above sense) of the sandpile model on wheel and fan graphs.
We show that the recurrent configurations on these graphs are related to a variety of combinatorial objects: subgraphs of the cycle or path graphs, marked words/orientations, and two families of lattice paths known as Delannoy paths and Kimberling paths.
In the wheel graph case, to exhibit the desired correspondences, it is better to consider a stochastic variant of the standard ASM, where the toppling rules of unstable vertices are random.
In this model, instead of sending a grain to each neighbour, an unstable vertex chooses a random subset of neighbours to send grains to, and keeps the remaining grains.
There are a number of such stochastic sandpile models in the literature, although on the whole they have not been nearly as widely studied as the classical Abelian model.

* In [32], there are two different types of grain, which cannot occupy the same vertex. When they do, one of the grains is moved to a randomly chosen neighbouring vertex instead.

* In [37], unstable vertices lose all their grains, which are re-distributed at random to their neighbours: some neighbours may receive more than one grain, others none, while some grains may exit the system directly.

* In  [14], unstable vertices flip a coin for each neighbour to decide which neighbours to send grains to. That is, all neighbours independently of each other receive a grain with probability $p  \in (0,1)$ (with probability $(1-p)$ that grain is kept by the toppling vertex).

* The model in [34] essentially generalises the two previous models in [14, 37].

* In [30], the toppling threshold of a vertex is set to a (fixed) multiple $M$ of its degree. For each toppling, a random number $\gamma \in \{1,\ldots,M\}$ is chosen, and each neighbour of the toppling vertex receives the same (random) number $\gamma$ of grains.

The model that proves to be the most useful for our purposes here is the “coin-flipping” model [14] (see Section <ref> for a more formal definition of this model).

The paper is organised as follows. In Section <ref>, we formally introduce the sandpile models (Abelian and stochastic) on general graphs.
We give some important results on the sandpile model, specifically on characterisations of its recurrent configurations.
In Section <ref> we focus on the sandpile model on wheel graphs. Our main result is exhibiting a bijection between the set of recurrent configurations and the set of subgraphs of the cycle graph (Theorem <ref>).
In Section <ref> we focus on the specific case of wheel graphs with an even number of vertices, and show that the recurrent configurations whose total number of grains is one-and-a-half times the number of vertices are enumerated by the first differences of the so-called Delannoy numbers (Theorem <ref>).
In Section <ref>, we study the sandpile model on fan graphs. Our main results are that their recurrent configurations are in bijection with certain subgraphs of the path graph (Theorem <ref>), and are equinumerous with certain lattice paths (Theorem <ref>), which we call Kimberling paths after the name of their author in the OEIS [29].
Finally, Section <ref> summarises the main results of our papers, and gives some suggestions for future work.

§ PRELIMINARIES

In this section, we introduce some of the necessary definitions, tools and notation we will need and use throughout the rest of the paper. As usual, the sets $\Z$ and $\N$ denote the sets of integers and (strictly) positive integers respectively. We let $\Zp:=\N \, \cup \, \{0\}$ denote the set of non-negative integers. For a positive integer $n \in \N$, we denote $[n]$, resp. $[n]_0$, the set $\{1,\ldots,n\}$, resp. $\{0,\ldots,n\}$.

Throughout this section, a graph $G$ is a labelled, simple, undirected, connected graph with vertex set $V \subseteq [n]_0$ for some $n$. The edge set $E$ is therefore finite, and may not contain multiple edges or loops.
For $i \in V$, we write $\dgr[i] = \dgr[i]^G$ for the degree of the vertex $i$ in $G$, omitting the superscript where the underlying graph is unambiguous.
A subgraph of $G$ is a pair $(A, E_A)$ where $A$ is a non-empty subset of $V$, and $E_A$ a subset of $E$ containing only (some of the) edges with both endpoints in $A$. We write $\Sub[G]$ for the set of subgraphs of a graph $G$.

The path graph $P_n$ is the simple path graph with vertex set $[n]$, that is the edges are the pairs $\{i,i+1\}$ for $i \in [n-1]$.
The cycle graph $C_n$ is the simple cycle graph with vertex set $[n]$, obtained by adding an edge $\{n,1\}$ to $P_n$ to complete the cycle.
The wheel graph $W_n$ is constructed by taking the join of the cycle graph $C_n$ and of a single isolated vertex $0$ (that is, the vertex $0$ is connected to all vertices in $C_n$).
The fan graph $F_n$ is constructed by removing the edge $\{n,1\}$ from $W_n$, or equivalently by taking the join of the path graph $P_n$ and of a single isolated vertex.
We refer to vertex $0$ as the sink of $W_n$ and $F_n$. Figure <ref> shows an example of cycle, wheel and fan graphs, with the sink vertex represented as a square, and other vertices as circles.

[circle, draw=black] (1) at (0,2) $1$;
[circle, draw=black] (2) at (sqrt(3),1) $2$;
[circle, draw=black] (3) at (sqrt(3),-1) $3$;
[circle, draw=black] (4) at (0,-2) $4$;
[circle, draw=black] (5) at (-sqrt(3),-1) $5$;
[circle, draw=black] (6) at (-sqrt(3),1) $6$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(1);

[rectangle, draw=black] (0) at (0,0) $0$;
[circle, draw=black] (1) at (0,2) $1$;
[circle, draw=black] (2) at (sqrt(3),1) $2$;
[circle, draw=black] (3) at (sqrt(3),-1) $3$;
[circle, draw=black] (4) at (0,-2) $4$;
[circle, draw=black] (5) at (-sqrt(3),-1) $5$;
[circle, draw=black] (6) at (-sqrt(3),1) $6$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(1);
in 1,...,6
[thick] (0)–();

[rectangle, draw=black] (0) at (1.5,-1.5) $0$;
in 1,...,6
[circle, draw=black] () at (-2+,1.5) $\x$;
in 1,...,6
[thick] (0)–();
[thick] (1)–(2)–(3)–(4)–(5)–(6);

The cycle graph $C_6$ (top left), the wheel graph $W_6$ (top right), and the fan graph $F_6$ (bottom centre).

An orientation $\OO$ of the graph $G$ is the assignment of a direction to each edge in $E$. For an orientation $\OO$, and an edge $e=\{i,j\} \in E$, we write $i \orighta j$ to denote that the edge $e$ is directed from $i$ to $j$ in $\OO$. For $i \in V$, we denote $\In[i]$, resp. $\Out[i]$, the number of incoming, resp. outgoing, edges at $i$ in $\OO$.

An orientation is acyclic if it contains no directed cycles. A target, resp. source, of an orientation is a vertex where all edges are incoming, resp. outgoing[The terminology “sink” is more widespread in the literature than “target”, but the sandpile model already has a designated vertex called “sink”, hence our choice of terminology here.]. It is straightforward to verify that an acyclic orientation contains at least one target and one source. For a given vertex $i \in V$, an orientation is said to be $i$-rooted if the vertex $i$ is the orientation's unique target.

A $0$-rooted orientation of the wheel graph $W_n$ can be mapped straightforwardly to an orientation of the cycle graph $C_n$ by removing the sink $0$ and its incident edges. This correspondence is clearly one-to-one.
Similarly, we have a one-to-one correspondence between $0$-rooted orientations of the fan graph $F_n$ and orientations of the path graph $P_n$.

§.§ The Abelian sandpile model (ASM)

In this part we introduce the Abelian sandpile model (ASM) on a general graph $G$, and recall some important results regarding the so-called recurrent configurations of the model.
Let $G$ be a graph with vertex set $[n]_0$. As in the wheel and fan graph cases, we refer to $0$ as the sink of the graph.

A configuration on $G$ is a vector $c=(c_1,\ldots ,c_n) \in \Zp^n$ that assigns the number $c_i$ to vertex $i$.
We think of $c_i$ as representing the number of grains of sand at the vertex $i$.
Note that the sink vertex $0$ is not assigned a number of grains.
Denote by $\Config[G]$ the set of all configurations on $G$.
Let $\alpha_i \in \Zp^n$ be the configuration with $1$ in the $i$-th position and $0$ elsewhere. By convention, $\alpha_0$ is the all-0 configuration.

We say that a vertex $i$ in a configuration $c=(c_1,\ldots ,c_n)\in \Config[G]$ is stable if $c_i < \dgr[i]$.
Otherwise it is called unstable.
A configuration is called stable if all its (non-sink vertices) are stable, and we denote $\Stable[G]$ the set of all stable configurations on $G$.

Unstable vertices topple.
We define the toppling operator $\T_i$ corresponding to the toppling of an unstable vertex $i \in [n]$ in a configuration $c \in \Config[G]$ by:

_i(c) := c - [i] α_i + ∑_j: {i,j} ∈E α_j,
where the sum is over all vertices $j$ adjacent to $i$ in $G$, and the addition operator on configurations denotes pointwise addition at each vertex. In words, the toppling of a vertex $i$ sends one grain of sand to each neighbour of $i$ in $G$.

Performing this toppling may cause other vertices to become unstable, and we topple these also.
One can show (see e.g. <cit.>) 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).
In addition, the configuration $c'$ reached does not depend on the sequence in which vertices are toppled.
We call this $c'$ the stabilisation of $c$.

We now define a Markov chain on the set $\Stable[G]$ of stable configurations.
Fix a probability distribution $\mu=(\mu_1,\dots,\mu_n)$ on $[n]$ such that $\mu_i>0$ for all $i \in [n]$.
At each step of the Markov chain we add a grain at the vertex $i$ with probability $\mu_i$ and stabilise the resulting configuration.

The recurrent configurations are those appear infinitely often in the long-time running of this Markov chain. We let $\ASMRec[G]$ be the set of recurrent configurations for the ASM on the graph $G$.
We use the notation $\ASMRec[G]$ is to mark the difference between configurations which are recurrent for the ASM and those for the SSM (stochastic sandpile model) which will be introduced in Section <ref>.

The study of the recurrent configurations has been of central importance in ASM research. There are a number of ways to characterise them. Perhaps most famously Dhar's burning algorithm provides a straightforward algorithmic process to check if a given stable configuration is recurrent or not <cit.>.
The result we make use of in this paper however is given in terms of so-called compatible orientations. This result was first stated in these terms by Biggs [10], although the author credits a previous paper [27] as having equivalent results.

Given a configuration $c = (c_1,\ldots,c_n) \in \Config[G]$ and an orientation $\OO$ of $G$, we say that $\OO$ and $c$ are compatible if

∀i ∈[n], c_i ≥[i].
If $\OO$ and $c$ are compatible, we will say that $\OO$ is compatible with $c$, or simply that $\OO$ is compatible if there is no ambiguity over which configuration $c$ is considered.

Let $c = (c_1,\ldots,c_n) \in \Stable[G]$ be a stable configuration on the graph $G$. Then $c$ is recurrent for the ASM if, and only if, there exists an acyclic, $0$-rooted orientation $\OO$ compatible with $c$.

§.§ A stochastic variant of the ASM

In this section, we introduce a stochastic variant of the ASM, called the stochastic sandpile model (SSM). We are more informal than in the previous section, as most of the notions introduced closely mirror those of the ASM. For a more formal definition of the SSM, see [14].

In the ASM, the only randomness in the model concerns the choice of which vertex to add a grain to at each step of the Markov chain (i.e. the distribution $\mu$ in Section <ref>), while the subsequent operations – topplings and thus stabilisation – are deterministic.

In the SSM, we introduce an additional layer of randomness by making the topplings random.
Fix some parameter $p \in (0,1)$. When we have an unstable vertex $i$, we flip a biased coin for each neighbour $j$ of $i$, and with probability $p$ one grain is sent from $i$ to $j$ (with probability $(1-p)$ the grain remains at $i$).
The coin flips are independent for each neighbour $j$, and independent of other vertex topplings.

In <cit.> it is shown that, as in the ASM, starting from some unstable configuration $c$ and successively toppling unstable vertices, we eventually reach a stable configuration $c'$.
Moreover, this configuration $c'$ does not depend on the sequence in which vertices are toppled.

As for the ASM, we can therefore define a Markov chain for the SSM on the set of stable configurations $\Stable[G]$, whose dynamics are given by:

* Add a grain at a randomly chosen vertex according to some probability distribution $\mu=(\mu_1,\dots,\mu_n)$.

* Stabilise the resulting configuration. The stabilisation operation here is random, according to the toppling rules described above.

We denote the set of recurrent configurations for the SSM Markov chain $\SSMRec[G]$, to distinguish from the recurrent configurations of the standard ASM. The following was shown, in slightly different but equivalent form, in <cit.>.

Let $c = (c_1,\ldots,c_n) \in \Stable[G]$ be a stable configuration on the graph $G$. Then $c$ is recurrent for the SSM if, and only if, there exists a $0$-rooted orientation $\OO$ compatible with $c$.

The only difference between Theorems <ref> and <ref> lies in the acyclicity (or not) of the compatible orientation. This immediately implies that $\ASMRec[G] \subseteq \SSMRec[G]$.
In general, the converse doesn't hold. In Section <ref> we will see that on the wheel graph $W_n$ there is exactly one additional recurrent configuration for the SSM, which is the configuration $(1,1,\ldots,1)$ with one grain of sand at each vertex.

§.§ A partial order on recurrent configurations

We now introduce a partial order on the set of recurrent configurations. Most of what we write here is valid for both the ASM and SSM, so we don't specify which model is being considered.
We will simply denote by $\Rec[G]$ the set of recurrent configurations for the sandpile model on the graph $G$.

There is a natural partial order $\preceq$ on configurations of the sandpile model, defined as follows. If $c,c' \in \Config[G]$, we let $c \preceq c'$ if, and only if, $c_i \leq c'_i$ for all vertices $i \in [n]$.
In other words $c'$ can be obtained from $c$ through a succession of grain additions. The following is an immediate consequence of Theorems <ref> and <ref>.

Let $c \in \Rec[G]$ be a recurrent configuration, and $c' \in \Stable[G]$ a stable configuration satisfying $c \preceq c'$. Then $c'$ is recurrent.

We let $\MinRec[G]$ denote the set of minimal recurrent configurations on $G$ for the partial order $\preceq$, using the notation $\ASMMinRec[G]$ and $\SSMMinRec[G]$ when we need to specify that we are considering the ASM or SSM respectively.
In words, a configuration is minimal recurrent if it is recurrent and removing a single grain from any vertex would cause it to no longer be so. These minimal recurrent configurations will play a crucial role in the rest of our paper.

Let $c \in \Stable[G]$ be a stable configuration on $G$. Then $c$ is minimal recurrent for the ASM, resp. for the SSM, if, and only if, there exists an acyclic $0$-rooted, resp. $0$-rooted, orientation $\OO$ of $G$ such that:

∀i ∈[n],   c_i = [i].
Moreover, in the ASM case, such an orientation is unique.

Theorem <ref> was proved in the ASM case in [38]. The proof in the SSM case is identical, taking into account the fact that the compatible orientation from Theorem <ref> is not necessarily acyclic.
We also note that in the SSM case, the compatible orientation is unique up to cycle flipping. That is, if $c$ is minimal recurrent for the SSM, and $\OO$ and $\OO'$ are two orientations satisfying Equation (<ref>), then $\OO'$ can be obtained from $\OO$ by successively flipping a finite number of directed cycles. This is a consequence of a general result linking out- or in-degree sequences of orientations and cycle flips (see e.g. <cit.> and references therein).

§.§ The level statistic and level polynomial

Summing the Compatibility Inequality (<ref>) gives the following inequality on the total number of grains of a recurrent configuration (for either the ASM or SSM):

$$ \sum\limits_{i \in [n]} c_i \geq \sum\limits_{i \in [n]} \In[i] = \vert E \vert - \dgr[0],$$

since in the right-hand sum every edge other than those incident to the sink $0$ is counted exactly once. This naturally leads to the following definition of the level statistic for a recurrent configuration $c$:

(c) := ∑_i ∈[n] c_i + [0] - |E |,
which is a non-negative integer. Note that the level of a configuration is essentially its total number of grains (up to an additive constant that only depends on the underlying graph), and that if $c$ is minimal recurrent, then $\level(c) = 0$.

The level polynomial of a graph $G$ is then defined by:

Level_G(x) := ∑_c ∈[G] x^(c),
where the sum is over all recurrent configurations on $G$. When we need to specify whether we are considering the ASM or SSM, we will write $\mathrm{ASMLevel}_G$ or $\mathrm{SSMLevel}_G$, as needed.

A well-known result links the ASM level polynomial to the ubiquitous Tutte polynomial of a graph.

Let $T_G(x,y)$ denote the bivariate Tutte polynomial of a graph $G$. We have:

$$ T_G(1,x) = \mathrm{ASMLevel}_G(x).$$

This result was first proved by Merino [33] following a conjecture by Biggs [10]. Since then, bijective proofs have been given in [7, 16], as well as in [25] in the specific case of permutation graphs.
Note that the SSM level polynomial is known to satisfy a deletion-contraction relation that is very similar to that of the Tutte polynomial <cit.>.

§ THE SANDPILE MODEL(S) ON WHEEL GRAPHS

In this section, we focus on the sandpile models (ASM and SSM) on wheel graphs. We first interpret Theorems <ref> and <ref> in terms of the wheel graph $W_n$, giving straightforward characterisations of recurrent configurations.
Then, we introduce one of the key ideas of our paper: the mapping from a recurrent configuration to a canonical minimal recurrent configuration.
This allows us to exhibit a bijection from recurrent configurations of $W_n$ to properly-marked orientations of $C_n$, which then yields the announced bijection to subgraphs of $C_n$.

Because of the cyclic symmetries inherent in the cycle and wheel graphs, it will be easier to mainly reason modulo $n$ on the vertex set $[n]$.
For this, we should picture the graphs $C_n$ and $W_n$ as drawn on a plane, with vertices $1,2,\ldots,n$ in a clockwise cycle, as in Figure <ref>.
For two vertices $i,j \in [n]$, we write $[i,j]$ for the clockwise interval from $i$ to $j$, that is $[i,j] := \{i, i+1, \ldots, j-1, j\}$ if $i \leq j$, and $[i,j] = \{i, i+1, \ldots, n\} \cup \{1, \ldots, j\}$ otherwise. We use similar notation for open and semi-open intervals.

§.§ Straightforward characterisation of recurrent configurations on Wn

In this part, we give some straightforward characterisations of recurrent configurations for the ASM and SSM on the wheel graphs $W_n$.
Note that for the wheel graph $W_n$, we have $\Stablen = \{0,1,2\}^n$, i.e. the set of stable configurations is simply the set of words of length $n$ on $\{0,1,2\}$.
Theorems <ref> and <ref>, combined with Remark <ref>, immediately yield the following.

Let $c = (c_1,\ldots,c_n) \in \{0,1,2\}^n$ be a stable configuration on the wheel graph $W_n$. Then $c$ is recurrent for the SSM, resp. ASM, if, and only if, there exists an orientation, resp. acyclic orientation, of the cycle graph $C_n$, compatible with $c$.

The above proposition says that, on the wheel graph $W_n$, we can essentially ignore the sink in our study of the sandpile model.
While this may seem straightforward, it is an important building block towards our main result.
First, we show that recurrent configurations of the sandpile model on $W_n$ are given by words in $\{0,1,2\}^n$ satisfying simple conditions.

Let $c = (c_1,\ldots,c_n) \in \{0,1,2\}^n$ be a stable configuration on the wheel graph $W_n$. We have the following.

* The configuration $c$ is recurrent for the SSM if, and only if, for all $i,j \in [n]$ such that $c_i = c_j = 0$, there exists $k \in (i,j)$ such that $c_k = 2$. By convention, if $i=j$, we let $(i,j) := [n] \setminus \{i\}$.

* The configuration $c$ is recurrent for the ASM if, and only if, it is recurrent for the SSM and there exists $i \in [n]$ such that $c_i=2$.

In words, Theorem <ref> states that the recurrent configurations on $W_n$ are the words in $\{0,1,2\}^n$ such that between a pair of vertices with no grains of sand (cyclically), there must always be at least one vertex with two grains. We will refer to this as the $02$-cycle condition.
The ASM recurrent configurations have the additional condition that there must be at least one vertex with two grains of sand. From this, we immediately deduce that:

= ∪{ (1,1,…,1) },
as announced in Remark <ref>.
This result is actually noted in  [18] in the ASM case, with a proof relying on Dhar's burning algorithm. Since no such algorithm exists for the SSM, we give a full proof here using the Characterisation Proposition <ref>.
This proof also shows how to construct a compatible orientation from a recurrent configuration, which will be needed later in the paper.

We first show that if a configuration is recurrent, then the $02$-cycle condition holds.
Let $c = (c_1, \ldots, c_n)$ be a recurrent configuration, and $i,j \in [n]$ such that $c_i = c_j = 0$. Since $c$ is recurrent, there exists an orientation $\OO$ of $C_n$ compatible with $c$ by Proposition <ref>.
The Compatibility Condition (<ref>) implies $\In[i] = \In[j] = 0$, i.e. $i$ and $j$ are sources of $\OO$. In particular, this implies that $i \orighta i+1$ (the edge is directed clockwise) and $j \orighta j-1$ (the edge is directed counter-clockwise).
We can therefore define $k := \min \{k' \in (i,j); \, k'+1 \orighta k' \}$. By construction we have $k+1 \orighta k$ and $k-1 \orighta k$, i.e. $k$ is a target of the orientation $\OO$.
By the Compatibility Condition (<ref>), this implies that $c_k = 2$, as desired. Figure <ref> provides an illustration of this part of the proof.

[circle, draw=black] (i) at (sqrt(3),1) $i$;
[rounded rectangle, draw=black] (i+1) at (2,0) $i+1$;
[rounded rectangle, draw=black] (k-1) at (1/2,-1.9) $k-1$;
[circle, draw=black] (k) at (-1,-sqrt(3)) $k$;
[rounded rectangle, draw=black] (k+1) at (-1.85,-3/4) $k+1$;
[circle, draw=black] (j) at (-1/8,1.98) $j$;
[rounded rectangle, draw=black] (j-1) at (-sqrt(2),sqrt(2)) $j-1$;

[thick,->] (i)–(i+1);
[thick,->] (k-1)–(k);
[thick,->] (k+1)–(k);
[thick,->] (j)–(j-1);

[thick,dashed,->] (i+1) to [out=-90, in=20] (k-1);
[thick,dashed] (k+1) to [out=95, in=-110] (j-1);
[thick,dashed] (j) to [out=0, in=120] (i);

Illustration of the above proof. In the orientation $\OO$, all edges on the arc $[i,k]$ are directed clockwise, and $k$ is a target. Such a vertex must exist because $i \orighta i+1$ and $j \orighta j-1$.

Now if $c$ is recurrent for the ASM, we know that in addition we can assume $\OO$ to be acyclic. Since an acyclic orientation must have at least one target say $i$, the Compatibility Condition (<ref>) implies as above that $c_i = 2$, as desired.

Let us now show the converse. Suppose that $c$ satisfies the $02$-cycle condition.  This implies that we either have $c = (1,\ldots,1)$ or there exists some $i \in [n]$ such that $c_i = 2$. If $c = (1, \ldots, 1)$ then the directed $n$-cycle orientation (in either direction) is clearly compatible with $c$, so that $c$ is recurrent for the SSM by Proposition <ref>.

It remains to consider the case where $c_i = 2$ for some $i \in [n]$, and we will show that $c$ is recurrent for the ASM in this case (which implies that it is also recurrent for the SSM by Remark <ref>).
First, we show that we can assume that there exists $j \in [n]$ such that $c_j = 0$. Indeed, if this is not the case, we simply define $c'$ as $c'_{i-1} = 0$ and $c' = c$ elsewhere.
The configuration $c'$ still satisfies the $02$-cycle condition, and since $c' \preceq c$, if we show that $c'$ is recurrent, this implies that $c$ is recurrent by Proposition <ref>.
Therefore, without loss of generality, we may assume that there exists $j \in [n]$ such that $c_j = 0$.

We now define an orientation $\OO$ of $C_n$ as follows. Set all vertices $j$ where $c_j = 0$ as sources of the orientation.
Between two consecutive sources $j < j'$, orient all edges clockwise from $j$ until we reach a first vertex $k$ with $c_k=2$ (such a vertex exists, since $c$ satisfies the $02$-cycle condition).
Then orient all edges between $k$ and $j'$ counter-clockwise. By construction this orientation $\OO$ is compatible with $c$, and because it has at least one source it must be acyclic. It follows from Proposition <ref> that $c$ is recurrent for the ASM, as desired.

We now state a characterisation of minimal recurrent configurations for the sandpile model on the wheel graph $W_n$.

Let $c = (c_1,\ldots,c_n) \in \{0,1,2\}^n$ be a stable configuration on the wheel graph $W_n$. Then $c$ is minimal recurrent for the SSM if, and only if, for all $i,j \in [n]$ such that $c_i = c_j = 0$ and $c_{\ell} >0$ for all $\ell \in (i,j)$, there exists a unique $k \in (i,j)$ such that $c_k = 2$. By convention, if $i=j$, we let $(i,j) := [n] \setminus \{i\}$. Moreover, $c$ is minimal recurrent for the ASM if, and only if, $c$ is minimal recurrent for the SSM and there exists $i \in [n]$ such that $c_i=2$.

Theorem <ref> states that the minimal recurrent configurations on $W_n$ are the words in $\{0,1,2\}^n$ such that between a pair of consecutive vertices with no grains of sand (cyclically), there must always be exactly one vertex with two grains.
Equivalently, this means that cyclically around the wheel, each vertex with no grains must be followed by a vertex with two grains, possibly with some vertices with one grain in between, and vice versa. We will refer to this as the strict $02$-cycle condition.
The (minimal) recurrent configurations for the ASM simply have the additional condition that there must be at least one vertex with two grains of sand, or equivalently, for the minimal recurrent configurations, at least one vertex with no grain. As in the case of general recurrent configurations, we have:

$$ \SSMMinRecn = \ASMMinRecn \cup \{ (1,1,\ldots,1) \}.$$

Suppose first that $c$ is minimal recurrent. Since $c$ is recurrent, it must satisfy the (general) $02$-cycle condition. But if there were two distinct vertices with two grains of sand between two consecutive vertices with no grains, removing one grain from either of those two vertices would not break the $02$-cycle condition, which contradicts the minimality of $c$. So $c$ must satisfy the strict $02$-cycle condition, as desired.

Conversely, suppose that $c$ satisfies the strict $02$-cycle condition. By Theorem <ref>, $c$ is recurrent. But now, removing any grain from $c$ would break the $02$-cycle condition by producing a pair of vertices with no grain and no vertex with two grains in between. Thus, no grain can be removed from $c$ if the resulting configuration is to remain recurrent, which means exactly that $c$ is minimal recurrent.

The distinction between ASM and SSM comes directly from the results in the case of general recurrent configurations (Theorem <ref>), so does not need to be considered here.

The bijection in Theorem <ref> from a minimal recurrent configuration for the ASM on $W_n$ to its compatible orientation of $C_n$ is straightforward to describe.
If a vertex has no grain of sand, the two edges on the cycle are outgoing. Working outwards from that vertex, all edges keep the same direction until we encounter a vertex with two grains, where the directions “flip” (the two edges incident to that vertex are incoming), and we then simply repeat the process.
Figure <ref> shows an example of this construction. We write $\OO(c)$ for the orientation corresponding to a minimal recurrent configuration $c$.
For the additional minimal recurrent configuration $c = (1,\ldots,1)$ of the SSM, we have the choice between the two directed cycles of $C_n$ (clockwise or counter-clockwise). We fix, conventionally, $\OO(c)$ to be the counter-clockwise directed cycle in this case.

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=black] (1) at (0,2) $1$;
[circle, thick, draw=black] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=black] (3) at (2,0) $0$;
[circle, thick, draw=black] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=black] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=black] (7) at (-2,0) $1$;
[circle, thick, draw=black] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick,->] (1)–(2);
[thick,->] (3)–(2);
[thick,->] (3)–(4);
[thick,->] (4)–(5);
[thick,->] (6)–(5);
[thick,->] (7)–(6);
[thick,->] (8)–(7);
[thick,->] (8)–(1);
in 1,...,8

A minimal recurrent configuration on $W_8$ and the corresponding compatible orientation of $C_8$; the number of incoming edges at each vertex is equal to the number of grains.

§.§ Canonical minimal recurrent configurations

In this part, we introduce one of the key ideas of the paper, namely mapping each recurrent configuration of the SSM on $W_n$ to a corresponding canonical minimal recurrent configuration.
This idea of mapping recurrent configurations to minimal recurrent configurations has been used in previous combinatorial sandpile research.
In [24] the authors use it implicitly to define the “bounce path” in the parallelogram polyomino that a recurrent configuration on the complete bipartite graph is mapped to.
The bounce path defines a minimal recurrent configuration (or equivalently, a ribbon polyomino), and this bounce path is then used to define a $(q,t)$-Narayana polynomial which enumerates recurrent configurations of the ASM on complete bipartite graphs according to certain parameters.
In [26], the authors first establish a bijection between minimal recurrent configurations for the ASM on Ferrers graphs and so-called EW-tableaux.
A general recurrent configuration $c$ is then decomposed into a pair $(m(c), e(c))$ where $m(c)$ is the canonical minimal recurrent configuration associated with $c$, and $e(c)$ describes where grains need to be added to this $m(c)$ to re-constitute the original configuration $c$.
This leads to a bijection between all recurrent configurations for the ASM on Ferrers graphs and decorated EW-tableaux.

In the wheel graph case, the construction of the canonical minimal recurrent configuration is very similar to the construction in the last part of the proof of Theorem <ref>.

Let $c \in \SSMRecn$ be a recurrent configuration for the SSM on the wheel graph $W_n$. We say that $i \in [n]$ is a cyclically first maximal vertex if $c_i = 2$, and there exists $j \in [n]$ such that $c_j=0$ and for all $k \in (j,i)$ we have $c_k=1$.

A (clockwise) $01^*$-chain of $c$ is a set of consecutive vertices $j, j+1, \ldots, j + k$ such that $c_j = 0$ and $c_{j'} = 1$ for $j+1 \leq j' \leq j+k$. The $01^*$-weight of $c$, denoted $\w(c)$, is the total number of vertices belonging to a $01^*$-chain.

In words, a cyclically first maximal vertex is a vertex with two grains of sand which is the first such vertex following some vertex with no grain (in a clockwise direction).
The maximal $01^*$-chains of $c$ are the semi-open intervals from a vertex with no grains (included) to the following cyclically first maximal vertex (excluded).
Then the $01*$-weight of $c$ is simply the sum of the lengths of these maximal chains. This is illustrated in Figure <ref> below.

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=blue] (1) at (0,2) $1$;
[circle, thick, draw=mygreen] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=blue] (3) at (2,0) $0$;
[circle, thick, draw=blue] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=mygreen] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=red] (7) at (-2,0) $2$;
[circle, thick, draw=blue] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick] (2)–(3);
[thick] (5)–(6)–(7)–(8);
[thick, blue] (8)–(1)–(2);
[thick, blue] (3)–(4)–(5);
in 1,...,8
[thick] (0)–();

A recurrent configuration on $W_8$ with its cyclically first maximal vertices in green, and its non cyclically first maximal vertices in red. The maximal $01^*$-chains are represented in blue, so this configuration has $01^*$-weight equal to $4$.

We are now ready to define the canonical mapping from recurrent configurations to minimal recurrent configurations.

Let $c \in \SSMRecn$ be a recurrent configuration for the SSM on $W_n$. We define a configuration $c' := m(c) \in \Confign$ as follows:

$$ c'_i = \begin{cases}
0 & \text{if } c_i = 0 \\
2 & \text{if } i \mbox{ is a cyclically first maximal vertex } \\
1 & \text{otherwise}.
\end{cases}$$

The map $m : c \mapsto m(c)$ given by Definition <ref> defines a surjection from $\SSMRecn$ to $\SSMMinRecn$, which reduces to the identity on $\SSMMinRecn$.
Moreover, we have $\level(c) = \vert c \vert - \vert m(c) \vert$, where $\vert c \vert := \sum\limits_{i=1}^n c_i$ is the total number of grains of a configuration $c$.
We call $m(c)$ the canonical minimal recurrent configuration associated to $c$.

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=black] (1) at (0,2) $1$;
[circle, thick, draw=mygreen] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=black] (3) at (2,0) $0$;
[circle, thick, draw=black] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=mygreen] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=red] (7) at (-2,0) $2$;
[circle, thick, draw=black] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(7)–(8)–(1);
in 1,...,8
[thick] (0)–();

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=black] (1) at (0,2) $1$;
[circle, thick, draw=mygreen, color=mygreen] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=black] (3) at (2,0) $0$;
[circle, thick, draw=black] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=mygreen, color=mygreen] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=red, color=red] (7) at (-2,0) $1$;
[circle, thick, draw=black] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(7)–(8)–(1);
in 1,...,8
[thick] (0)–();

Illustrating the map from a recurrent configuration (left) to its canonical minimal recurrent configuration (right).

By Theorem <ref> all vertices with two grains of sand in a minimal recurrent configuration are cyclically first maximal vertices.  This implies that $m(c) = c$ if $c \in \SSMMinRecn$.
Moreover, if $c \in \SSMRecn$, then it satisfies the general $02$-cycle condition. By construction, this implies that $m(c)$ satisfies the strict $02$-cycle condition, and is therefore minimal recurrent as desired.
The formula for the level follows from the fact that since $m(c)$ is minimal recurrent, its level is $0$, and thus $\level(c) = \level(c) - \level(m(c)) = \vert c \vert - \vert m(c) \vert$.

§.§ Properly-marked orientations of Cn

In this part, we introduce the concept of properly-marked orientations of the cycle graph $C_n$, and exhibit a bijection between these objects and the set of recurrent configurations for the SSM on $W_n$.
A marked orientation of a graph $G=(V,E)$ is simply a pair $\OM = (\OO, M)$ where $\OO$ is an orientation of $G$ and $M$ a subset of the vertex set $V$. We refer to the vertices of $M$ as being the marked vertices of $\OM$.

A properly-marked orientation of the cycle graph $C_n$ is a marked orientation $\OM = (\OO,M)$ of $C_n$ such that for each marked vertex $i \in M$, the two edges incident to $i$ are both oriented in a counter-clockwise direction in $\OO$ (that is, $i+1 \orighta i \orighta i-1$), and $\OO$ contains at least one counter-clockwise edge. The set of properly-marked orientations of $C_n$ is denoted $\PMO$.

Let $c \in \SSMRecn$ be a recurrent configuration for the SSM on $W_n$. Define a marked orientation $\Phi_W(c) := \OM = (\OO, M)$ of $C_n$ by:

* $\OO := \OO(m(c))$, where $m(c)$ is the canonical minimal recurrent configuration associated with $c$ from Definition <ref>, and $\OO(m(c))$ is the corresponding orientation of $C_n$, as exhibited at the end of Section <ref>;

* $M$ is the set of vertices $i \in [n]$ such that $c_i = 2$ but $i$ is not a cyclically first maximal vertex.

Then $\Phi_W: \SSMRecn \rightarrow \PMO$ defines a bijection from the set of recurrent configurations for the SSM on $W_n$ to the set of properly-marked orientations of $C_n$.
Moreover, for any configuration $c \in \SSMRecn$, we have $\level(c) = \vert M \vert$ and $\w(c) = \big\vert \{ \text{clockwise edges of } \OO \} \big\vert$.

In this construction, the marked vertices of the orientation are given by the vertices which are maximal (i.e. have two grains of sand) but not cyclically first maximal, in the corresponding recurrent configuration $c$.
We can interpret these also as the locations of “excess grains” in $c$, that is the vertices where (exactly) one grain is removed from $c$ to obtain its canonical minimal recurrent configuration $m(c)$.

There is in fact little work remaining to be done in the proof, since nearly all has been done through the constructions of Sections <ref> and <ref>.
We simply exhibit the inverse bijection $\Psi_W: \PMO \rightarrow \SSMRecn$ as follows. Let $\OM = (\OO, W)$ be a properly-marked orientation of $C_n$, and define $\tilde{c}$ to be the minimal recurrent configuration corresponding to the orientation $\OO$, i.e. $\tilde{c}_i := \In[i]$ for all $i \in [n]$.
Then we define $c = \Psi_W(\OM) := \tilde{c} + \mathds{1}_M$ (i.e. $c$ is obtained from $\tilde{c}$ by adding one grain of sand to each marked vertex in $\OM$). It is clear that by construction $\Phi_W$ and $\Psi_W$ are inverses of each other, and the bijection is proved.

The formula for the level follows immediately from the level formula in Proposition <ref> and the observation that each marked vertex corresponds to exactly one grain of sand being removed in the transformation from $c$ to $m(c)$ (see Remark <ref>).
The formula for the $01^*$-weight follows from the observation that each vertex $i$ in a $01^*$-chain corresponds bijectively to a clockwise edge $i \orighta i+1$.
Figure <ref> provides an illustration of the different steps in the construction of $\Phi_W$.

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=blue] (1) at (0,2) $1$;
[circle, thick, draw=black] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=blue] (3) at (2,0) $0$;
[circle, thick, draw=blue] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=black] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=red] (7) at (-2,0) $2$;
[circle, thick, draw=blue] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(7)–(8)–(1);
in 1,...,8
[thick] (0)–();

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=blue] (1) at (0,2) $1$;
[circle, thick, draw=black] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=blue] (3) at (2,0) $0$;
[circle, thick, draw=blue] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=black] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=red, color=red] (7) at (-2,0) $1$;
[circle, thick, draw=blue] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(7)–(8)–(1);
in 1,...,8
[thick] (0)–();

[circle, thick, draw=black] (1) at (0,2) ;
[circle, thick, draw=black] (2) at (sqrt(2),sqrt(2)) ;
[circle, thick, draw=black] (3) at (2,0) ;
[circle, thick, draw=black] (4) at (sqrt(2),-sqrt(2)) ;
[circle, thick, draw=black] (5) at (0,-2) ;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) ;
[circle, thick, draw=red, color=red] (7) at (-2,0) ;
[circle, thick, draw=black] (8) at (-sqrt(2),sqrt(2)) ;
[thick,->,blue] (1)–(2);
[thick,->] (3)–(2);
[thick,->,blue] (3)–(4);
[thick,->,blue] (4)–(5);
[thick,->] (6)–(5);
[thick,->] (7)–(6);
[thick,->] (8)–(7);
[thick,->,blue] (8)–(1);

Illustrating the different steps in the construction of the bijection $\Phi_W$. On the left, a recurrent configuration $c$ on $W_8$ with its non cyclically first maximal vertex $v$ marked in red. In the middle, we have the canonical minimal recurrent configuration corresponding to $c$, keeping the marking on $v$. And on the right, the corresponding properly marked orientation of $C_8$ (with $M = \{v\}$ the previously marked vertex). The vertices on the $01^*$-chains of $c$ are in 1-1 correspondence with the clockwise-directed edges which immediately follow them (in blue).

§.§ Subgraphs of Cn

We are now equipped to establish the main result of this section: a bijection between recurrent configurations for the SSM on $W_n$ and subgraphs of $C_n$ which maps the level, resp. $01^*$-weight, of a configuration to the number of edges in, resp. vertices not in, the corresponding subgraph.
First, consider the following construction. Given a properly-marked orientation $\OM = (\OO, M)$ of $C_n$, we define a subgraph $S(\OM)$ of the edge-to-vertex dual graph $C_n'$ by letting the vertices of $S(\OM)$ be those that correspond to edges directed counter-clockwise in $\OO$, and the edges of $S(\OM)$ be those that correspond to marked vertices in $M$. Since $\OO$ contains at least one counter-clockwise edge (Definition <ref>), by construction the subgraph $S(\OM)$ is non-empty (it contains at least one vertex).
This construction is illustrated on the right-hand side of Figure <ref>.

By Definition <ref>, both edges incident to a marked vertex must be directed counter-clockwise.
This means that the two end-points of the corresponding edge of $C_n'$ are present in $S(\OM)$, and therefore that $S(\OM)$ is indeed a subgraph of $C_n'$.
It is then straightforward to check that $S$ defines a bijection from the set of properly-marked orientations of the cycle graph $C_n$ to the set of subgraphs of $C_n'$.
Moreover, by construction, the number of marked vertices in $\OM$ is equal to the number of edges in $S(\OM)$, and the number of clockwise edges in $\OM$ is equal to the number of vertices not in $S(\OM)$.
Since the (edge-to-vertex) dual graph $C_n'$ is isomorphic to $C_n$, with a slight abuse of notation we get the following, which is the first main result of our paper.

The map $S \circ \Phi_W : \SSMRecn \rightarrow \Subn$ defines a bijection from the set of recurrent configurations for the SSM on the wheel graph $W_n$ to the set of subgraphs of the cycle graph $C_n$.
Moreover, this bijection maps the level of a recurrent configuration $c$ to the number of edges in the corresponding subgraph $G$, and the $01^*$-weight of $c$ to the number of vertices that are not in $G$.

Figure <ref> illustrates the bijection from Theorem <ref>.
The outer cycle on the right is the properly marked orientation $\Phi_W(c)$, as in Figure <ref>, and the inner cycle is the corresponding subgraph of the edge-to-vertex dual cycle graph.
For readability purposes, we have represented vertices present in the subgraph (corresponding to counter-clockwise edges) in black, and “missing” vertices (corresponding to clockwise edges) in white.

[rectangle, draw=black] (0) at (0,0) $*$;
[circle, thick, draw=blue] (1) at (0,2) $1$;
[circle, thick, draw=black] (2) at (sqrt(2),sqrt(2)) $2$;
[circle, thick, draw=blue] (3) at (2,0) $0$;
[circle, thick, draw=blue] (4) at (sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=black] (5) at (0,-2) $2$;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) $1$;
[circle, thick, draw=red] (7) at (-2,0) $2$;
[circle, thick, draw=blue] (8) at (-sqrt(2),sqrt(2)) $0$;
[thick] (1)–(2)–(3)–(4)–(5)–(6)–(7)–(8)–(1);
in 1,...,8
[thick] (0)–();

[circle, thick, draw=black] (1) at (0,2) ;
[circle, thick, draw=black] (2) at (sqrt(2),sqrt(2)) ;
[circle, thick, draw=black] (3) at (2,0) ;
[circle, thick, draw=black] (4) at (sqrt(2),-sqrt(2)) ;
[circle, thick, draw=black] (5) at (0,-2) ;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) ;
[circle, thick, draw=red, color=red] (7) at (-2,0) ;
[circle, thick, draw=black] (8) at (-sqrt(2),sqrt(2)) ;
[thick,->,blue] (1)–(2);
[thick,->] (3)–(2);
[thick,->,blue] (3)–(4);
[thick,->,blue] (4)–(5);
[thick,->] (6)–(5);
[thick,->] (7)–(6);
[thick,->] (8)–(7);
[thick,->,blue] (8)–(1);

[circle, draw, fill=black] (11) at (-1.25,0.5) ;
[circle, draw, fill=black] (12) at (-1.25,-0.5) ;
[circle, draw, fill=black] (13) at (-0.55,-1.1) ;
[circle, draw=black] (14) at (0.55,-1.1) ;
[circle, draw=black] (15) at (1.25,-0.5) ;
[circle, draw, fill=black] (16) at (1.25,0.5) ;
[circle, draw=black] (17) at (0.55,1.1) ;
[circle, draw=black] (18) at (-0.55,1.1) ;

[very thick] (11)–(12);

Illustrating the bijection from $\SSMRecn$ to $\Subn$.

The following straightforward corollary links a specification of the Tutte polynomial of $W_n$ to the number of subgraphs of $C_n$.
While some quite complicated explicit general formulae have been given for the Tutte polynomial of $W_n$ (see e.g. [8, 12]), and simpler formulae for the chromatic polynomial (another specification of the Tutte polynomial), as far as we know, this particular specification, with its simple combinatorial interpretation, has not been observed previously in the literature.

Let $T_{W_n}(x,y)$ denote the Tutte polynomial of the wheel graph $W_n$. We have:

$$ 1 + T_{W_n}(1,x) = \sum\limits_{k \geq 0} a_{k,n} x^k, $$

where $a_{k,n}$ is the number of subgraphs of $C_n$ with $k$ edges.

The sequence $\left( a_{k,n} \right)$ is given by Sequence A277919 in the OEIS [29], although no explicit formula is given for computing these numbers.

This follows immediately from Theorem <ref> and Theorem <ref>, along with the observation that $\SSMRecn$ is obtained by adding the configuration $(1,\ldots,1)$ (with level $0$) to $\ASMRecn$ (see Equation (<ref>) and preceding remarks).

While the recurrent configurations for the ASM and SSM on wheel graphs differ only by one element, the configuration $(1,\ldots,1)$, this additional element really is crucial in our construction via canonical minimal recurrent configurations.
Indeed, any configuration where all vertices have at least one grain maps canonically to this additional element.
The properly-marked orientation corresponding to such a configuration is simply the counter-clockwise directed cycle, with marks on all vertices with two grains of sand.
In terms of subgraphs, these correspond to all subgraphs with $n$ vertices, i.e. where all the vertices are present.

§ LINKS TO DELANNOY NUMBERS

In this section, we consider the case where the cycle has an even number of edges (or vertices) and the subgraphs have exactly half the edges of the cycle. We denote $\Gamma_n$ the set of subgraphs of $C_{2n}$ with $n$ edges.
Our main goal is to enumerate $\Gamma_n$. In fact, we enumerate these subgraphs according to their number of connected components.
Consider a subgraph $G$ of $C_{2n}$ with $n$ edges. A connected component of $G$ is simply a path with $i$ edges and $i+1$ vertices, for some $i \geq 0$ (isolated vertices are considered to make up a connected component).
By summing these numbers of vertices and edges over all connected components, we see that if $G$ has $k$ connected components, then it has $(n+k)$ vertices (and vice versa). Note that we must have $1 \leq k \leq n$.

In the spirit of Figure <ref>, we will refer to the $(n-k)$ vertices not in  $G$ as the “missing” (or sometimes “white”) vertices of $G$.
For $k \in \{1,\ldots,n\}$, we denote $\Gamma_{n,k}$ the set of subgraphs in $\Gamma_n$ with $k$ connected components (equivalently $(n+k)$ vertices, equivalently $(n-k)$ missing vertices).
The subgraph on the left of Figure <ref> is an element of $\Gamma_{4,3}$.

The sets $\Gamma_{n,k}$ turn out to be equinumerous with certain lattice paths. These paths are named Delannoy paths after Henri Delannoy, a French mathematician of the 19th century. For more information about the life and work of Delannoy, we refer the reader to the very interesting historical note by Banderier and Schwer [6].

A Delannoy path is a path in $\Z^2$ starting at $(0,0)$ with steps $R:=(1,0)$, $U:=(0,1)$ and $D:=(1,1)$. A Delannoy path is said to be symmetric if it ends on the first diagonal, i.e. at some point $(x,x)$.
In this paper, we only consider symmetric Delannoy paths, and will typically refer to them as simply Delannoy paths.
For $n \geq 0$ we denote $\Del[n]$ the set of Delannoy paths ending at $(n,n)$, and for $0 \leq k \leq n$, we denote $\Del[n,k]$ the elements of $\Del[n]$ with $k$ steps $R$ (equivalently $k$ steps $U$, equivalently $(n-k)$ steps $D$). The $n$-th (central) Delannoy number is $\vert \Del[n] \vert$.

These numbers appear in several related problems in enumerative combinatorics and also have an interesting link to the Legendre polynomials.
We refer the interested reader to the fun paper by Sulanke [40] which lists 29 examples of combinatorial objects enumerated by the central Delannoy numbers, such as paths, polyominoes, domino tilings, graph matchings, and so on.
In this paper, we use the following notion of differed Delannoy paths.

A differed Delannoy path is a Delannoy path whose first step is not $D$. We denote $\DiffDel[n]$ the set of differed Delannoy paths ending at $(n,n)$ and $\DiffDel[n,k]$ those with $k$ steps $R$. Note that in this case we should have $k \geq 1$.

in 0,...,4
in 0,...,4
[fill=mygray, color=mygray] (,) circle [radius=0.1];
[dashed, mygray] (-0.3,-0.3)–(4.3,4.3);
(1) [fill] (0,0) circle [radius=0.1];
(2) [fill] (1,0) circle [radius=0.1];
(3) [fill] (1,1) circle [radius=0.1];
(4) [fill] (1,2) circle [radius=0.1];
(5) [fill] (2,3) circle [radius=0.1];
(6) [fill] (3,3) circle [radius=0.1];
(7) [fill] (4,3) circle [radius=0.1];
(8) [fill] (4,4) circle [radius=0.1];
in 1,...,7
[thick] (0,0)–(1,0)–(1,2)–(2,3)–(4,3)–(4,4);

A differed Delannoy path in $\DiffDel[4,3]$.

The term differed Delannoy path comes from the following straightforward observation. Partitioning elements of $\Del[n,k]$ according to whether their first step is $D$ or not, we get that $\vert \DiffDel[n,k] \vert = \vert \Del[n,k] \vert - \vert \Del[n-1,k] \vert$ for any $n \geq 1$ and $k \in \{1,\ldots,n\}$. That is, the differed Delannoy paths are counted by the first differences of the Delannoy numbers.

The general sequence of first differences of Delannoy numbers $\vert \DiffDel[n] \vert$ (not decomposed according to step numbers) is given by Sequence A110170 in the OEIS [29]. If we decompose differed Delannoy paths according to their number of steps, we get the following array, with row indices $n \geq 1$ and column indices $k \geq 1$.

$$ \begin{array}{llllll}
2 & & & & & \\
4 & 6 & & & & \\
6 & 24 & 20 & & & \\
8 & 60 & 120 & 70 & & \\
10 & 120 & 420 & 560 & 252 & \\
12 & 210 & 1120 & 2520 & 2520 & 924 \\
\end{array}

We can check that the rows do indeed sum to the first differences of Delannoy numbers given in the OEIS.

The sequence of numbers above does not yet appear in the OEIS (the author has submitted it for consideration). The equivalent array for Delannoy numbers rather than first differences is Sequence A063007.

Let $n \geq 1$, and $k \in \{1,\ldots,n\}$. The following three sets all have cardinality

2kk ·n+k-1n-k.

* The set of recurrent configurations $c \in \Rec[W_{2n}]$ satisfying $\level(c) = n$ and $\w(c) = n-k$.

* The set $\Gamma_{n,k}$ of subgraphs of $C_{2n}$ with $n$ edges and $k$ connected components (equivalently $(n+k)$ vertices).

* The set $\DiffDel[n,k]$ of differed Delannoy paths ending at $(n,n)$ with $k$ steps $R$ (equivalently $(n-k)$ steps $D$).

The following lemma is a straightforward classical counting exercise, but as it will be re-used in various parts of the proof of the above theorem, we find it useful to state it here.

Let $n \geq 1$ and $k \geq 0$. The number of ways of putting $k$ unmarked (indistinguishable) balls into $n$ ordered (distinguishable) boxes is given by the binomial coefficient $\binom{n+k-1}{k}$.

Including the $(n-1)$ delimiters between the boxes, there are $(n+k-1)$ “spaces” (balls + delimiters) in total for us to choose where the $k$ balls go. More formally, if $b = (b_1, \ldots, b_n)$ denotes the balls-in-boxes sequence ($b_i$ being the number of balls in box $i$), we can define a word $w(b) := 0^{b_1} 1 0^{b_2} 1 \cdots 0^{b_{n-1}} 1 0^{b_n}$, where $0^k = 0\cdots0$ (repeated $k$ times). The map $w$ is a bijection from the desired balls-in-boxes configurations to the set of words on $\{0, 1\}$ with $k$ $0$'s and $(n-1)$ $1$'s.

The fact that (1) and (2) are equinumerous is an immediate consequence of Theorem <ref> (a subgraph of $C_{2n}$ with $n+k$ vertices has $(n-k)$ “missing” vertices).
The fact that (2) and (3) are equinumerous when removing the subscript $k$ (keeping only $n$) is noted in the CrossRefs of Entry A277919 of the OEIS [29] (“Middle diagonal gives A110170”), but we haven't been able to find a reference to this in the literature, so are unsure if it has been formally proved or not.
In any case, the specialisation in $k$ does not seem to have been noted.

Our first claim is the following formula enumerating differed Delannoy paths.

|[n,k] |= 2kk ·n+k-1n-k,
for all $n \geq 1$ and $ k \in \{1,\ldots,n\}$. Indeed, since a path in $\DiffDel[n,k]$ is comprised of $k$ $R$-steps, $k$ $U$-steps, and $(n-k)$ $D$-steps where the first step is not $D$, we can decompose it as follows.
First, choose the underlying “shape” of the path, that is the path with all $D$ steps removed. There are $\binom{2k}{k}$ such shapes. It remains to insert the $(n-k)$ $D$-steps into a shape.
Now notice that $D$-steps can be inserted after any $R$- or $U$-step of the shape (but not before the first step), which gives $2k$ places where $D$-steps can be inserted.
The insertion of $D$-steps is thus equivalent to placing $(n-k)$ unmarked balls into $2k$ ordered boxes, which yields Equation (<ref>) by Lemma <ref>.

We therefore wish to show that $\Gamma_{n,k}$ is also enumerated by the right-hand side of Equation (<ref>).
It turns out to be easier to enumerate a subset of $\Gamma_{n,k}$. Define $\bar{\Gamma}_{n,k}$ to be the subset of graphs $G \in \Gamma_{n,k}$ such that the vertex $1$ is in $G$ but the edge $\{2n,1\}$ is not.
In words, $\bar{\Gamma}_{n,k}$ is the set of subgraphs of $C_{2n}$ with $n$ edges and $k$ connected components, where the vertex labelled $1$ (the “top” vertex in our geometric representation) is in the subgraph, and it is the “first” (clockwise) vertex in its connected component. We claim that:

|Γ̅_n,k |= n+k-1n ·n-1n-k,
for all $n \geq 1$ and $ k \in \{1,\ldots,n\}$. To show this, we observe that the construction of a subgraph $G \in \bar{\Gamma}_{n,k}$ is equivalent to placing $n$ unmarked black balls and $(n-k)$ unmarked white balls into $k$ ordered boxes.
The black balls correspond to the $n$ edges, placed in the $k$ connected components of $G$, while the white balls correspond to the $(n-k)$ vertices in $C_{2n} \setminus G$ (i.e. absent or “white” vertices of the subgraph $G$), placed into the $k$ gaps between connected components of $G$.

We illustrate the construction on an example in Figure <ref> below, with $n=4$ and $k=3$.
Going round the cycle clockwise, the connected component starting at the top vertex has one edge, and there are no missing vertices between this component and the next connected component, so we put one black ball (for the edge) and no white balls (for the missing vertices) in Box 1.
Then the second connected component has three edges, and is followed by one missing (white) vertex, so we put three black balls and one white ball in Box 2.
Finally, the third connected is an isolated vertex and is followed by no missing vertices, so Box 3 is empty. This correspondence is clearly one-to-one (it is straightforward to construct its inverse), and Equation (<ref>) follows by once again applying Lemma <ref>.

[circle, thick, draw=black, fill=black] (1) at (0,2) ;
[circle, thick, draw=black, fill=black] (2) at (sqrt(2),sqrt(2)) ;
[circle, thick, draw=black, fill=black] (3) at (2,0) ;
[circle, thick, draw=black, fill=black] (4) at (sqrt(2),-sqrt(2)) ;
[circle, thick, draw=black, fill=black] (5) at (0,-2) ;
[circle, thick, draw=black, fill=black] (6) at (-sqrt(2),-sqrt(2)) ;
[circle, thick, draw=black] (7) at (-2,0) ;
[circle, thick, draw=black, fill=black] (8) at (-sqrt(2),sqrt(2)) ;
[thick] (1)–(2);
[thick] (3)–(4)–(5)–(6);

[thick] (5,1)–(5,-1)–(6.5,-1)–(6.5,1);
[above, yshift=6, circle, draw, fill=black] (b1) at (5.75, -1) ;
[below, yshift=-6] at (5.75,-1) Box 1;

[thick] (7.5,1)–(7.5,-1)–(9,-1)–(9,1);
[above, yshift=6, circle, draw, fill=black] (b2) at (8, -1) ;
[above, yshift=6, circle, draw, fill=black] (b3) at (8.5, -1) ;
[yshift=-2, circle, draw, fill=black] (b4) at (8, 0) ;
[yshift=-2, circle, draw=black] (w1) at (8.5, 0) ;
[below, yshift=-6] at (8.25,-1) Box 2;

[thick] (10,1)–(10,-1)–(11.5,-1)–(11.5,1);
[below, yshift=-6] at (10.75,-1) Box 3;

Illustrating the correspondence between $\bar{\Gamma}_{n,k}$ and placing $n$ unmarked black balls and $(n-k)$ unmarked white balls into $k$ ordered boxes, for $n=4$ and $k=3$.

Finally, we show the following formula linking the enumeration of this subset $\bar{\Gamma}_{n,k}$ to the set $\Gamma_{n,k}$. This formula can be thought of as a type of cyclic lemma for graphs.

(2n) ·|Γ̅_n,k |= k ·|Γ_n,k |,
for all $n \geq 1$ and $ k \in \{1,\ldots,n\}$.
The way this is written is suggestive.
The left-hand side counts the set of pairs $(G,i) \in \bar{\Gamma}_{n,k} \times [2n]$, i.e. the set of graphs $G \in \bar{\Gamma}_{n,k}$ rooted at a vertex of $C_{2n}$.
Similarly, the right-hand side counts the set of graphs $G \in \Gamma_{n,k}$ rooted at a connected component of $G$.

In fact, it is slightly more convenient to think of the two sides counting certain doubly-rooted subgraphs of $C_{2n}$. A doubly-rooted subgraph is a triple $\mathcal{G} = (G,i,c)$ where $G \in \Gamma_{n,k}$ is a sub-graph of $C_{2n}$, $i \in [2n]$ is a vertex of $C_{2n}$ (not necessarily a vertex of the subgraph $G$), and $c$ is a connected component of $G$. Now the left-hand side of Equation (<ref>) counts doubly-rooted subgraphs $(G,i,c)$ such that $G \in \bar{\Gamma}_{n,k}$ (i.e. $1$ is the clockwise first vertex of the connected component $c$). An example is shown on the left of Figure <ref>. The right-hand side of Equation (<ref>) counts doubly-rooted subgraphs $(G,i,c)$ such that $i=1$ (i.e. the “top” vertex is the root). We exhibit a simple bijection between these two sets of doubly-rooted subgraphs.

Consider a doubly-rooted subgraph $\mathcal{G} = (G,i,c)$ with $G \in \bar{\Gamma}_{n,k}$, i.e. $1$ is the clockwise first vertex of the connected component $c$.
We construct a doubly-rooted subgraph $
\mathcal{G}' = (G',i',c')$ by rotating $G$ anti-clockwise through $i-1$ vertices, so that the vertex that was previously labelled $i$ is now labelled $i'=1$. The connected component $c'$ is the image of $c$ under this rotation, i.e. a path of same length as $c$, whose clockwise first vertex is now $(2n+1-i)$.

The map $\mathcal{G} \mapsto \mathcal{G'}$ gives the desired bijection. By construction it maps a doubly-rooted subgraph whose connected component root starts at vertex $1$ to a doubly-rooted subgraph whose root vertex is $1$. Furthermore, the inverse bijection is simply the inverse rotation. Namely, starting from $\mathcal{G}' = (G',1,c')$, we get the inverse image $\mathcal{G} = (G, i, c)$ by rotating $\mathcal{G}'$ so that its connected component root starts at vertex $1$.

The bijection between rooted graphs is illustrated on Figure <ref> below.
On the left, a doubly-roooted subgraph $\mathcal{G} = (G,i,c)$ with $G \in \bar{\Gamma}_{n,k}$. We represent the vertex root in blue (here labelled $i = 7$), and the connected component root (which here starts at the top vertex $j=1$) in red.
On the right, the corresponding doubly-rooted subgraph $
\mathcal{G}' = (G',1,c')$, obtained by rotating $\mathcal{G}$ counterclockwise through $i-1 = 6$ vertices (or equivalently clockwise through $2$ vertices), so that the vertex root is now the top vertex labelled $i'=1$, and the connected component root starts at vertex labelled $j' = 2n + 1 - i = 3$.

[circle, thick, draw=red, fill=red] (1) at (0,2) ;
[circle, thick, draw=red, fill=red] (2) at (sqrt(2),sqrt(2)) ;
[circle, thick, draw=red, fill=red] (3) at (2,0) ;
[circle, thick, draw=black] (4) at (sqrt(2),-sqrt(2)) ;
[circle, thick, draw=black, fill=black] (5) at (0,-2) ;
[circle, thick, draw=black, fill=black] (6) at (-sqrt(2),-sqrt(2)) ;
[circle, thick, draw=blue] (7) at (-2,0) ;
[circle, thick, draw=black, fill=black] (8) at (-sqrt(2),sqrt(2)) ;
[thick] (6)–(5);
[thick,red] (1)–(2)–(3);
[left, xshift=-5pt] at (-2,0) $i=7$;
[above, yshift=4pt] at (0,2) $j=1$;

[circle, thick, draw=blue] (1) at (0,2) ;
[circle, thick, draw=black, fill=black] (2) at (sqrt(2),sqrt(2)) ;
[circle, thick, draw=red, fill=red] (3) at (2,0) ;
[circle, thick, draw=red, fill=red] (4) at (sqrt(2),-sqrt(2)) ;
[circle, thick, draw=red, fill=red] (5) at (0,-2) ;
[circle, thick, draw=black] (6) at (-sqrt(2),-sqrt(2)) ;
[circle, thick, draw=black, fill=black] (7) at (-2,0) ;
[circle, thick, draw=black, fill=black] (8) at (-sqrt(2),sqrt(2)) ;
[above, yshift=4pt] at (0,2) $i'=1$;
[right, xshift=5pt] at (2,0) $j'=3$;
[thick] (7)–(8);
[thick,red] (3)–(4)–(5);

Illustrating the bijection that established Equation (<ref>) .

Combining Equations (<ref>), (<ref>) and (<ref>), it suffices to check the following binomial equality

2nk ·n+k-1n ·n-1n-k = 2kk ·n+k-1n-k,
which can be done by simply expanding the binomial coefficients. This completes the proof of Theorem <ref>.

While our proofs of the combinatorial equalities (<ref>), (<ref>) and (<ref>) are all bijective, and a bijective proof can undoubtedly be found of the binomial equality (<ref>), we have been unable to find a direct bijection between the sets $\Gamma_{n,k}$ and $\DiffDel[n,k]$.
It would be useful if such a bijection (offering a direct bijective proof of Theorem <ref>) could be exhibited in the future.

§ THE SANDPILE MODEL ON FAN GRAPHS

In this section, we study the sandpile model on fan graphs $F_n$.
Our main goals in this section are to show that the recurrent configurations on $F_n$ are in bijection with certain subgraphs of the path graph $P_n$, and that they are counted by certain lattice paths. As in the wheel graph case, this specialises according to the level of the configuration.
As in Sections <ref> and <ref>, it is convenient to consider the geometric representations of $F_n$ and $P_n$ where $P_n$ is simply a line of vertices $1,\ldots,n$ from left-to-right, and thus $F_n$ is as in Figure <ref>.
The tools we use are similar to those of these two sections, so we will allow ourselves to be briefer here. We proceed as follows.

Firstly, in Section <ref>, we define a notion of canonical minimal recurrent configuration, as in Section <ref>. This allows us to exhibit a bijection between $\Rec[F_n]$ and a set of properly-marked words on the alphabet $\{L,R\}$. We then exhibit a natural bijection between these properly-marked words and subgraphs of $P_n$ whose vertex set contains the right-most vertex $n$.
In Section <ref>, we partition these properly-marked words according to their number of unmarked $L$-elements. Using similar decompositions to those in the proof of Theorem <ref>, we then show that they are enumerated by the lattice paths in question.

From Theorem <ref>, Remark <ref> and the observation that the path graph $P_n$ is acyclic (hence so are all its orientations), we deduce that the sets of recurrent configurations for the ASM and the SSM on $F_n$ are the same.
Thus, we will simply talk of recurrent configurations, and denote $\Rec[F_n]$ their set.

§.§ Characterisation and enumeration of Rec(Fn)

In the spirit of Theorem <ref>, we have a similar characterisation of the set $\Rec[F_n]$.
Note that this time $(i,j)$ refers to the standard open integer interval, rather than the cyclic interval of the wheel graph case.

Let $c \in \{0,1,2\}^n$ with $c_1,c_n \leq 1$ be a stable configuration on $F_n$. Then $c$ is recurrent if, and only if, for all pairs $i,j \in [n]$ such that $i<j$ and $c_i=c_j=0$, there exists $k \in (i,j)$ such that $c_k = 2$.

The proof of this result is essentially analogous to that of Theorem <ref>, with minor adjustments to take into account the removal of the cycle edge $\{n,1\}$, so we omit it here.
Similarly, the minimal recurrent configurations are configurations with at least one pair $(i,j)$ such that $c_i=c_j=0$ and for each such consecutive pair the $k$ is unique, as well as configurations where exactly one vertex has no grains, and all other vertices have (exactly) one grain.

As in Section <ref>, we construct a bijection between recurrent configurations on $F_n$ and certain marked orientations of the path $P_n$. We proceed as follows. Consider the path graph $P_n^0$ with an extra vertex $0$ and edge $\{0,1\}$. Given a recurrent configuration $c \in \Rec[F_n]$, we define a marked orientation $(\OO,M)$ of $P_n^0$ as follows:

* Direct the edge $0 \olefta 1$.

* For $i \geq 1$, assume we have given a direction to $\{i-1,i\}$ in $\OO$.

* If $i-1 \olefta i$, then direct $i \orighta i+1$ if $c_i=0$. Otherwise, direct $i \olefta i+1$, and mark vertex $i$ if $c_i = 2$.

*  If $i-1 \orighta i$, then direct $i \orighta i+1$ if $c_i=1$ and $i \olefta i+1$ if $c_i=2$.

* Mark vertex $n$ if $n-1 \olefta n$ and $c_n=1$.

Note that Theorem <ref> implies that $c_i=0$ is impossible in Case <ref>.
In words, the marked orientation is constructed left-to-right as follows. So long as $c_i \geq 1$, direct $i \olefta i+1$ i.e. “leftwards”, marking vertex $i$ if $c_i=2$.
When encountering $i$ such that $c_i=0$, start directing all subsequent edges $j \orighta j+1$ i.e. “rightwards” for $j \geq i$ until encountering the first $j$ such that $c_j = 2$ (or reaching the end vertex $n$), at which point we start directing edges leftwards again, and repeat the process.
Mark the rightmost vertex $n$ if the last edge $\{n-1,n\}$ is directed leftwards and $c_n = 1$.

Removing the (always leftwards) edge $\{0,1\}$, we obtain a marked orientation $(\OO,M)$ of the path graph $P_n$ where all marked vertices $i$ must have $i+1 \orighta i \orighta i-1$ (with the convention that $n+1 \orighta n$).
As in the wheel graph case, the underlying orientation $\OO$ defines a minimal recurrent configuration on $F_n$, which can be viewed as the canonical minimal recurrent configuration associated with $c$, while the marked vertices represent the locations of “excess grains” in $c$ (see Remark <ref>).

In the path graph case, it is slightly more convenient to mark the edges instead of the vertices.
For this, if a vertex $i$ is marked, we simply move the mark to its left edge $\{i-1,i\}$ (necessarily directed $i-1 \olefta i$). Since the leftmost vertex $1$ can never be marked by construction ($c_1 < 2$ since $c$ is stable), there is no issue in doing this.
Transforming the marked orientation into a word on the alphabet $\{L,R\}$ with markings on certain $L$-elements yields the following.

A properly-marked $\{L,R\}$-word is a word on the alphabet $\{L^u, L^m, R\}$ such that no occurrence of $L^m$ is followed by an occurrence of $R$.
We refer to the occurrences of $L^m$ as the marked $L$-elements (or simply marked elements), and the occurrences of $L^u$ as the unmarked $L$-elements (or simply unmarked elements).
The set of properly marked $\{L,R\}$-words of length $n$ is denoted $\PMW_n$.

Note that the condition is equivalent to every marked $L$-element being either followed by another $L$-element (marked or not), or being the last element in the word. We have therefore constructed a map $\Phi_F:\Rec[F_n] \rightarrow \PMW_{n-1}$.  The equivalent of Theorem <ref> is the following result (again, the proof is analogous, so we omit it here).

The map $\Phi_F:\Rec[F_n] \rightarrow \PMW_{n-1}$ is a bijection from the set of recurrent configurations on the fan graph $F_n$ to the set of properly-marked $\{L,R\}$-words of length $(n-1)$. Moreover, for $c \in \Rec[F_n]$, the level of the configuration $c$ is equal to the number of marked elements in the word $\Psi_F(c)$.

An example of the bijection $\Phi_F$, applied to the recurrent configuration (read from left to right) $c = (1,1,0,1,2,2,0,2,1) \in \Rec[F_9]$, is illustrated in Figure <ref>.
The marked orientation of the path $P_9$ is shown, with marks (in red) on both the vertices and their immediate left edges for convenience.
This maps to the properly-marked $\{L,R\}$-word $w = \Phi_F(c) \in \PMW_8$, which is shown above the orientation ($w = L^uL^uRRL^mL^uRL^m$).

[rectangle, draw=black] (0) at (0,-2.5) $*$;
[circle, draw=black] (1) at (-6,0) $1$;
[circle, draw=black] (2) at (-4.5,0) $1$;
[circle, draw=black] (3) at (-3,0) $0$;
[circle, draw=black] (4) at (-1.5,0) $1$;
[circle, draw=black] (5) at (-0,0) $2$;
[circle, draw=red] (6) at (1.5,0) $2$;
[circle, draw=black] (7) at (3,0) $0$;
[circle, draw=black] (8) at (4.5,0) $2$;
[circle, draw=red] (9) at (6,0) $1$;
in 1,...,9
[thick,->] (2)–(1);
[thick,->] (3)–(2);
[thick,->] (3)–(4);
[thick,->] (4)–(5);
[thick,->,red] (6)–(5);
[thick,->] (7)–(6);
[thick,->] (7)–(8);
[thick,->,red] (9)–(8);

[yshift=0.5cm] (w1) at (-5.25,0) $L^u$;
[yshift=0.5cm] (w2) at (-3.75,0) $L^u$;
[yshift=0.5cm] (w3) at (-2.25,0) $R$;
[yshift=0.5cm] (w4) at (-0.75,0) $R$;
[yshift=0.5cm] (w5) at (0.75,0) $L^m$;
[yshift=0.5cm] (w6) at (2.25,0) $L^u$;
[yshift=0.5cm] (w7) at (3.75,0) $R$;
[yshift=0.5cm] (w8) at (5.25,0) $L^m$;

Illustrating the bijection $\Phi_F$.

As in the wheel graph case, there is a subgraph interpretation of properly-marked words. Let $w = w_1 \cdots w_{n-1}$ be a properly-marked $\{L,R\}$-word of length $(n-1)$. We construct a subgraph $G = (V,E) = T(w)$ of the path graph $P_n$ by letting $V = \big\lbrace i \in [n]; \, w_i \in \{L^u, L^m\} \big\rbrace \cup \{ n \}$, and $E = \big\lbrace \{i, i+1\}; w_i = L^m \big\rbrace$.For example, if $w = L^uL^uRRL^mL^uRL^m$ is the properly-marked word from Figure <ref>, then the corresponding subgraph has vertex set $V = \{1, 2, 5, 6, 8, 9 \}$ and edge set $E = \big\lbrace \{5, 6\}, \{8, 9\} \big\rbrace$.

In words, if we think of the word $w$ as labelling the edges of $P_n$ as in Figure <ref>, then the vertices of $T(w)$ are those whose right-incident edge is labelled with an $L$-element (marked or not), as well as the right-most vertex $n$, while the edges are simply the edges labelled $L^m$. Since each $L^m$ is either followed by an $L$-element, or is the right-most edge, this implies that the map is well defined, i.e. that $T(w)$ is indeed a subgraph of $P_n$.

Moreover, given a subgraph $G = (V,E)$ of $P_n$ such that $n \in V$, we can define its inverse $w = w_1 \cdots w_{n-1} = T'(G)$ by setting:

$$ w_i = \begin{cases}
L^m & \text{if } \{i, i+1\} \in E \\
L^u & \text{if } i \in V \mbox{ and } \{i, i+1\} \notin E \\
R & \text{otherwise (i.e. if } i \notin V \mbox{)}.
\end{cases} $$

By construction, $T'(G)$ is a properly-marked $\{L,R\}$-word, and the maps $T$ and $T'$ are inverses of each other. We also note that for $i < n$, then $i$ is the right-most vertex of a connected component of $G$ if, and only if, $w_i = L^m$. This implies that the number of connected components of $G$ is equal to the number of unmarked $L$-elements plus one (for the right-most connected component, whose right-most vertex is always $n$). We summarise this in the following proposition.

The map $T: w \mapsto T(w)$ is a bijection between the set of properly-marked $\{L,R\}$-word of length $(n-1)$ and the set of subgraphs of the path graph $P_n$ whose vertex set contains $n$. Moreover, the number of marked, resp. unmarked, $L$-elements of $w$ is equal to the number of edges, resp. to one plus the number of connected components, of $T(w)$.

Proposition <ref> and Theorem <ref> immediately combine for the following.

The map $T \circ \Phi_F$ defines a bijection from the set of recurrent configurations on the fan graph $F_n$ to the set of subgraphs of the path graph $P_n$ whose vertex set contains $n$. Moreover, this bijection maps the level of a recurrent configuration $c$ to the number of edges in the corresponding subgraph $G$.

We now provide a counting formula for the set of properly-marked words $\PMW_n$. In fact, we count these according to the numbers of both marked and unmarked $L$-elements. This also counts subgraphs of $P_n$ containing $n$ according to their numbers of edges and connected components, by Proposition <ref>.

Let $n \geq 1$ and $k,r \geq 0$ such that $k+r \leq n-1$. The number of properly-marked $\{L,R\}$-words of length $(n-1)$ with $k$ marked $L$-elements and $r$ unmarked $L$-elements is equal to $\binom{n-k-1}{r} \cdot \binom{r+k}{r}$.

The proof is similar to that of the enumeration of differed Delannoy paths in Equation (<ref>).
First we choose the underlying “shape” of the word, that is the word with marked elements removed.
There are $\binom{n-1-k}{r}$ possibilities for this (removing the $k$ marked $L$-elements from the word leaves $(n-1-k)$ elements to place, of which $r$ are unmarked $L$-elements and the remainder $R$-elements).

We then need to insert the $k$ marked elements into this shape. But there are $(r + 1)$ places where we can insert such elements: to the left of any of the $r$ unmarked element, and in the rightmost position(s) of the word.
Thus the possible insertions into a given “shape” are equivalent to placing $k$ unmarked balls into $(r+1)$ ordered boxes, and the result follows by Lemma <ref>.

By combining Proposition <ref> and Theorem <ref>, we immediately get the following enumeration formula for $\Rec[F_n]$.

Let $n \geq 1$ and $0 \leq k < n$. Then:

$$ \big\vert \{ c \in \Rec[F_n]; \, \level(c) = k \} \big\vert = \sum\limits_{r=0}^{n-k-1} \binom{n-k-1}{r} \cdot \binom{r+k}{r}. $$

§.§ Kimberling paths

For $n \geq 1$ and $0 \leq k \leq (n-1)$, the numbers $R(n,k) := \big\vert \{ c \in \Rec[F_n]; \, \level(c) = k \} \big\vert$ of recurrent configurations for the fan graph $F_n$ with level $k$ give the following enumeration triangle.

$$ \begin{array}{lllllll}
1 & & & & & \\
1 & 2 & & & & & \\
1 & 3 & 4 & & & & \\
1 & 4 & 8 & 8 & & & \\
1 & 5 & 13 & 20 & 16 & & \\
1 & 6 & 19 & 38 & 48 & 32 & \\
1 & 7 & 26 & 63 & 104 & 112 & 64 \\
\end{array}

This is (essentially) Sequence A049600 in the OEIS [29], and enumerates certain lattice paths.
Hetyei [28] calls a variant of this array the asymmetric Delannoy numbers and shows that they are related to a face-enumeration problem associated with Jacobi polynomials.
Callan [13] calls the lattice paths enumerated by this sequence Kimberling paths, after the author of the aforementioned sequence in the OEIS, and we follow this latter terminology here.

A Kimberling path is a lattice path starting at the origin $(0,0)$ and with steps in $\N \times \Zp$. In other words, Kimberling paths are made of steps with finite non-negative slope (so horizontal rightwards steps are allowed, but vertical upward steps are not). Note that steps in a Kimberling path can have any length. For $i>0, j \geq 0$, we denote $\Kimb[i,j]$ the set of Kimberling paths ending at $(i,j)$. If $0 \leq r \leq i-1$, we denote $\Kimb[i,j,r] \subseteq \Kimb[i,j]$ the set of such paths with $r$ internal vertices (excluding start and end points), equivalently $(r+1)$ steps.

[thick] (0,0)–(2,1);

[fill] (1,0) circle [radius=0.1];

[fill] (1,1) circle [radius=0.1];

The three paths in $\Kimb[2,1]$. There are three paths in total, one with no internal vertices (left) and two with one internal vertex (middle and right).

The following gives a simple counting formula for Kimberling paths (see e.g. <cit.>.

Let $i \geq 1, j \geq 0$ and $r \in \{0,\ldots,i-1\}$. Then:

$$ \big\vert \Kimb[i,j,r] \big\vert = \binom{i-1}{r} \cdot \binom{r+j}{r}.$$

Combined with Proposition <ref>, we immediately get the following.

Let $n \geq 1$ and $k,r \geq 0$ such that $k+r \leq n-1$. The following sets both have cardinality $\binom{n-k-1}{r} \cdot \binom{r+k}{r}$.

* The set of properly-marked $\{L,R\}$-words of length $(n-1)$ with $k$ marked elements and $r$ unmarked elements.

* The set of Kimberling paths ending at $(n-k,k)$ with $r$ internal vertices.

Combining with the results of Section <ref> gives us the following result, which was the main objective of this section.

Let $n \geq 1$ and $0 \leq k \leq n-1$. The following sets are equinumerous.

* The set of recurrent configurations $c \in \Rec[F_{n}]$ satisfying $\level(c) = k$.

* The set of subgraphs $G = (V,E)$ of the path graph $P_n$ such that $n \in V$ and $\vert E \vert = k$.

* The set $\Kimb[n-k,k]$ of Kimberling paths ending at $(n-k,k)$.

In particular, if $T_{F_n}$ is the Tutte polynomial of the fan graph $F_n$, we have:

$$ T_{F_n}(1,x) = \sum\limits_{k=0}^{n-1} \big\vert \Kimb[n-k,k] \big\vert \cdot x^k. $$

As far as we can tell, as in the wheel graph case, this specification of the Tutte polynomial for fan graphs has not been noted anywhere in the literature. Note that, unlike in the wheel graph case, we can give an explicit formula for the coefficients here:

$$ \big\vert \Kimb[n-k,k] \big\vert = \sum\limits_{r=0}^{n-k-1} \binom{n-k-1}{r} \cdot \binom{r+k}{r}. $$

As in the wheel graph case, it is possible to give an interpretation of the parameter $r$ in terms of certain $2\{1,2\}^*0$-chains of the corresponding recurrent configuration, with suitable precautions taken to deal with the end vertices $1$ and $n$.

As in Section <ref>, our proof of Theorem <ref> is not a direct bijection. Instead it relies on the fact that both objects are enumerated by the same formula (a product of binomial coefficients in this case). It would be useful to exhibit a direct bijection from either recurrent configurations on $F_n$ or properly-marked $\{L,R\}$-words to the Kimberling paths.

§ CONCLUSION AND FUTURE WORK

In this paper, we have studied the sandpile model on wheel and fan graphs, focusing on bijective characterisations of the recurrent configurations. These results are in the same spirit as a growing list of similar combinatorial characterisations on other graph families (see the list in Section <ref> for more details).

In the case of the wheel graph $W_n$, it proved helpful to consider a stochastic variant of the standard Abelian sandpile model (ASM). We described (Theorem <ref>) a bijection between the recurrent configurations and the set of non-empty subgraphs of the cycle graph $C_n$. This bijection maps the level of a configuration to the number of edges of the subgraph, and a statistic called the $01*$-weight of the configuration to the number of vertices absent from the subgraph. The tools used included a bijection between minimal recurrent configurations on the wheel graph and orientations of the cycle, which we enriched to a bijection between all recurrent configurations and properly-marked orientations of the cycle.

We then considered the special case where the wheel graph has an even number of vertices $2n$. We showed (Theorem <ref>) that the recurrent configurations with level $n$ are equinumerous with certain lattice paths called differed Delannoy paths. In this case, the $01*$-weight corresponds to the number of diagonal steps in the path. However, our proof of this result is non-bijective, relying instead on a variety of enumerative arguments. In the future, it would be useful to find a direct bijective proof of this result.

In the case of the fan graph $F_n$, we described (Theorem <ref>) a bijection between the recurrent configurations and subgraphs of the path graph $P_n$ whose vertex set contains the right-most vertex of the path. The bijection again maps the level of the recurrent configuration to the number of edges in the corresponding subgraph. The initial tools used are similar to the wheel graph case, relying on enriching a bijection between minimal recurrent configurations on the fan graph and orientations of the path graph, which yields a bijection between all the recurrent configurations and objects called properly-marked words. The bijection to the subgraphs of $P_n$ follows naturally. We then show that these sets are equinumerous with another family of lattice paths, which we called Kimberling paths, named after the author of the corresponding entry in the OEIS [29]. As in the wheel graph case, this proof is non-bijective, and in the future it would be useful to find a direct bijection instead.

Because of the well-known link between the enumeration of recurrent configurations for the ASM according to their level, and the ubiquitous polynomial (Theorem <ref>), these results yield specialisations of the Tutte polynomial of wheel and fan graphs. It would be interesting to investigate whether the bijective correspondences exhibited here can be enriched in some way to account for the second variable of the Tutte polynomial. This would potentially yield simpler and more explicit formulae for the Tutte polynomial of wheel and fan graphs than those that are currently known.

§ ACKNOWLEDGMENTS

The research leading to these results received funding from the National Natural Science Foundation of China (NSFC) under Grant Agreement No 12101505. In addition, we would like to thank the two anonymous referees for their many helpful comments and corrections, as well as the suggestion to look into subgraph characterisations of the recurrent configurations in the fan graph case.

[1]
Amal Alofi and Mark Dukes.
Parallelogram polyominoes and rectangular ew-tableaux:
Correspondences through the sandpile model.
Enumer. Combin. Appl., 1(1):Art–S2R8, 2018.

[2]
Jean-Christophe Aval, Michele D'Adderio, Mark Dukes, and Yvan Le
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]
Per Bak, Chao Tang, and Kurt Wiesenfeld.
Self-organized criticality: An explanation of the 1/f noise.
Phys. Rev. Lett., 59:381–384, 1987.

[4]
Per Bak, Chao Tang, and Kurt Wiesenfeld.
Self-organized criticality.
Phys. Rev. A (3), 38(1):364–374, 1988.

[5]
Matthew Baker and Serguei Norine.
Riemann-Roch and Abel-Jacobi theory on a finite graph.
Adv. Math., 215(2):766–788, 2007.

[6]
Cyril Banderier and Sylviane Schwer.
Why Delannoy numbers?
J. Stat. Plann. Inference, 135(1):40–54, 2005.

[7]
Olivier Bernardi.
Tutte polynomial, subgraphs, orientations and sandpile model: new
connections via embeddings.
Electron. J. Comb., 15(1):research paper r109, 53, 2008.

[8]
N. L. Biggs, R. M. Damerell, and D. A. Sands.
Recursive families of graphs.
J. Comb. Theory, Ser. B, 12:123–131, 1972.

[9]
Norman Biggs.
Chip-firing and the critical group of a graph.
J. Algebr. Comb., 9(1):25–45, 1999.

[10]
Norman Biggs.
The Tutte polynomial as a growth function.
J. Algebr. Comb., 10(2):115–133, 1999.

[11]
Anders Björner, László Lovász, and Peter W. Shor.
Chip-firing games on graphs.
Eur. J. Comb., 12(4):283–291, 1991.

[12]
C. Brennan, T. Mansour, and E. Mphako-Banda.
Tutte polynomials of wheels via generating functions.
Bull. Iran. Math. Soc., 39(5):881–891, 2013.

[13]
David Callan.
Some bijections for lattice paths, 2021.

[14]
Yao-Ban Chan, Jean-François Marckert, and Thomas Selig.
A natural stochastic extension of the sandpile model on a graph.
J. Comb. Theory, Ser. A, 120(7):1913–1928, 2013.

[15]
Haiyan Chen and Bojan Mohar.
The sandpile group of polygon rings and twisted polygon rings, 2020.

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

[17]
Robert Cori and Dominique Poulalhon.
Enumeration of \((p,q)\)-parking functions.
Discrete Math., 256(3):609–623, 2002.

[18]
Robert Cori and Dominique Rossin.
On the sandpile group of dual graphs.
Eur. J. Comb., 21(4):447–459, 2000.

[19]
Michele D'Adderio and Yvan Le Borgne.
The sandpile model on $ k\_m, n $ and the rank of its configurations.
Sém. Loth. Comb., 77:Art–B77h, 2018.

[20]
Arnaud Dartois, Francesca Fiorenzi, and Paolo Francini.
Sandpile group on the graph \(\mathcal D_n\) of the dihedral group.
Eur. J. Comb., 24(7):815–824, 2003.

[21]
Deepak Dhar.
Self-organized critical state of sandpile automaton models.
Phys. Rev. Lett., 64(14):1613–1616, 1990.

[22]
Deepak Dhar.
Theoretical studies of self-organized criticality.
Physica A, 369(1):29–70, 2006.
Fundamental Problems in Statistical Physics.

[23]
Mark Dukes.
The sandpile model on the complete split graph, Motzkin words, and
tiered parking functions.
J. Comb. Theory, Ser. A, 180:15, 2021.
Id/No 105418.

[24]
Mark Dukes and Yvan 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.

[25]
Mark Dukes, Thomas Selig, Jason P. Smith, and Einar Steingrímsson.
Permutation graphs and the abelian sandpile model, tiered trees and
non-ambiguous binary trees.
Electron. J. Comb., 26(3):research paper p3.29, 25, 2019.

[26]
Mark Dukes, Thomas Selig, Jason P. Smith, and Einar Steingrímsson.
The abelian sandpile model on Ferrers graphs – a classification of
recurrent configurations.
Eur. J. Comb., 81:221–241, 2019.

[27]
Curtis Greene and Thomas Zaslavsky.
On the interpretation of Whitney numbers through arrangements of
hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs.
Trans. Am. Math. Soc., 280:97–126, 1983.

[28]
Gábor Hetyei.
Central Delannoy numbers and balanced Cohen-Macaulay complexes.
Ann. Comb., 10(4):443–462, 2006.

[29]
The OEIS Foundation Inc.
The On-line Encyclopedia of Integer Sequences, 2022.

[30]
Seungki Kim and Yuntao Wang.
A stochastic variant of the abelian sandpile model.
J. Stat. Phys., 178(3):711–724, 2020.

[31]
Caroline J. Klivans.
The mathematics of chip-firing.
Boca Raton, FL: CRC Press, 2019.

[32]
S S Manna.
Two-state model of self-organized criticality.
Journal of Physics A: Mathematical and General,
24(7):L363–L369, apr 1991.

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

[34]
François Nunzi.
On the abelianity of the stochastic sandpile model, 2016.

[35]
Zahid Raza, Mohammed M. M. Jaradat, Mohammed S. Bataineh, and Faiz
On the sandpile model of modified wheels. II.
Open Math., 18:1531–1539, 2020.

[36]
Zahid Raza, Saleha Tariq, and M. Tariq Rahim.
Sandpile model on subdivided wheels \(W_{n,l}\).
Util. Math., 105:291–302, 2017.

[37]
Tridib Sadhu and Deepak Dhar.
Steady state of stochastic sandpile models.
J. Stat. Phys., 134(3):427–441, 2009.

[38]
Matthias Schulz.
Minimal recurrent configurations of chip firing games and directed
acyclic graphs.
In Automata 2010. Selected papers based on the presentations at
the 16th international workshop on cellular automata (CA) and discrete
complex systems (DCS), Nancy, France, June 14–16, 2010, pages 111–124.
Nancy: The Association. Discrete Mathematics & Theoretical Computer Science
(DMTCS), 2010.

[39]
Thomas Selig, Jason P. Smith, and Einar Steingrímsson.
EW-tableaux, Le-tableaux, tree-like tableaux and the abelian
sandpile model.
Electron. J. Comb., 25(3):research paper p3.14, 32, 2018.

[40]
Robert A. Sulanke.
Objects counted by the central Delannoy numbers.
J. Integer Seq., 6(1):art. 03.1.5, 19, 2003.

[41]
Yufang Zhou and Haiyan Chen.
The sandpile group of a family of nearly complete graphs.
Bull. Malays. Math. Sci. Soc. (2), 44(2):625–637, 2021.