Chip firing on graphs

Description

Chip-firing is a discrete dynamical process on graphs that exhibits rich connections to many mathematical subjects: combinatorics, mathematical physics, algebraic geometry, tropical geometry and more! The fundamental idea of this process is simple: given a graph where each vertex holds a certain number of "chips," a vertex can "fire" by distributing one chip to each of its neighbors, provided it has enough chips to do so. Despite its elementary rules, chip-firing gives rise to complex behaviors, making it a fascinating subject in discrete mathematics.

One of the most famous incarnations of chip-firing is the abelian sandpile model, which originated in theoretical physics as a model for self-organized criticality. This model leads to intricate fractal-like stable states and has been widely studied. The study of recurrent configurations in sandpile models reveals deep connections with algebraic structures such as the critical group (or sandpile group) of a graph, an abelian group whose order is given by the number of spanning trees of the graph via Kirchhoff’s Matrix-Tree Theorem. In algebraic and tropical geometry, chip-firing appears through the lens of divisors on graphs, which serve as a discrete analogue of divisors on algebraic curves. The Riemann-Roch theorem for graphs, developed by Baker and Norine, mirrors its classical counterpart in algebraic geometry but in a purely combinatorial setting. This perspective has led to applications in Brill-Noether theory, moduli spaces of curves, and tropical geometry, where chip-firing plays a role in understanding metric graphs and degeneration techniques in algebraic geometry.

This project offers students the opportunity to explore chip-firing from multiple perspectives, depending on their interests. Possible directions include (but are not limited to):

• Studying sandpile dynamics and recurrent configurations on different graph structures.
• Investigating combinatorial games related to chip-firing and analyzing winning strategies.
• Exploring the algebraic structure of the critical group and its connections to spanning trees.
• Examining the Riemann-Roch theorem for graphs and its implications in tropical geometry.

Through this project, students will gain insight into the interplay between combinatorics, algebra, geometry, and physics, all emerging from a deceptively simple process on graphs.

Essential modules

It is essential that students have taken Algebra II and Complex Analysis II. It is suggested (but not essential) that students take Geometry III or Decision Theory III (depending on the students interest) during the course of the project.

Resources

- “Divisors and sandpiles” by Scott Corry and David Perkinson [available here]
- “What is… a sandpile?” by Lionel Levine and James Propp [available here]
- "The mathematics of chip-firing” by C. Klivans [Wiki description, the book has been requested from the library]
-  https://thedollargame.io/ (an applet where you can play the chip-firing game on graphs yourself)