Sandpiles

Sandpiles

The Abelian Sandpile Model (ASM) was created by Dhar in 1990. It is a generalization of the sandpile model proposed by Bak-Tang-Wiesenfeld (1987) as an example of self-organized criticality, having especially nice mathematical properties. The ASM is connected to a wide range of mathematics: markov processes and statistical mechanics, combinatorics (tilings, the Tutte polynomial, parking functions, the matrix-tree theorem), algebraic geometry (lattice ideals), graph analogues to Riemann surfaces, and tropical geometry.

Google Summer of Code

Sage Sandpiles: a package for doing sandpile calculations

Sage is an open-source alternative to Mathematica, Maple, Matlab, etc. To read about Sage, try it online, and download it for free, visit the Sage homepage. It runs under Linux, Mac OSX, and Windows. The following is a Sage package for doing sandpile calculations on directed multigraphs, including: recurrent and superstable elements, identity elements, burning configurations, vertex firings, sandpile ideals, resolutions, Hilbert functions, Betti numbers, effective divisors, and linear systems.

Download Version 1.51 (July 15, 2009)

Literature

Links to papers I find especially interesting.

Chip-Firing and Rotor-Routing on Directed Graphs, Holroyd, Levine, Meszaros, Peres, Propp, Wilson. The final version of this paper appears in In and out of Equilibrium II, Eds. V. Sidoravicius, M. E. Vares, in the Series Progress in Probability, Birkhauser (2008). This is my recommendation for an introduction to the subject (along with Babai's notes and Dhar's 2006 paper referenced below).
D. Dhar
- Exactly Solved Models of Self-Organized Criticality, Physica A 369 (2006).
- The abelian sandpile and related models, Physica A 263 (1999)
- Algebraic Aspects of Abelian Sandpile Models, TIFR/TH/94-30
M. Baker
- Riemann-Roch and Abel-Jacobi Theory on a Finite Graph, with Serguei Norine, Advances in Mathematics 215 (2007), 766--788.
- Specialization of Linear Systems from Curves to Graphs, Algebra & Number Theory 2, no. 6 (2008), 613--653.
- Harmonic Morphisms and Hyperelliptic Graphs, with Serguei Norine,(2008)
A Riemann-Roch theorem in tropical geometry, Gathmann, Kerber (2007)
J. Ellis-Monaghan and C. Merino
- Graph polynomials and their applications I: The Tutte polynomial, (2008)
- Graph polynomials and their applications II: Interrelations and interpretations, (2008)
Polynomial Ideals for Sandpiles and their Grobner Bases, Cori, Rossin, Salvy, INRIA (2000)
Babai's 2005 REU lecture notes on sandpiles
Asymmetric Abelian sandpile models, preprint of E. Speer's paper in J. Stat. Phys. 71 (1993), 61-74. This paper contains a generalization of Dhar's burning algorithm to directed graphs.

Course

In the fall of 2008, I taught an undergraduate course at Reed College on sandpiles. It covered the following topics:

The sandpile group: stabilization, recurrent configurations, the Laplacian, Smith normal form.
Matrix tree theorem for weighted directed graphs.
A variation on Speer's script algorithm, generalizing Dhar's burning algorithm.
The relation of sandpiles to tilings.
Algebraic geometry of sandpiles: Groebner bases for sandpile ideals (generalized to directed graphs), structure of the solution set to the sandpile equations, lattice ideals.
Riemann-Roch for graphs: an overview of the work of Baker et al.
Miscellaneous topics: Turing machines and sandpiles, duality, the Tutte polynomial, G-invariant configurations, parking functions.

Here is a link to the course webpage. The course materials will be made available (lecture notes) after they have been edited.

Algebraic Geometry

Here is a link to a primer on the algebraic geometry of sandpiles.

Applets/Java

Bryan Head is creating a sandpile computer application for a 2009 Google Summer of Code project. Your can participate. Please follow the given link to the project homepage, try out the prototype, and send us comments. Requests for features would be much appreciated.
Sergei Maslov's Sandpile applet.
A visualization of the chip-firing game, by Adam Tart.