Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

   
 
 

 

Mixing time and eigenvalues of the abelian sandpile Markov chain


Authors: Daniel C. Jerison, Lionel Levine and John Pike
Journal: Trans. Amer. Math. Soc. 372 (2019), 8307-8345
MSC (2010): Primary 60J10, 82C20; Secondary 05C50
DOI: https://doi.org/10.1090/tran/7585
Published electronically: September 23, 2019
MathSciNet review: 4029698
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The abelian sandpile model defines a Markov chain whose states are integer-valued functions on the vertices of a simple connected graph $ G$. 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 $ G$. We show that the spectral gap of the sandpile chain is within a constant factor of the length of the shortest noninteger 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 $ G$: If the latter has a sufficiently large spectral gap, then the former has a small gap! In the case where $ G$ is the complete graph on $ n$ vertices, we show that the sandpile chain exhibits cutoff at time $ \frac {1}{4\pi ^{2}}n^{3}\log n$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60J10, 82C20, 05C50

Retrieve articles in all journals with MSC (2010): 60J10, 82C20, 05C50


Additional Information

Daniel C. Jerison
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Address at time of publication: Department of Mathematics, Tel Aviv University, Tel Aviv, Israel
Email: jerison@math.cornell.edu, jerison@mail.tau.ac.il

Lionel Levine
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: levine@math.cornell.edu

John Pike
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Address at time of publication: Department of Mathematics, Bridgewater State University, Bridgewater, Massachusetts 02325
Email: john.pike@bridgew.edu

DOI: https://doi.org/10.1090/tran/7585
Keywords: Abelian sandpile model, chip-firing, Laplacian lattice, mixing time, multiplicative harmonic function, pseudoinverse, sandpile group, smoothing parameter, spectral gap
Received by editor(s): November 26, 2015
Received by editor(s) in revised form: March 13, 2018
Published electronically: September 23, 2019
Additional Notes: The first and third authors were supported in part by NSF grant \href{https://nsf.gov/awardsearch/showAward?AWD_{I}D=0739164&HistoricalAwards=false}DMS-0739164.
The second author was supported by NSF grant \href{http://www.nsf.gov/awardsearch/showAward?AWD_{I}D=1455272}DMS-1455272 and a Sloan Fellowship.
Article copyright: © Copyright 2019 by the authors