The Mathematics of Chip-Firing

The Mathematics of Chip-Firing is a textbook in mathematics on chip-firing games and abelian sandpile models. It was written by Caroline Klivans, and published in 2018 by the CRC Press.

Topics

The identity element of an abelian sandpile model

A chip-firing game, in its most basic form, is a process on an undirected graph, with each vertex of the graph containing some number of chips. At each step, a vertex with more chips than incident edges is selected, and one of its chips is sent to each of its neighbors. If a single vertex is designated as a "black hole", meaning that chips sent to it vanish, then the result of the process is the same no matter what order the other vertices are selected. The stable states of this process are the ones in which no vertex has enough chips to be selected; two stable states can be added by combining their chips and then stabilizing the result. A subset of these states, the so-called critical states, form an abelian group under this addition operation. The abelian sandpile model applies this model to large grid graphs, with the black hole connected to the boundary vertices of the grid; in this formulation, with all eligible vertices selected simultaneously, it can also be interpreted as a cellular automaton. The identity element of the sandpile group often has an unusual fractal structure.

The book covers these topics, and is divided into two parts. The first of these parts covers the basic theory outlined above, formulating chip-firing in terms of algebraic graph theory and the Laplacian matrix of the given graph. It describes an equivalence between states of the sandpile group and the spanning trees of the graph, and the group action on spanning trees, as well as similar connections to other combinatorial structures, and applications of these connections in algebraic combinatorics. And it studies chip-firing games on other classes of graphs than grids, including random graphs.

The second part of the book has four chapters devoted to more advanced topics in chip-firing. The first of these generalizes chip-firing from Laplacian matrices of graphs to M-matrices, connecting this generalization to root systems and representation theory. The second considers chip-firing on abstract simplicial complexes instead of graphs. The third uses chip-firing to study graph-theoretic analogues of divisor theory and the Riemann–Roch theorem. And the fourth applies methods from commutative algebra to the study of chip-firing.

The book includes many illustrations, and ends each chapter with a set of exercises making it suitable as a textbook for a course on this topic.

Audience and reception

Although the book may be readable by some undergraduate mathematics students, reviewer David Perkinson suggests that its main audience should be graduate students in mathematics, for whom it could be used as the basis of a graduate course or seminar. He calls it "a thorough introduction to an exciting and growing subject", with "clear and concise exposition". Reviewer Paul Dreyer calls it a "deep dive" into "incredibly deep mathematics".

Another book on the same general topic, published at approximately the same time, is Divisors and Sandpiles: An Introduction to Chip-Firing by Corry and Perkinson (American Mathematical Society, 2018). It is written at a lower level aimed at undergraduate students, covering mainly the material from the first part of The Mathematics of Chip-Firing, and framed more in terms of algebraic geometry than combinatorics.