On graph parameters guaranteeing fast sandpile diffusion

Ayush Choure¹ ; Sundar Vishwanathan¹

¹Indian Institute of Technology Bombay, India

The electronic journal of combinatorics, Tome 22 (2015) no. 1

Résumé

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.

Détail

DOI : 10.37236/2898

Classification : 05C81, 05C25, 05C90, 82C20
Mots-clés : abelian sandpile model, harmonic functions on graphs, diffusion