Mixing time and eigenvalues of the abelian sandpile Markov chain
HTML articles powered by AMS MathViewer
- by Daniel C. Jerison, Lionel Levine and John Pike PDF
- Trans. Amer. Math. Soc. 372 (2019), 8307-8345
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
- Omid Amini and Madhusudan Manjunath, Riemann-Roch for sub-lattices of the root lattice $A_n$, Electron. J. Combin. 17 (2010), no. 1, Research Paper 124, 50. MR 2729373
- LĂĄszlĂł Babai and Evelin Toumpakari, A structure theory of the sandpile monoid for directed graphs, (2010).
- Roland Bacher, Pierre de la Harpe, and Tatiana Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France 125 (1997), no. 2, 167â198 (English, with English and French summaries). MR 1478029, DOI 10.24033/bsmf.2303
- Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364â374. MR 949160, DOI 10.1103/PhysRevA.38.364
- Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766â788. MR 2355607, DOI 10.1016/j.aim.2007.04.012
- Matthew Baker and Farbod Shokrieh, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A 120 (2013), no. 1, 164â182. MR 2971705, DOI 10.1016/j.jcta.2012.07.011
- N. L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9 (1999), no. 1, 25â45. MR 1676732, DOI 10.1023/A:1018611014097
- Anders Björner, LĂĄszlĂł LovĂĄsz, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283â291, MR1120415.
- Shu-Chiuan Chang, Lung-Chi Chen, and Wei-Shih Yang, Spanning trees on the Sierpinski gasket, J. Stat. Phys. 126 (2007), no. 3, 649â667. MR 2294471, DOI 10.1007/s10955-006-9262-0
- Fan Chung and Mary Radcliffe, On the spectra of general random graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 215, 14. MR 2853072
- D. Dhar, P. Ruelle, S. Sen, and D.-N. Verma, Algebraic aspects of abelian sandpile models, J. Phys. A 28 (1995), no. 4, 805â831. MR 1326322, DOI 10.1088/0305-4470/28/4/009
- Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613â1616. MR 1044086, DOI 10.1103/PhysRevLett.64.1613
- Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture NotesâMonograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069, DOI 10.1007/BFb0086177
- Matthew Farrell and Lionel Levine, CoEulerian graphs, Proc. Amer. Math. Soc. 144 (2016), no. 7, 2847â2860. MR 3487219, DOI 10.1090/proc/12952
- Anne Fey, Lionel Levine, and David B. Wilson, Driving sandpiles to criticality and beyond, Phys. Rev. Lett. 104 (2010), 145703, arXiv:0912.3206, 2009.
- Joel Friedman, A proof of Alonâs second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100. MR 2437174, DOI 10.1090/memo/0910
- Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions [extended abstract], STOCâ08, ACM, New York, 2008, pp. 197â206. MR 2582664, DOI 10.1145/1374376.1374407
- M. L. Glasser and F. Y. Wu, On the entropy of spanning trees on a large triangular lattice, Ramanujan J. 10 (2005), no. 2, 205â214. MR 2194523, DOI 10.1007/s11139-005-4847-9
- Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620, DOI 10.1007/978-1-4613-0163-9
- Felix Goldberg, Chip-firing may be much faster than you think, e-prints, arXiv:1411.1652, 2014.
- Alexander E. Holroyd, Lionel Levine, Karola MĂ©szĂĄros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, BirkhĂ€user, Basel, 2008, pp. 331â364. MR 2477390, DOI 10.1007/978-3-7643-8786-0_{1}7
- Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439â561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1990. Corrected reprint of the 1985 original. MR 1084815
- Hang-Hyun Jo and Hyeong-Chai Jeong, Comment on âdriving sandpiles to criticality and beyondâ, Phys. Rev. Lett. 105 (2010), 019601.
- Dieter Jungnickel, Graphs, networks and algorithms, 4th ed., Algorithms and Computation in Mathematics, vol. 5, Springer, Heidelberg, 2013. MR 2986014, DOI 10.1007/978-3-642-32278-5
- David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. MR 2466937, DOI 10.1090/mbk/058
- Lionel Levine, Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Comm. Math. Phys. 335 (2015), no. 2, 1003â1017. MR 3316648, DOI 10.1007/s00220-014-2216-5
- Alexander Lubotzky, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 1, 113â162. MR 2869010, DOI 10.1090/S0273-0979-2011-01359-3
- Daniele Micciancio and Oded Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput. 37 (2007), no. 1, 267â302. MR 2306293, DOI 10.1137/S0097539705447360
- Chris Peikert, Limits on the hardness of lattice problems in $l_p$ norms, Comput. Complexity 17 (2008), no. 2, 300â351. MR 2417596, DOI 10.1007/s00037-008-0251-3
- David Perkinson, Jacob Perlman, and John Wilmes, Primer for the algebraic geometry of sandpiles, Tropical and non-Archimedean geometry, Contemp. Math., vol. 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211â256. MR 3204273, DOI 10.1090/conm/605/12117
- Su. S. Poghosyan, V. S. Poghosyan, V. B. Priezzhev, and P. Ruelle, Numerical study of the correspondence between the dissipative and fixed-energy abelian sandpile models, Phys. Rev. E 84 (2011), 066119, arXiv:1104.3548, 2011.
- Laurent Saloff-Coste, Random walks on finite groups, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 263â346. MR 2023654, DOI 10.1007/978-3-662-09444-0_{5}
- Andrey Sokolov, Andrew Melatos, Tien Kieu, and Rachel Webster, Memory on multiple time-scales in an Abelian sandpile, Phys. A 428 (2015), 295â301.
- Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
- Wei Wei, Chengliang Tian, and Xiaoyun Wang, New transference theorems on lattices possessing $n^Ï”$-unique shortest vectors, Discrete Math. 315 (2014), 144â155. MR 3130366, DOI 10.1016/j.disc.2013.10.020
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
- MR Author ID: 654666
- 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
- MR Author ID: 966572
- Email: john.pike@bridgew.edu
- 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 DMS-0739164.
The second author was supported by NSF grant DMS-1455272 and a Sloan Fellowship. - © Copyright 2019 by the authors
- Journal: Trans. Amer. Math. Soc. 372 (2019), 8307-8345
- MSC (2010): Primary 60J10, 82C20; Secondary 05C50
- DOI: https://doi.org/10.1090/tran/7585
- MathSciNet review: 4029698