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 @math . We outline an efficient bijective proof of this theorem, by studying a canonical finite abelian group attached to @math 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 @math -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.
The relationship between chip-firing games and the Jacobian group is studied in @cite_3 @cite_28 . Some algorithmic aspects of the chip-firing games are studied in @cite_19 @cite_0 @cite_23 ; see for a discussion on how @cite_19 relates to our work.
@cite_28 @cite_3 @cite_0 @cite_19 @cite_23
1910083634 2111293718 2082513731 2026915189
A variant of the chip-firing game on a graph is defined. It is shown that the set of configurations that are stable and recurrent for this game can be given the structure of an abelian group, and that the order of the group is equal to the tree number of the graph. In certain cases the game can be used to illuminate the structure of the group. This paper encompasses a motley collection of ideas from several areas of mathematics, including, in no particular order, random walks, the Picard group, exchange rate networks, chip-firing games, cohomology, and the conductance of an electrical network. The linking threads are the discrete Laplacian on a graph and the solution of the associated Dirichlet problem . Thirty years ago, this subject was dismissed by many as a trivial specialisation of cohomology theory, but it has now been shown to have hidden depths. Plumbing these depths leads to new theoretical advances, many of which throw light on the diverse applications of the theory. We analyse the following (solitaire) game: each node of a graph contains a pile of chips, and a move consists of selecting a node with at least as many chips on it as its degree, and letting it send one chip to each of its neighbors. The game terminates if there is no such node. We show that the finiteness of the game and the terminating configuration are independent of the moves made. If the number of chips is less than the number of edges, the game is always finite. If the number of chips is at least the number of edges, the game can be infinite for an appropriately chosen initial configuration. If the number of chips is more than twice the number of edges minus the number of nodes, then the game is always infinite. The independence of the finiteness and the terminating position follows from simple but powerful ‘exchange properties’ of the sequences of legal moves, and from some general results on ‘antimatroids with repetition’, i.e. languages having these exchange properties. We relate the number of steps in a finite game to the least positive eigenvalue of the Laplace operator of the graph. Bjorner, Lvasz, and Shor have introduced a chip firing game on graphs. This paper proves a polynomial bound on the length of the game in terms of the number of vertices of the graph provided the length is finite. The obtained bound is best possible within a constant factor.