Chip-Firing Games, G-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem

2009/07/27 by Shokrieh, Farbod
#05C05 #05C50 #05C85 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0907.4761

Abstract

Kirchhoff's matrix-tree theorem states that the number of spanning trees of a graph G is equal to the value of the determinant of the reduced Laplacian of G. We outline an efficient bijective proof of this theorem, by studying a canonical finite abelian group attached to G whose order is equal to the value of same matrix determinant. More specifically, we show how one can efficiently compute a bijection between the group elements and the spanning trees of the graph. The main ingredient for computing the bijection is an efficient algorithm for finding the unique G-parking function (reduced divisor) in a linear equivalence class defined by a chip-firing game. We also give applications, including a new and completely algebraic algorithm for generating random spanning trees. Other applications include algorithms related to chip-firing games and sandpile group law, as well as certain algorithmic problems about the Riemann-Roch theory on graphs.

Related

• Chip-firing on graphs of groups
• Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff's matrix tree theorem
• A Beginner's Guide to Counting Spanning Trees in a Graph
• The critical group of a combinatorial map
• Generalized chip firing and critical groups of arithmetical structures on trees