You are here

The Mathematics of Chip-Firing

Caroline J. Klivans
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2018
Number of Pages: 
295
Format: 
Paperback
Series: 
Discrete Mathematics and Its Applications
Price: 
119.95
ISBN: 
9781138634091
Category: 
Textbook
[Reviewed by
David Perkinson
, on
08/31/2019
]
Chip-firing is a discrete dispersion process on a graph. It has arisen in a variety of mathematical fields over the last 30 years, gradually coalescing into a coherent collection of ideas. This delightful book presents those ideas carefully and elegantly, and it serves as a snapshot of the state of the art.
 
To get the basic idea of chip-firing, start with a finite, undirected, and connected graph. A chip configuration is formed by placing a number of chips on each vertex. By the most usual dispersion rule, governed by the discrete Laplacian operator of the graph, if a vertex has at least as many chips as it has neighboring vertices, it is unstable and fires one of its chips to each neighbor. Firing a vertex may cause a neighbor to become unstable and thus set off an avalanche of firings. Depending on the initial configuration, repeated firings may lead to a stable configuration—one in which each vertex has fewer chips than the number of its neighbors.
 
The designation of a "sink" vertex, which never fires but instead absorbs all the chips it receives, guarantees that every chip configuration has a unique stabilization, independent of the order in which unstable vertices are fired along the way. Thus, one may define an addition operation on the set of stable chip configurations: to add two configurations, stabilize their vertex-wise sum. Restricting addition to a certain class of critical configurations yields a central object of study in chip-firing: the sandpile group of the graph, which is isomorphic to the torsion part of the cokernel of the integer Laplacian matrix. As a first indication of the fascinating properties of this group, it turns out that it is not straightforward to describe its identity element! On a large grid graph, for instance, the identity has a beautiful, intricate, fractal-like structure.
 
The first part of The Mathematics of Chip-Firing covers the fundamentals of chip-firing with pointers to the broader literature. Some highlights:
 
  • Existence and uniqueness of stabilizations, with and without a sink.
  • The Laplacian operator and its relation to the sandpile group.
  • Combinatorial bijections between the sandpile group and the set of spanning trees of the graph, and the awe-inspiring free and transitive sandpile group action on spanning trees provided by the rotor-router model.
  • Chip-firing's connection to a wide variety of combinatorial structures in addition to spanning trees, including hyperplane arrangements, parking functions, graph orientations, and domino tilings.
  • Merino's theorem that a restriction of the Tutte polynomial of the graph is a generating function for a key statistic associated with elements of the sandpile group, ultimately leading to a proof of Stanley's h-vector conjecture for cographic matroids.​
  • The structure of the sandpile group for some classes of graphs, including (Erdős-Rényi) random graphs.
  • The beginnings of understanding pattern formation in large-scale chip-firing configurations.
 
The second part of the book consists of four chapters, each extending the theory covered in part one:
 
M-matrices. The Laplacian, which drives the chip-firing in part one, belongs to a larger class of matrices, called M-matrices, satisfying certain positivity conditions. Many aspects of chip-firing theory carry over if one replaces the Laplacian with an arbitrary M-matrix. This more general theory allows one to apply chip-firing methods to crystallographic root systems and to the complex representations of finite groups.
 
Higher dimensions. Chip-firing extends to higher-dimensional simplicial complexes. For instance, on a triangulated surface one may consider placing chips, better thought of as "flow", on the edges. Firing an edge diverts the flow around incident faces. The sandpile group generalizes to this setting and is related to higher-dimensional spanning trees.
 
Riemann-Roch theory. Another guise for chip-firing is the divisor theory of graphs, which views a graph as a discrete version of a Riemann surface. The book introduces divisor theory up through a proof of Baker and Norine's Riemann-Roch theorem for graphs. It goes on to describe the connection with tropical geometry, with Lorenzini's arithmetical structures, and with a Riemann-Roch theory for lattices.
 
Commutative algebra. The tools of commutative algebra may be brought to bear on chip-firing. Here, a chip configuration is encoded as the exponent vector of a monomial in a polynomial ring, and firings are encoded in a binomial ideal called the toppling ideal. A central result is Wilmes' theorem describing the Betti numbers of the free resolution of the toppling ideal in terms of the combinatorics of the underlying graph.
 
This book is accessible to beginning graduate students and some advanced undergraduates. It would be suitable for a semester-long graduate course or seminar. Besides those wanting a firm foundation in the subject, the book is also easy to skim, and thus should appeal to anyone wanting to get a flavor of the subject. Many exercises and several open questions are provided.
 
The Mathematics of Chip-Firing is a thorough introduction to an exciting and growing subject, written by an expert with a gift for clear and concise exposition. I enthusiastically recommend it.
David Perkinson (davidp@reed.edu) is the F.L. Griffin Professor of Mathematics at Reed College in Portland, OR. 

Introduction

A brief introduction. Origins/History.

 

Chip-firing on Finite Graphs

The chip-firing process. Confluence. Stabilization. Toppling time. Stabilization with a sink. Long-term stable configurations. The sandpile Markov chain.

 

Spanning Trees

Spanning trees. Statistics on Trees. Merino’s Theorem. Cori-Le Borgne bijection. Acyclic orientations. Parking functions. Dominoes. Avalanche polynomials.

 

Sandpile Groups

Toppling dynamics. Group of chip-firing equivalence. Identity. Combinatorial invariance. Sandpile groups and invariant factors. Discriminant groups. Sandpile torsors.

 

Pattern Formation

Compelling visualizations. Infinite graphs. The one-dimensional grid. Labeled chip-firing. Two and more dimensional grids. Other lattices. The identity element.

 

Avalanche Finite Systems

M-matrices. Chip-firing on M-matrices. Stability. Burning. Directed graphs. Cartan matrices as M-matrices. M-pairings.

 

Higher Dimensions

An illustrative example. Cell complexes. Combinatorial Laplacians. Chip-firing in higher dimensions. The sandpile group. Higher-dimensional trees. Sandpile groups. Cuts and flows. Stability.

 

Divisors

Divisors on curves. The Picard group and Abel-Jacobi theory. Riemann-Roch Theorems. Torelli’s Theorem. The Pic^g (G) torus. Metric graphs and tropical geometry. Arithmetic geometry. Arithmetical graphs. Riemann-Roch for lattices. Two variable zeta-functions. Enumerating arithmetical structures.

 

Ideals

Ideals. Toppling ideals. Tree ideals. Resolutions. Critical ideals. Riemann-Roch for monomial ideals.