Observations on Abelian sandpile models for directed graphs

Amena Assem; Hanna Derets; Chrystopher L. Nehaniv; Amena Assem; Hanna Derets; Chrystopher L. Nehaniv

doi:10.3934/era.2025240

Electronic Research Archive

2025, Volume 33, Issue 9: 5348-5376. doi: 10.3934/era.2025240

Previous Article Next Article

Review Special Issues

Observations on Abelian sandpile models for directed graphs

1.
Department of Systems Design Engineering, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
2.
David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
3.
Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
In honor of Professor Roderick Melnik, in celebration of his contributions.

Received: 01 May 2025 Revised: 01 August 2025 Accepted: 13 August 2025 Published: 12 September 2025

We relate various characterizations of sandpile dynamics arising in the literature referred to as "Abelian sandpile models", and we rigorously establish the sense in which they are commutative and associative as algebraic structures. In particular, associativity is approached from different perspectives: directly for the addition of configurations followed by stabilization; as a property of homomorphic images of semigroups; via the composition of operators on configurations; and, more generally, from an asynchronous perspective. We show how the existing formulations all arise within a common framework as substructures or homomorphic images of a non-commutative semigroup of operators. The appendix gives results on the algebraic complexity of sandpile semigroups, with 1) two different proofs determining the Krohn–Rhodes complexity of the finite Abelian sandpile models and all finite Abelian semigroups, 2) exact values of the aperiodic complexity measure for directed non-Abelian sandpile semigroups, and 3) exhibits new kinds of non-Abelian sandpile semigroups of higher Krohn–Rhodes complexity.
- self-organized criticality,
- semigroups,
- sandpile model,
- recurrent group,
- complexity,
- algebraic structures,
- graph theory,
- asynchronous timing
Citation: Amena Assem, Hanna Derets, Chrystopher L. Nehaniv. Observations on Abelian sandpile models for directed graphs[J]. Electronic Research Archive, 2025, 33(9): 5348-5376. doi: 10.3934/era.2025240

Related Papers:

Abstract

We relate various characterizations of sandpile dynamics arising in the literature referred to as "Abelian sandpile models", and we rigorously establish the sense in which they are commutative and associative as algebraic structures. In particular, associativity is approached from different perspectives: directly for the addition of configurations followed by stabilization; as a property of homomorphic images of semigroups; via the composition of operators on configurations; and, more generally, from an asynchronous perspective. We show how the existing formulations all arise within a common framework as substructures or homomorphic images of a non-commutative semigroup of operators. The appendix gives results on the algebraic complexity of sandpile semigroups, with 1) two different proofs determining the Krohn–Rhodes complexity of the finite Abelian sandpile models and all finite Abelian semigroups, 2) exact values of the aperiodic complexity measure for directed non-Abelian sandpile semigroups, and 3) exhibits new kinds of non-Abelian sandpile semigroups of higher Krohn–Rhodes complexity.

References

[1]	P. Bak, C. Tang, K. Wiesenfeld, Self-organized criticality, Phys. Rev. A, 38 (1988), 364–374. https://doi.org/10.1103/PhysRevA.38.364 doi: 10.1103/PhysRevA.38.364
[2]	P. Bak, C. Tang, K. Wiesenfeld, Self-organized criticality: An explanation of the 1/f noise, Phys. Rev. Lett., 59 (1987), 381–384. https://doi.org/10.1103/PhysRevLett.59.381 doi: 10.1103/PhysRevLett.59.381
[3]	P. Fieguth, An Introduction to Complex Systems, 2nd Ed., Springer Verlag, 2021. https://doi.org/10.1007/978-3-030-63168-0
[4]	D. Dhar, Self-organized critical state of sandpile automation models, Phys. Rev. Lett., 64 (1990), 1613–1616.
[5]	D. Dhar, S. N. Majumdar, Abelian sandpile model on the Bethe lattice, J. Phys. A: Math. Gen., 23 (1990), 4333. https://doi.org/10.1088/0305-4470/23/19/018 doi: 10.1088/0305-4470/23/19/018
[6]	V. B. Priezzhev, Structure of two-dimensional sandpile. I. Height probabilities, J. Stat. Phys., 74 (1994), 955–979. https://doi.org/10.1007/BF02188212 doi: 10.1007/BF02188212
[7]	S. R. Athreya, A. A. Járai, Infinite volume limit for the stationary distribution of Abelian sandpile models, Commun. Math. Phys., 249 (2004), 197–213. https://doi.org/10.1007/s00220-004-1080-0 doi: 10.1007/s00220-004-1080-0
[8]	C. J. Klivans, The Mathematics of Chip-Firing, Chapman and Hall/CRC, 2018. https://doi.org/10.1201/9781315206899
[9]	A. Björner, L. Lovász, P. W. Shor, Chip-firing games on graphs, European Journal of Combinatorics, 12 (1991), 283–291. https://doi.org/10.1016/S0195-6698(13)80111-4 doi: 10.1016/S0195-6698(13)80111-4
[10]	D. Dhar, P. Ruelle, S. Sen, D. N. Verma, Algebraic aspects of Abelian sandpile models, J. Phys. A: Math. Gen., 28 (1995), 805. https://doi.org/10.1088/0305-4470/28/4/009 doi: 10.1088/0305-4470/28/4/009
[11]	D. J. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Mathematics, 91 (1991), 277–282. https://doi.org/10.1016/0012-365X(90)90236-B doi: 10.1016/0012-365X(90)90236-B
[12]	P. Chen, Y. Hou, On the sandpile group of $ P_4 \times C_n $, Eur. J. Comb., 29 (2008), 532–534. https://doi.org/10.1016/j.ejc.2006.12.003 doi: 10.1016/j.ejc.2006.12.003
[13]	B. Jacobson, A. Niedermaier, V. Reiner, Critical groups for complete multipartite graphs and Cartesian products of complete graphs, J. Graph Theory, 44 (2003), 231–250. https://doi.org/10.1002/jgt.10139 doi: 10.1002/jgt.10139
[14]	H. Chen, B. Mohar, The sandpile group of a polygon flower, Discrete Appl. Math., 270 (2019), 68–82. https://doi.org/10.1016/j.dam.2019.07.020 doi: 10.1016/j.dam.2019.07.020
[15]	H. Bai, On the critical group of the $ n $-cube, Linear Algebra Appl., 369 (2003), 251–261. https://doi.org/10.1016/S0024-3795(02)00727-9 doi: 10.1016/S0024-3795(02)00727-9
[16]	Z. Raza, On the critical group of certain subdivided wheel graphs, Punjab Univ. J. Math., 47 (2015), 57–64.
[17]	C. A. Alfaro, C. E. Valencia, On the sandpile group of the cone of a graph, Linear Algebra Appl., 436 (2012), 1154–1176. https://doi.org/10.1016/j.laa.2011.07.030 doi: 10.1016/j.laa.2011.07.030
[18]	D. B. Chandler, P. Sin, Q. Xiang, The Smith and critical groups of Paley graphs, J. Algebr. Comb., 41 (2015), 1013–1022. https://doi.org/10.1007/s10801-014-0563-0 doi: 10.1007/s10801-014-0563-0
[19]	A. Dartois, F. Fiorenzi, P. Francini, Sandpile group on the graph $ D_n $ of the dihedral group, Eur. J. Comb., 24 (2003), 815–824. https://doi.org/10.1016/S0195-6698(03)00104-5 doi: 10.1016/S0195-6698(03)00104-5
[20]	M. Creutz, Abelian sandpiles, Comput. Phys., 5 (1991), 198–203. https://doi.org/10.1063/1.168408 doi: 10.1063/1.168408
[21]	T. Shibazaki, T. Namiki, Efficient computation method for identity element of Abelian sandpile model, in Proceedings of the 2015 Third International Symposium on Computing and Networking (CANDAR), IEEE, (2015), 430–435. https://doi.org/10.1109/CANDAR.2015.76
[22]	S. Corry, D. Perkinson, Divisors and Sandpiles, American Mathematical Society, 2018.
[23]	H. Derets, C. L. Nehaniv, The study of the transformation semigroup of the Abelian and directed non-Abelian sandpiles. in Addressing Modern Challenges in the Mathematical, Statistical, and Computational Sciences, Springer, (2025), 3–13. https://doi.org/10.1007/978-3-031-84869-8_1
[24]	L. Babai, E. Toumpakari, A structure theory of the sandpile monoid for directed graphs, J. Comb., 2010.
[25]	S. Kim, Y. Wang, A stochastic variant of the Abelian sandpile model, J. Stat. Phys., 178 (2020), 711–724. https://doi.org/10.1007/s10955-019-02453-7 doi: 10.1007/s10955-019-02453-7
[26]	Y. B. Chan, J. F. Marckert, T. Selig, A natural stochastic extension of the sandpile model on a graph, J. Comb. Theory Ser. A, 120 (2013), 1913–1928. https://doi.org/10.1016/j.jcta.2013.07.004 doi: 10.1016/j.jcta.2013.07.004
[27]	A. Ayyer, A. Schilling, B. Steinberg, N. M. Thiéry, Directed nonabelian sandpile models on trees, Commun. Math. Phys., 335 (2015), 1065–1098. https://doi.org/10.1007/s00220-015-2343-7 doi: 10.1007/s00220-015-2343-7
[28]	M. Lang, M. Shkolnikov, Harmonic dynamics of the Abelian sandpile, in PNAS, 116 (2019), 2821–2830. https://doi.org/10.1073/pnas.1812015116
[29]	L. Levine, Y. Peres, Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile, Potential Anal., 30 (2009), 1–27. https://doi.org/10.1007/s11118-008-9104-6 doi: 10.1007/s11118-008-9104-6
[30]	J. L. Rhodes, K. B. Krohn, B. R. Tilson, Algebraic Theory of Machines, Languages, and Semigroups, edited by M. A. Arbib, Academic Press, 1968.
[31]	K. Krohn, J. Rhodes, Complexity of finite semigroups, Ann. Math., 88 (1968), 128–160. https://doi.org/10.2307/1970558 doi: 10.2307/1970558
[32]	S. Eilenberg, Automata, Languages, and Machines, Volume B, Pure and Applied Mathematics, Academic Press, 1976.
[33]	B. Tilson, Complexity of Semigroups and Morphisms, in Automata, Languages and Machines. Volume B, edited by S. Eilenberg, Pure and Applied Mathematics, 59B, Academic Press, (1976), 313–385.
[34]	C. L. Nehaniv, Complexity of finite aperiodic semigroups and star-free languages, in Semigroups, Automata, Languages, edited by J. Almeida, G. Gomes, and P. Silva, World Scientific, (1996), 195–209.

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)