AIM logo

Generalizations of chip-firing and the critical group

July 8 to July 12, 2013

at the

American Institute of Mathematics, Palo Alto, California

organized by

Lionel Levine, Jeremy Martin, David Perkinson, and James Propp

This workshop, sponsored by AIM and the NSF, will center around the abelian sandpile model and related chip-firing games on graphs, including generalizations to higher dimension, abelian networks, and pattern formation. The abelian sandpile model is a crossroads for a wide range of mathematics: Markov processes and statistical mechanics, combinatorics, algebraic geometry, graph analogues to Riemann surfaces, and tropical geometry. This workshop will bring together mathematicians from a variety of fields---including probability theory, combinatorics, and algebraic geometry---to apply a variety of viewpoints to a few specific problems. The topics of the workshop will be:

  1. Chip-firing in higher dimensions.

    Building on the work of Duval, Klivans, and Martin, we would like to develop a theory of chip-firing for general simplicial or CW-complexes. Is there a generalization of the Baker-Norine theorem to higher dimensions---perhaps a "combinatorial Hirzebruch-Riemann-Roch theorem"? Are there appropriate generalizations of the recurrent elements of the abelian sandpile model? What are the implications of a higher-dimensional theory for combinatorics?

  2. Abelian networks.

    Abelian networks, proposed by Dhar and developed by Bond and Levine, are systems of communicating finite automata satisfying a certain local commutativity condition. As a model of computation, they implement asynchronous algorithms on graphs. The two most widely studied examples of abelian networks are the abelian sandpile model and the rotor-router or Eulerian walkers model. How much more general are abelian networks than these? Is there a computational hierarchy within the class of abelian networks? Is the halting problem for abelian networks decidable in polynomial time?

  3. Pattern formation.

    How can one rigorously identify and classify the rich patterns that arise in identity elements of critical groups? Can the proof of existence of the sandpile scaling limit by Pegden and Smart be adapted to prove properties of the limit? Ostojic has given a heuristic, involving the conformal map $z\mapsto 1/z^2$, for the locations and features of certain sandpile patterns. Can these heuristics be converted into precise conjectures, and what tools would be required to prove these conjectures?

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Go to the list of upcoming workshops.