Chip-firing games, potential theory on graphs, and spanning trees

Abstract

We study the interplay between chip-firing games and potential theory on graphs, characterizing reduced divisors ($G$-parking functions) on graphs as the solution to an energy (or potential) minimization problem and providing an algorithm to efficiently compute reduced divisors. Applications include an "efficient bijective" proof of Kirchhoff's matrix-tree theorem and a new algorithm for finding random spanning trees. The running times of our algorithms are analyzed using potential theory, and we show that the bounds thus obtained generalize and improve upon several previous results in the literature. We also extend some of these considerations to metric graphs.

To appear in Journal of Combinatorial Theory, Series A -- Revised and updated. The discussion on metric graphs (now in Appendix A) will not appear in the journal version. Proofs of the Dhar theorem and the Cori-Le Borgne theorem are in v1 but not in v2

References in corpus (3)

• A family of bijections between G-parking functions and spanning trees
• The rank of a divisor on a finite graph: geometry and computation
• Reduced Divisors and Embeddings of Tropical Curves

Cited by in corpus (36)

• Canonical representatives for divisor classes on tropical curves and the Matrix-Tree Theorem
• Divisors on graphs, Connected flags, and Syzygies
• Sandpiles on the square lattice
• Geometric Bijections for Regular Matroids, Zonotopes, and Ehrhart Theory
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• Divisors on graphs, binomial and monomial ideals, and cellular resolutions
• Fourientations and the Tutte Polynomial
• Minimal Free Resolutions of the $G$-parking Function Ideal and the Toppling Ideal
• Kirchhoff's theorem for Prym varieties
• Canonical measures on metric graphs and a Kazhdan's theorem
• Abelian sandpile model and Biggs-Merino polynomial for directed graphs
• Chip-Firing Games and Critical Groups
• Linear series on metrized complexes of algebraic curves
• Counting Finite Index Subrings of ${\mathbb{Z}}^n$
• Tropical Convexity and Canonical Projections
• The distribution of Weierstrass points on a tropical curve
• G-parking functions and tree inversions
• The Riemann-Roch strategy, Complex lift of the Scaling Site
• Monomials, Binomials, and Riemann-Roch
• Divisors on graphs, orientations, syzygies, and system reliability
• A Bijection Between the Recurrent Configurations of a Hereditary Chip-Firing Model and Spanning Trees
• A Note on the Critical Groups of Strongly Regular Graphs and Their Generalizations
• Chip-firing may be much faster than you think
• Free divisors on metric graphs
• On lengths of burn-off chip-firing games
• Simplicial Dollar Game
• Sandpiles and Dominos
• Infinite Reduction of Divisors on Metric Graphs
• Integral flow and cycle chip-firing on graphs
• Standard monomials of $1$-skeleton ideals of multigraphs
• A Torelli Theorem for Graph Isomorphisms
• Chip-firing groups of iterated cones
• Tropical trigonal curves
• Diffusion on graphs is eventually periodic
• Generalized Bijective Maps between $G$-Parking Functions, Spanning Trees, and the Tutte Polynomial
• On approximating the rank of graph divisors