TY - JOUR
T1 - The Stochastic Sandpile Model on Complete Graphs
AU - Selig, Thomas
N1 - Publisher Copyright:
© The author.
PY - 2024/9/6
Y1 - 2024/9/6
N2 - The stochastic sandpile model (SSM) is a generalisation of the standard Abelian sandpile model (ASM), in which topplings of unstable vertices are made random. When unstable, a vertex sends one grain to each of its neighbours independently with probability p ∈ (0, 1). We study the SSM on complete graphs. Our main result is a description of the recurrent states of the model. We show that these are given by convex sums of recurrent states for the ASM. This allows us to recover a well-known result: that the number of integer lattice points in the n-dimensional permutation polytope is equal to the number of labeled spanning forests on n vertices. We also provide a stochastic version of Dhar’s burning algorithm to check if a given (stable) state is recurrent or not, which runs in linear time. Finally, we study a family of so-called partial SSMs, in which some vertices topple randomly, while others topple deterministically (as in the ASM, sending one grain to all neighbours). We show that this distinction is meaningful, yielding sets of recurrent states that are in general different from those of both the ASM and SSM. We also show that to get all recurrent states of the SSM, we can allow up to two vertices to topple deterministically.
AB - The stochastic sandpile model (SSM) is a generalisation of the standard Abelian sandpile model (ASM), in which topplings of unstable vertices are made random. When unstable, a vertex sends one grain to each of its neighbours independently with probability p ∈ (0, 1). We study the SSM on complete graphs. Our main result is a description of the recurrent states of the model. We show that these are given by convex sums of recurrent states for the ASM. This allows us to recover a well-known result: that the number of integer lattice points in the n-dimensional permutation polytope is equal to the number of labeled spanning forests on n vertices. We also provide a stochastic version of Dhar’s burning algorithm to check if a given (stable) state is recurrent or not, which runs in linear time. Finally, we study a family of so-called partial SSMs, in which some vertices topple randomly, while others topple deterministically (as in the ASM, sending one grain to all neighbours). We show that this distinction is meaningful, yielding sets of recurrent states that are in general different from those of both the ASM and SSM. We also show that to get all recurrent states of the SSM, we can allow up to two vertices to topple deterministically.
UR - http://www.scopus.com/inward/record.url?scp=85203395360&partnerID=8YFLogxK
U2 - 10.37236/12780
DO - 10.37236/12780
M3 - Article
AN - SCOPUS:85203395360
SN - 1077-8926
VL - 31
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 3
M1 - P3.26
ER -