Generalizations of chip-firing and the critical group
July 8 to July 12, 2013
American Institute of Mathematics,
San Jose, California
and James Propp
This workshop 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:
- 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?
- 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?
- 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?
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.
A list of open problems.
Papers arising from the workshop:
Fourientations and the Tutte Polynomial
by Spencer Backman and Sam Hopkins, Res. Math. Sci. 4 (2017), 4:18 MR3696165
Chip-firing and energy minimization on M-matrices
by Johnny Guzmán and Caroline Klivans, J. Combin. Theory Ser. A 132 (2015), 14-31 MR3311336
Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
by Lionel Levine, Comm. Math. Phys. 335 (2015), no. 2, 1003-1017 MR3316648
Abelian networks: foundations and examples
by Benjamin Bond and Lionel Levine, SIAM J. Discrete Math. 30 (2016), no. 2, 856-874 MR3493110
Rotor-routing and spanning trees on planar graphs
by Melody Chan, Thomas Church and Joshua A. Grochow, Int. Math. Res. Not. IMRN 2015, no. 11, 3225-3244 MR3373049
Critical Groups of Graphs with Dihedral Actions
by Darren Glass and Criel Merino, European J. Combin. 39 (2014), 95-112 MR3168517
The Bernardi process and torsor structures on spanning trees
by Matthew Baker and Yao Wang
Sandpiles, spanning trees, and plane duality
by Melody Chan, Darren Glass, Matthew Macauley, David Perkinson, Caryn Werner and Qiaoyu Yang, SIAM J. Discrete Math. 29 (2015), no. 1, 461-471 MR3319526
G-parking functions and tree inversions
by David Perkinson, Qiaoyu Yang and Kuai Yu, Combinatorica 37 (2017), no. 2, 269–282 MR3638345