论文标题
完整图上的随机砂液模型
The stochastic sandpile model on complete graphs
论文作者
论文摘要
随机砂液模型（SSM）是标准的Abelian砂型模型（ASM）的概括，其中使不稳定顶点的拨号随机。如果不稳定，一个顶点将以（0,1）$的概率$ p \独立地向其每个邻居发送一个谷物。我们在完整图上研究SSM。我们的主要结果是对模型的复发状态的描述。我们表明，这些是由ASM的凸面态总和给出的。这使我们能够恢复一个众所周知的结果：$ n $维置置换式多层的整数晶格点数量等于$ n $顶点上标记的跨越森林的数量。我们还提供了DHAR燃烧算法的随机版本，以检查给定（稳定）状态是否经常性，该状态在线性时间内运行。最后，我们研究了一个所谓的“部分” SSM的家族，其中一些顶点随机倾倒，而另一些顶点则是确定性的（如在ASM中，向所有邻居发送了一种谷物）。我们表明，这种区别是有意义的，产生了与ASM和SSM相同的复发状态集。我们还表明，要获得SSM的所有经常性状态，我们最多可以允许两个顶点确定地推翻。
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 \in (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.
