Donald Knuth: Sand Piles and Spanning Trees February 2, 2005

Physicists have proposed a general "sand pile" model that applies to any connected graph: Each vertex of the graph is assumed to contain grains of sand. If a vertex has d neighbors and contains at least d grains of sand, it "topples" by transferring one grain of sand to each of its neighbors. A sequence of topplings is called an "avalanche". One vertex is, however, special; it doesn't topple, it just accumulates more and more sand. Every avalanche then leads to a stable state after finitely many steps.

Amazingly, the number of recurrent stable states of this system turns out to be the same as the number of spanning trees of the graph. In this talk, the speaker will describe an interesting algorithm by means of which we can associate a unique recurrent state to each spanning tree.

KTH/SU Mathematics Colloquium