Avalanches, Sandpiles and Tutte Decomposition

Sandpile and avalanche models of failure were introduced recently (Bak et al., 1987, and an avalanche of publications with references to this paper) to simulate processes of different nature (earthquakes, charge density waves, forest fires, etc., including economics) characterized by self-organized critical behavior. Statistical properties of an important class of these models, abelian sandpiles (Dhar, 1990) and abelian avalanches (Gabrielov, 1992), can be investigated analytically due to an abelian group acting on the phase space. It is shown that the distribution of avalanches in a discrete, stochastic abelian sandpile model is identical to the distribution of avalanches in a continuous, deterministic abelian avalanche model with the same redistribution matrix and loading rate vector. For a symmetric redistribution matrix, recurrent formulas for the distribution of avalanches in the abelian avalanche model lead to explicit expressions containing invariants of graphs known as Tutte polynomials. In general case, an analog of the Tutte decomposition is suggested for matrices and directed graphs, and the corresponding expressions for the distribution of avalanches in terms of directed tree numbers of a directed graph are found. New combinatorial identities for graphs and directed graphs are derived from these formulas.