The abelian sandpile model defines a Markov chain whose states are integer-valued functions on the vertices of a simple connected graph @math . By viewing this chain as a (nonreversible) random walk on an abelian group, we give a formula for its eigenvalues and eigenvectors in terms of multiplicative harmonic functions' on the vertices of @math . We show that the spectral gap of the sandpile chain is within a constant factor of the length of the shortest non-integer vector in the dual Laplacian lattice, while the mixing time is at most a constant times the smoothing parameter of the Laplacian lattice. We find a surprising inverse relationship between the spectral gap of the sandpile chain and that of simple random walk on @math : If the latter has a sufficiently large spectral gap, then the former has a small gap! In the case where @math is the complete graph on @math vertices, we show that the sandpile chain exhibits cutoff at time @math .
A new bound (Theorem ) for the duration of the chip-firing game with @math chips on a @math -vertex graph is obtained, by a careful analysis of the pseudo-inverse of the discrete Laplacian matrix of the graph. This new bound is expressed in terms of the entries of the pseudo-inverse. It is shown (Section 5) to be always better than the classic bound due to Bj "o rner, Lov ' a sz and Shor. In some cases the improvement is dramatic. For instance: for strongly regular graphs the classic and the new bounds reduce to @math and @math , respectively. For dense regular graphs - @math - the classic and the new bounds reduce to @math and @math , respectively. This is a snapshot of a work in progress, so further results in this vein are in the works. 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 [email protected]?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. 