On Graph Parameters Guaranteeing Fast Sandpile Diffusion

  • Ayush Choure
  • Sundar Vishwanathan
Keywords: Abelian Sandpile Model, Harmonic functions on graphs, Diffusion

Abstract

The Abelian Sandpile Model (Dhar 1990) is a discrete diffusion process, defined on graphs, which serves as the standard model of self-organized criticality. One is allowed to add sand particles on the nodes of the graph such that each node can stably hold at most some bounded number of particles. The particles flow through the graph as a consequence of surpassing the node capacities, until they reach a special sink node possessing infinite capacity. These simple dynamics give rise to a very interesting Markovian system. The transience class of a sandpile is defined as the maximum number of particles that can be added without making the system recurrent. We identify a small set of key graph properties that guarantee polynomial bounds on transience classes of the sandpile families satisfying them. These properties governing the speed of sandpile diffusion process are volume growth parameters, boundary regularity type properties and non-empty interior type constraints.

This generalizes a previous result by Babai and Gorodezky (2007), in which they establish polynomial bounds on the $n\times n$ grid. Indeed the properties we show are based on ideas extracted from their proof as well as the continuous analogs in the theory of harmonic functions.

Published
2015-02-25
Article Number
P1.44