''The Mathematics of Chip-Firing'' is a textbook in mathematics on

chip-firing game The chip-firing game is a one-player game on a graph which was invented around 1983 and since has become an important part of the study of structural combinatorics. Each vertex has the number of "chips" indicated by its state variable. On each ...

s and

abelian sandpile model The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, ...

s. It was written by Caroline Klivans, and published in 2018 by the

CRC Press The CRC Press, LLC is an American publishing group that specializes in producing technical books. Many of their books relate to engineering, science and mathematics. Their scope also includes books on business, forensics and information tec ...

Topics

A chip-firing game, in its most basic form, is a process on an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

, with each

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

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 In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...

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 In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplac ...

of the given graph. It describes an equivalence between states of the sandpile group and the

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

s 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 Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algeb ...

. And it studies chip-firing games on other classes of graphs than grids, including

random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs li ...

s. 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 system In mathematics, a root system is a configuration of vectors in a Euclidean space satisfying certain geometrical properties. The concept is fundamental in the theory of Lie groups and Lie algebras, especially the classification and representati ...

s and

representation theory Representation theory is a branch of mathematics that studies abstract algebraic structures by ''representing'' their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures. In essen ...

. 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 In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...

and the

Riemann–Roch theorem The Riemann–Roch theorem is an important theorem in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeros and allowed poles. It rel ...

. And the fourth applies methods from

commutative algebra Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prominent ...

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 Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...

than combinatorics.

References

{{DEFAULTSORT:Mathematics of Chip-Firing, The Graph theory Cellular automata Critical phenomena Mathematics textbooks 2018 non-fiction books CRC Press books