Abelian sandpiles, spanning trees, and loop-erased random walk

Frank Redig

I will give an introduction to the ``abelian sandpile model" (ASM). In this model to every vertex i of a finite subset V of Zd we associate a integer valued height variable hi>0 (``the number of grains at i"). If hi < 2d+1 the site is called stable. An unstable configuration is stabilized by a sequence of ``topplings" consisting of removing 2d grains from unstable sites and giving one grain to each neighbor. In the ASM dynamics, one picks a vertex at random, adds a grain and stabilizes the configuration.

The recurrent configurations of ASM form an abelian group (under pointwise addition and stabilization). They can also be characterized by an algorithm which gives a bijection to the set of rooted spanning trees on V. The effect of adding one grain to a recurrent configuration can be characterized by a sequence of ``waves", each of which can be represented by a two component spanning tree. Spanning trees are related to loop-erased random walk via Wilson's algorithm.

If time is left, I will discuss some recent results for the ASM on infinite graphs.

back to TU/e Combinatorial Theory Seminar announcements