Can I read Chip-Firing Games, $G$-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem on EtoBox?

Chip-Firing Games, $G$-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem by Shokrieh, Farbod is a scholarly article available to read on EtoBox.

What is Chip-Firing Games, $G$-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem about?

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.

Author

Shokrieh, Farbod

Published

2009

Language

EN