1210.4327 (Ayush Choure et al.)

Improved bounds on the sandpile diffusions on Grid graphs    [PDF]

Ayush Choure, Sundar Vishwanathan

The Abelian Sandpile Model is a discrete di?usion process de?ned on graphs (Dhar [10], Dhar et al. [11]) which serves as the standard model of self-organized criticality. The transience class of a sandpile is de?ned as the maximum number of particles that can be added without making the system recurrent ([3]). Using elementary combinatorial arguments and symmetry properties, Babai and Gorodezky (SODA 2007,[2]) demonstrated a bound of O(n^30) on the transience class of an n?xn grid. This was later improved by Choure and Vishwanathan (SODA 2012,[7]) to O(n^7) using techniques based on harmonic functions on graphs. We improve this bound to O(n^7 log n). We also demonstrate tight bounds on certain resistance ratios over grid networks. The tools used for deriving these bounds may be of independent interest.

View original: http://arxiv.org/abs/1210.4327