Observations on Abelian sandpile models for directed graphs

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

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.

Keywords

self-organized criticality / semigroups / sandpile model / recurrent group / complexity / algebraic structures / graph theory / asynchronous timing

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

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

[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

[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

[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

[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

[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

[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

[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

[12] P. Chen, Y. Hou, On the sandpile group of P₄ × C_n , Eur. J. Comb., 29 (2008), 532-534. https://doi.org/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

[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

[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

[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

[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

[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

[20] M. Creutz, Abelian sandpiles, Comput. Phys., 5 (1991), 198-203. https://doi.org/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-81

[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

[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

[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

[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

[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

[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.