NB: A PDF version of this announcement (suitable for posting) is also available.

The Abelian Sandpile Model

Laszlo Babai
University of Chicago

Thursday, April 10, 2008
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall

Abstract: In an unusual confluence of concepts emerging from a diverse set of areas in the past two decades, the Abelian Sandpile Model offers a rich structure studied by communities in statistical physics, probability theory, algebraic combinatorics, theoretical computer science, discrete dynamical systems.

The process under consideration takes a connected graph, puts "grains of sand" on each "site" (node); when the "pile" at a site gets too tall, it "topples," passing a grain to each neighbor. One of the sites is a "sink;" it swallows all the grains that reach it. We repeat the process until the configuration stabilizes ("avalanche"). Then we add another grain at some site and start all over. The process was introduced in 1988 by Bak, Tang, and Wiesenfeld as a model of the phenomenon of "self-organized criticality" in statistical physics. The evolution of the system is a "visual feast" (Creutz, 1991); the images show largely unexplored fractal phenomena.

The study of this diffusion process has led to the assignment of algebraic structures to (rooted) graphs (Dhar, 1990) and the discovery of surprising connections, including the fact that the number of "recurrent states" of the system is the number of spanning trees of the underlying graph.

After a general introduction to the subject along the lines of joint work with Evelina Toumpakari, we shall mention recent work on the "transience class" of a graph (joint work with Igor Gorodezky).

We shall conclude with open problems regarding the algorithmic aspects of the model, touching upon the intriguing relationship between the concepts of "good characterization" and "efficient solvability" central to combinatorial optimization.

This talk will be accessible to graduate students.