Mixing time and eigenvalues of the abelian sandpile Markov chain. (English) Zbl 1472.60119
Summary: 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\).
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Keywords:
abelian sandpile model; chip-firing; Laplacian lattice; mixing time; multiplicative harmonic function; pseudoinverse; sandpile group; smoothing parameter; spectral gapReferences:
| [1] | Amini, Omid; Manjunath, Madhusudan, Riemann-Roch for sub-lattices of the root lattice \(A_n\), Electron. J. Combin., 17, 1, Research Paper 124, 50 pp. (2010) · Zbl 1277.05105 |
| [2] | BabTou L\'aszl\'o Babai and Evelin Toumpakari, A structure theory of the sandpile monoid for directed graphs, (2010). |
| [3] | Bacher, Roland; de la Harpe, Pierre; Nagnibeda, Tatiana, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France, 125, 2, 167-198 (1997) · Zbl 0891.05062 |
| [4] | Bak, Per; Tang, Chao; Wiesenfeld, Kurt, Self-organized criticality, Phys. Rev. A (3), 38, 1, 364-374 (1988) · Zbl 1230.37103 · doi:10.1103/PhysRevA.38.364 |
| [5] | Baker, Matthew; Norine, Serguei, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 2, 766-788 (2007) · Zbl 1124.05049 · doi:10.1016/j.aim.2007.04.012 |
| [6] | Baker, Matthew; Shokrieh, Farbod, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A, 120, 1, 164-182 (2013) · Zbl 1408.05089 · doi:10.1016/j.jcta.2012.07.011 |
| [7] | Biggs, N. L., Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 1, 25-45 (1999) · Zbl 0919.05027 · doi:10.1023/A:1018611014097 |
| [8] | BLS91 Anders Bj\`“orner, L\'”aszl\'o Lov\'asz, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283-291, http://www.ams.org/mathscinet-getitem?mr=1120415MR1120415. · Zbl 0729.05048 |
| [9] | Chang, Shu-Chiuan; Chen, Lung-Chi; Yang, Wei-Shih, Spanning trees on the Sierpinski gasket, J. Stat. Phys., 126, 3, 649-667 (2007) · Zbl 1110.82007 · doi:10.1007/s10955-006-9262-0 |
| [10] | Chung, Fan; Radcliffe, Mary, On the spectra of general random graphs, Electron. J. Combin., 18, 1, Paper 215, 14 pp. (2011) · Zbl 1229.05248 |
| [11] | Dhar, D.; Ruelle, P.; Sen, S.; Verma, D.-N., Algebraic aspects of abelian sandpile models, J. Phys. A, 28, 4, 805-831 (1995) · Zbl 0848.68062 |
| [12] | Dhar, Deepak, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613-1616 (1990) · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613 |
| [13] | Diaconis, Persi, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes-Monograph Series 11, vi+198 pp. (1988), Institute of Mathematical Statistics, Hayward, CA · Zbl 0695.60012 |
| [14] | Farrell, Matthew; Levine, Lionel, CoEulerian graphs, Proc. Amer. Math. Soc., 144, 7, 2847-2860 (2016) · Zbl 1334.05025 · doi:10.1090/proc/12952 |
| [15] | FLW Anne Fey, Lionel Levine, and David B. Wilson, Driving sandpiles to criticality and beyond, Phys. Rev. Lett. 104 (2010), 145703, http://arxiv.org/abs/0912.3206arXiv:0912.3206, 2009. |
| [16] | Friedman, Joel, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc., 195, 910, viii+100 pp. (2008) · Zbl 1177.05070 · doi:10.1090/memo/0910 |
| [17] | Gentry, Craig; Peikert, Chris; Vaikuntanathan, Vinod, Trapdoors for hard lattices and new cryptographic constructions [extended abstract]. STOC’08, 197-206 (2008), ACM, New York · Zbl 1231.68124 · doi:10.1145/1374376.1374407 |
| [18] | Glasser, M. L.; Wu, F. Y., On the entropy of spanning trees on a large triangular lattice, Ramanujan J., 10, 2, 205-214 (2005) · Zbl 1079.05007 · doi:10.1007/s11139-005-4847-9 |
| [19] | Godsil, Chris; Royle, Gordon, Algebraic graph theory, Graduate Texts in Mathematics 207, xx+439 pp. (2001), Springer-Verlag, New York · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9 |
| [20] | G14 Felix Goldberg, Chip-firing may be much faster than you think, e-prints, http://arxiv.org/abs/1411.1652arXiv:1411.1652, 2014. |
| [21] | Holroyd, Alexander E.; Levine, Lionel; M\'{e}sz\'{a}ros, Karola; Peres, Yuval; Propp, James; Wilson, David B., Chip-firing and rotor-routing on directed graphs. In and out of equilibrium. 2, Progr. Probab. 60, 331-364 (2008), Birkh\"{a}user, Basel · Zbl 1173.82339 · doi:10.1007/978-3-7643-8786-0\_17 |
| [22] | Hoory, Shlomo; Linial, Nathan; Wigderson, Avi, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), 43, 4, 439-561 (2006) · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8 |
| [23] | Horn, Roger A.; Johnson, Charles R., Matrix analysis, xiv+561 pp. (1990), Cambridge University Press, Cambridge · Zbl 0704.15002 |
| [24] | JJ Hang-Hyun Jo and Hyeong-Chai Jeong, Comment on “driving sandpiles to criticality and beyond”, Phys. Rev. Lett. 105 (2010), 019601. |
| [25] | Jungnickel, Dieter, Graphs, networks and algorithms, Algorithms and Computation in Mathematics 5, xx+675 pp. (2013), Springer, Heidelberg · Zbl 1255.68001 · doi:10.1007/978-3-642-32278-5 |
| [26] | Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L., Markov chains and mixing times, xviii+371 pp. (2009), American Mathematical Society, Providence, RI · Zbl 1160.60001 |
| [27] | Levine, Lionel, Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Comm. Math. Phys., 335, 2, 1003-1017 (2015) · Zbl 1320.82039 · doi:10.1007/s00220-014-2216-5 |
| [28] | Lubotzky, Alexander, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. (N.S.), 49, 1, 113-162 (2012) · Zbl 1232.05194 · doi:10.1090/S0273-0979-2011-01359-3 |
| [29] | Micciancio, Daniele; Regev, Oded, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput., 37, 1, 267-302 (2007) · Zbl 1142.68037 · doi:10.1137/S0097539705447360 |
| [30] | Peikert, Chris, Limits on the hardness of lattice problems in \(l_p\) norms, Comput. Complexity, 17, 2, 300-351 (2008) · Zbl 1149.68039 · doi:10.1007/s00037-008-0251-3 |
| [31] | Perkinson, David; Perlman, Jacob; Wilmes, John, Primer for the algebraic geometry of sandpiles. Tropical and non-Archimedean geometry, Contemp. Math. 605, 211-256 (2013), Amer. Math. Soc., Providence, RI · Zbl 1320.05060 · doi:10.1090/conm/605/12117 |
| [32] | PPPR 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, http://arxiv.org/abs/1104.3548arXiv:1104.3548, 2011. |
| [33] | Saloff-Coste, Laurent, Random walks on finite groups. Probability on discrete structures, Encyclopaedia Math. Sci. 110, 263-346 (2004), Springer, Berlin · Zbl 1049.60006 · doi:10.1007/978-3-662-09444-0\_5 |
| [34] | SMKW15 Andrey Sokolov, Andrew Melatos, Tien Kieu, and Rachel Webster, Memory on multiple time-scales in an Abelian sandpile, Phys. A 428 (2015), 295-301. |
| [35] | Stanley, Richard P., Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics 62, xii+581 pp. (1999), Cambridge University Press, Cambridge · Zbl 0928.05001 · doi:10.1017/CBO9780511609589 |
| [36] | Wei, Wei; Tian, Chengliang; Wang, Xiaoyun, New transference theorems on lattices possessing \(n^{\epsilon} \)-unique shortest vectors, Discrete Math., 315, 144-155 (2014) · Zbl 1281.11068 · doi:10.1016/j.disc.2013.10.020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
