KTH/SU Mathematics Colloquium
2005-02-02
Donald Knuth, Stanford University
Sand Piles and Spanning Trees
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.