On graph parameters guaranteeing fast sandpile diffusion (Q2260617)

Summary: The abelian sandpile model 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 \textit{L. Babai} and \textit{I. Gorodezky} [in: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7--9, 2007. New York, NY: Association for Computing Machinery (ACM). 627--636 (2007; Zbl 1302.82065)], 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.