Departmental Colloquium
Laszlo Babai
University of Chicago
The Abelian Sandpile Model
Abstract: In an unusual confluence of concepts emerging from a diverse set
of areas about 15 years ago, 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): a commutative
monoid (the "sandpile monoid") on the set of stable configurations;
and an abelian group, the "sandpile group," on the important subset of
"recurrent configurations." The sandpile group, which is the unique
mimimal ideal of the sandpile monoid, is a particularly intriguing
algebraic invariant of the graph. It is related to the lattice
generated by the rows of the reduced Laplacian of the graph; and
from this connection it follows that its order is the number of
spanning trees of the graph, thus adding group structure to
Kirchhoff's celebrated "matrix-tree theorem" (1848).
After a general introduction to the subject along the lines of
joint work with Evelina Toumpakari, I will mention recent
work on the "transience class" of a graph, i.e., the maximum number
of grains that can be added to the empty configuration before it
becomes recurrent. This number is also the nilpotence class of a
related semigroup. While this number can be exponentially large
compared to the size of the underlying graph, we prove that for
the particularly interesting case of the square grid, it is
polynomially bounded. This result is joint work with Igor Gorodezky.
Open problems of diverse nature arise; they involve statistics,
dynamical systems, algebra, number theory, algorithms and
computational complexity.
Friday December 8, 2006 at 3:00 PM in SEO 636