Divisors and Sandpiles:
An Introduction to Chip-Firing

Divisors and Sandpiles: An Introduction to
	Chip-Firing

Divisors and Sandpiles provides an introduction to the combinatorial theory of chip-firing on finite graphs. Part 1 motivates the study of the discrete Laplacian by introducing the dollar game. The resulting theory of divisors on graphs runs in close parallel to the geometric theory of divisors on Riemann surfaces, and Part 1 culminates in a full exposition of the graph-theoretic Riemann-Roch theorem due to M. Baker and S. Norine. The text leverages the reader's understanding of the discrete story to provide a brief overview of the classical theory of Riemann surfaces.

Part 2 focuses on sandpiles, which are toy models of physical systems with dynamics controlled by the discrete Laplacian of the underlying graph. The text provides a careful introduction to the sandpile group and the abelian sandpile model, leading ultimately to L. Levine's threshold density theorem for the fixed-energy sandpile Markov chain. In a precise sense, the theory of sandpiles is dual to the theory of divisors, and there are many beautiful connections between the first two parts of the book.

Part 3 addresses various topics connecting the theory of chip-firing to other areas of mathematics, including the matrix-tree theorem, harmonic morphisms, parking functions, M-matrices, matroids, the Tutte polynomial, and simplicial homology.

The text is suitable for advanced undergraduates and beginning graduate students.

Contents
Part 1. Divisors
Chapter 1. The dollar game
  • An initial game
  • Formal definitions
  • The Picard and Jacobian groups
  • Notes
  • Problems
Chapter 2. The Laplacian
  • The discrete Laplacian
  • Configurations and the reduced Laplacian
  • Complete linear systems and convex polytopes
  • Structure of the Picard group
  • Notes
  • Problems
Chapter 3. Algorithms for winning
  • Greed
  • q-reduced divisors
  • Superstable configurations
  • Dhar's algorithm and efficient implementation
  • The Abel-Jacobi map
  • Notes
  • Problems
Chapter 4. Acyclic orientations
  • Orientations and maximal unwinnables
  • Dhar's algorithm revisited
  • Notes
  • Problems
Chapter 5. Riemann-Roch
  • The rank function
  • Riemann-Roch for graphs
  • The analogy with Riemann surfaces
  • Alive divisors and stability
  • Notes
  • Problems
Part 2. Sandpiles
Chapter 6. The sandpile group
  • A first example
  • Directed graphs
  • Sandpile graphs
  • The reduced Laplacian
  • Recurrent sandpiles
  • Images of sandpiles on grid graphs
  • Notes
  • Problems
Chapter 7. Burning and duality
  • Burning sandpiles
  • Existence and uniqueness
  • Superstables and recurrents
  • Forbidden configurations
  • Dhar's burning algorithm for recurrents
  • Notes
  • Problems
Chapter 8. The threshold density theorem
  • Markov Chains
  • The fixed-energy sandpile
  • The threshold density theorem
  • Notes
  • Problems
Part 3. Topics
Chapter 9. Trees
  • The matrix-tree theorem
  • Consequences of the matrix-tree theorem
  • Tree bijections
  • Notes
  • Problems
Chapter 10. Harmonic morphisms
  • Morphisms between graphs
  • Branched coverings of Riemann surfaces
  • Household-solutions to the dollar game
  • Notes
  • Problems
Chapter 11. Divisors on complete graphs
  • Parking functions
  • Computing ranks on complete graphs
  • Notes
  • Problems
Chapter 12. More about sandpiles
  • Changing the sink
  • Minimal number of generators for \(\mathcal{S}(G)\)
  • \(M\)-matrices
  • Self-organized criticality
  • Notes
  • Problems
Chapter 13. Cycles and cuts
  • Cycles, cuts, and the sandpile group
  • Planar duality
  • Notes
  • Problems
Chapter 15. Matroids and the Tutte polynomial
  • Matroids
  • The Tutte polynomial
  • 2-isomorphisms
  • Merino's Theorem
  • Tutte polynomials of complete graphs
  • The \(h\)-vector conjecture
  • Notes
  • Problems
Chapter 16. Higher dimensions
  • Simplicial homology
  • Higher-dimensional critical groups
  • Simplicial spanning trees
  • Firing rules for faces
  • Notes
  • Problems
Appendices
Appendix A.
  • Undirected multigraphs
  • Directed multigraphs
Appendix B.
  • Monoids, groups, rings, fields
  • Modules
Glossary of symbols
Bibliography
Index