Ayush Choure, Sundar Vishwanathan
The Abelian Sandpile Model is a discrete diffusion process defined on graphs (Dhar \cite{DD90}, Dhar et al. \cite{DD95}) which serves as the standard model of \textit{self-organized criticality}. The transience class of a sandpile is defined as the maximum number of particles that can be added without making the system recurrent (\cite{BT05}). We demonstrate a large class of sandpile which have polynomially bound transience classes by identifying key graph properties that play a role in the rapid diffusion process. These are the volume growth parameters, boundary regularity type properties and non-empty interior type constraints. This generalizes a previous result by Babai and Gorodezky (SODA 2007,\cite{LB07}), in which they establish polynomial bounds on $n \times n$ grid. Indeed the properties we show are based on ideas extracted from their proof as well as the continuous analogs in complex analysis. For degree bounded graphs, we demonstrate the first constant factor approximation algorithm for the transience class problem, based on harmonic functions. This algorithm is used in an essential way in proving the impulse superposition properties, which in turn help us derive the polynomial bounds. We conclude with a discussion on the notion of degeneracy and dimensions in graphs.
View original:
http://arxiv.org/abs/1207.0421
No comments:
Post a Comment