On the Abelian Sandpile Model
Evelina Toumpakari, Math Department, University of Chicago
November 5, 2004

Abstract

Motivated by statistical physics (self-organized criticality), the abeliansandpile automaton is a variant of the chip-firing game studied by Bjorner, Lovasz, Shor, E. Tardos, G. Tardos, and others. We take a rooted directed graph X in which the root is accessible from every vertex. Every ordinary (non-root) vertex has an associated pile of identical grains. When the height h(i) of the pile at an ordinary vertex i reaches its outdegree deg(i), the vertex i "topples," i.e., passes deg(i) grains to its out-neighbors, one along each outgoing edge. Grains passed to the root disappear; therefore, every toppling sequence ("avalanche") is finite. A state is "stable" if h(i) < deg(i) for each ordinary vertex i.

Dhar and Lovasz at al showed that the stable state reached after an avalanche depends solely on the initial state. This permits to define addition on the set S of stable states, by adding pointwise and toppling. States reachable from every state are called recurrent. (S,+) is a commutative semigroup; the recurrent states form a subgroup G, the "sandpile group" of X (Dhar, 1990). The order of G is the number of directed spanning trees oriented toward the root; this is also the determinant of the truncated Laplacian of X. The defining relations of G correspond to the rows of the truncated Laplacian.

We study combinatorial, algebraic, and algorithmic aspects of this model. We relate the structure of S to the structure of X. We consider a number of related algorithmic questions, several of which have an unresolved complexity status. We describe the structure of G in detail for the case when X is a ball in a regular tree plus a root connected to the leaves.

Some of the results are joint work with Laszlo Babai The speaker's advisor is Steven Lalley.