2012/07/02 by Ayush Choure, Choure, Ayush, Sundar Vishwanathan +1
Computer Science · Mathematics · Physics and Astronomy · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #Mathematical Physics (math-ph) #cs.DM #math-ph #math.MP
paper · pdf · doi:10.48550/arxiv.1207.0421
26 pages, 11 figures
arxiv created 2012/11/01 · arxiv updated 2012/11/02
The Abelian Sandpile Model is a discrete diffusion process defined on graphs (Dhar \citeDD90, Dhar et al. \citeDD95) which serves as the standard model of 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 (\citeBT05). We demonstrate a 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,\citeLB07), in which they establish polynomial bounds on n × n grid. Indeed the properties we show are based on ideas extracted from their proof as well as the continuous analogs in complex analysis. We conclude with a discussion on the notion of degeneracy and dimensions in graphs.