AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Abelian networks IV. Dynamics of nonhalting networks
About this Title
Swee Hong Chan and Lionel Levine
Publication: Memoirs of the American Mathematical Society
Publication Year:
2022; Volume 276, Number 1358
ISBNs: 978-1-4704-5141-7 (print); 978-1-4704-7024-1 (online)
DOI: https://doi.org/10.1090/memo/1358
Published electronically: March 8, 2022
Keywords: Abelian distributed processors,
abelian mobile agents,
atemporal dynamics,
burning algorithm,
chip-firing,
commutative monoid action,
confluence,
critical group,
cycle-rooted spanning forest,
exchange lemma,
Eulerian walkers,
Grothendieck group,
injective action,
removal lemma,
rotor walk,
sandpile group
Table of Contents
Chapters
- 1. Introduction
- 2. Commutative Monoid Actions
- 3. Review of Abelian Networks
- 4. The Torsion Group of an Abelian Network
- 5. Critical Networks: Recurrence
- 6. Critical Networks: Dynamics
- 7. Rotor and Agent Networks
- 8. Concluding Remarks
Abstract
An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local commutativity condition. This paper is a continuation of the abelian networks series of Bond and Levine (2016), for which we extend the theory of abelian networks that halt on all inputs to networks that can run forever. A nonhalting abelian network can be realized as a discrete dynamical system in many different ways, depending on the update order. We show that certain features of the dynamics, such as minimal period length, have intrinsic definitions that do not require specifying an update order.
We give an intrinsic definition of the torsion group of a finite irreducible (halting or nonhalting) abelian network, and show that it coincides with the critical group of Bond and Levine (2016) if the network is halting. We show that the torsion group acts freely on the set of invertible recurrent components of the trajectory digraph, and identify when this action is transitive.
This perspective leads to new results even in the classical case of sinkless rotor networks (deterministic analogues of random walks). In Holroyd et. al (2008) it was shown that the recurrent configurations of a sinkless rotor network with just one chip are precisely the unicycles (spanning subgraphs with a unique oriented cycle, with the chip on the cycle). We generalize this result to abelian mobile agent networks with any number of chips. We give formulas for generating series such as \[ \sum _{n \geq 1} r_n z^n = \det (\frac {1}{1-z}D - A ) \] where $r_n$ is the number of recurrent chip-and-rotor configurations with $n$ chips; $D$ is the diagonal matrix of outdegrees, and $A$ is the adjacency matrix. A consequence is that the sequence $(r_n)_{n \geq 1}$ completely determines the spectrum of the simple random walk on the network.
- A. Asadi and S. Backman, Chip-Firing and Riemann-Roch Theory for Directed Graphs, ArXiv e-prints (2010), 1–29.
- Benjamin Braun, Hugo Corrales, Scott Corry, Luis David García Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, Gregg Musiker, and Carlos E. Valencia, Counting arithmetical structures on paths and cycles, Discrete Math. 341 (2018), no. 10, 2949–2963. MR 3843283, DOI 10.1016/j.disc.2018.07.002
- F. Bagnoli, F. Cecconi, A. Flammini, and A. Vespignani, Short-period attractors and non-ergodic behavior in the deterministic fixed-energy sandpile model, EPL (Europhysics Letters) 63 (2003), no. 4, 512.
- Javier Bitar and Eric Goles, Parallel chip firing games on graphs, Theoret. Comput. Sci. 92 (1992), no. 2, 291–300. MR 1148575, DOI 10.1016/0304-3975(92)90316-8
- 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
- Georgia Benkart, Caroline Klivans, and Victor Reiner, Chip firing on Dynkin diagrams and McKay quivers, Math. Z. 290 (2018), no. 1-2, 615–648. MR 3848449, DOI 10.1007/s00209-017-2034-5
- Anders Björner and László Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992), no. 4, 305–328. MR 1203679, DOI 10.1023/A:1022467132614
- Benjamin Bond and Lionel Levine, Abelian networks I. Foundations and examples, SIAM J. Discrete Math. 30 (2016), no. 2, 856–874. MR 3493110, DOI 10.1137/15M1030984
- Benjamin Bond and Lionel Levine, Abelian networks II: halting on all inputs, Selecta Math. (N.S.) 22 (2016), no. 1, 319–340. MR 3437839, DOI 10.1007/s00029-015-0192-z
- Benjamin Bond and Lionel Levine, Abelian networks III: The critical group, J. Algebraic Combin. 43 (2016), no. 3, 635–663. MR 3482442, DOI 10.1007/s10801-015-0648-4
- 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. MR 1120415, DOI 10.1016/S0195-6698(13)80111-4
- Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 544666
- Anders Björner and Günter M. Ziegler, Introduction to greedoids, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 284–357. MR 1165545, DOI 10.1017/CBO9780511662041.009
- Hannah Cairns, Some halting problems for abelian sandpiles are undecidable in dimension three, SIAM J. Discrete Math. 32 (2018), no. 4, 2636–2666. MR 3876862, DOI 10.1137/16M1091964
- Joshua Cooper, Benjamin Doerr, Joel Spencer, and Gábor Tardos, Deterministic random walks on the integers, European J. Combin. 28 (2007), no. 8, 2072–2090. MR 2351511, DOI 10.1016/j.ejc.2007.04.018
- Seth Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 319–329. MR 666857, DOI 10.1137/0603033
- Swee Hong Chan, Abelian sandpile model and Biggs-Merino polynomial for directed graphs, J. Combin. Theory Ser. A 154 (2018), 145–171. MR 3718064, DOI 10.1016/j.jcta.2017.08.013
- Hugo Corrales and Carlos E. Valencia, Arithmetical structures on graphs, Linear Algebra Appl. 536 (2018), 120–151. MR 3713448, DOI 10.1016/j.laa.2017.09.018
- Luca Dall’Asta, Exact solution of the one-dimensional deterministic fixed-energy sandpile, Phys. Rev. Lett. 96 (2006), 058003.
- Benjamin Doerr and Mahmoud Fouz, Quasi-random rumor spreading: reducing randomness can be costly, Inform. Process. Lett. 111 (2011), no. 5, 227–230. MR 2790745, DOI 10.1016/j.ipl.2010.11.006
- 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
- Leonard Eugene Dickson, Finiteness of the Odd Perfect and Primitive Abundant Numbers with $n$ Distinct Prime Factors, Amer. J. Math. 35 (1913), no. 4, 413–422. MR 1506194, DOI 10.2307/2370405
- Arnaud Dartois and Dominique Rossin, Height arrow model, FPSAC PROCEEDINGS 2004 ACTES SFCA 2004 Vancouver CANADA, 2004, p. 87.
- 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 Yuval Peres, Growth rates and explosions in sandpiles, J. Stat. Phys. 138 (2010), no. 1-3, 143–159. MR 2594895, DOI 10.1007/s10955-009-9899-6
- Robin Forman, Determinants of Laplacians on graphs, Topology 32 (1993), no. 1, 35–46. MR 1204404, DOI 10.1016/0040-9383(93)90035-T
- Andrei Gabrielov, Abelian avalanches and Tutte polynomials, Phys. A 195 (1993), no. 1-2, 253–274. MR 1215018, DOI 10.1016/0378-4371(93)90267-8
- Johnny Guzmán and Caroline Klivans, Chip-firing and energy minimization on M-matrices, J. Combin. Theory Ser. A 132 (2015), 14–31. MR 3311336, DOI 10.1016/j.jcta.2014.12.002
- Eric Goles and Maurice Margenstern, Universality of the chip-firing game, Theoret. Comput. Sci. 172 (1997), no. 1-2, 121–134. MR 1432859, DOI 10.1016/S0304-3975(95)00242-1
- P. A. Grillet, Commutative semigroups, Advances in Mathematics (Dordrecht), vol. 2, Kluwer Academic Publishers, Dordrecht, 2001. MR 2017849, DOI 10.1007/978-1-4757-3389-1
- Pierre Antoine Grillet, Irreducible actions, Period. Math. Hungar. 54 (2007), no. 1, 51–76. MR 2310367, DOI 10.1007/s-10998-007-1051-4
- Bálint Hujter, Viktor Kiss, and Lilla Tóthmérész, On the complexity of the chip-firing reachability problem, Proc. Amer. Math. Soc. 145 (2017), no. 8, 3343–3356. MR 3652788, DOI 10.1090/proc/13498
- 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
- Alexander E. Holroyd, Lionel Levine, and Peter Winkler, Abelian logic gates, Combin. Probab. Comput. 28 (2019), no. 3, 388–422. MR 3933782, DOI 10.1017/S0963548318000482
- Alexander E. Holroyd and James Propp, Rotor walks and Markov chains, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 105–126. MR 2681857, DOI 10.1090/conm/520/10256
- Gérard Huet, Confluent reductions: abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach. 27 (1980), no. 4, 797–821. MR 594700, DOI 10.1145/322217.322230
- Tian-Yi Jiang, On the Period Lengths of the Parallel Chip-Firing Game, ArXiv e-prints (2010), 1–13.
- Tian-Yi Jiang, Ziv Scully, and Yan X. Zhang, Motors and impossible firing patterns in the parallel chip-firing game, SIAM J. Discrete Math. 29 (2015), no. 1, 615–630. MR 3327346, DOI 10.1137/130933770
- Richard Kenyon, Spanning forests and the vector bundle Laplacian, Ann. Probab. 39 (2011), no. 5, 1983–2017. MR 2884879, DOI 10.1214/10-AOP596
- M. A. Kiwi, R. Ndoundam, M. Tchuente, and E. Goles, No polynomial bound for the period of the parallel chip firing game on graphs, Theoret. Comput. Sci. 136 (1994), no. 2, 527–532. MR 1311220, DOI 10.1016/0304-3975(94)00131-2
- Serge Lang, Algebra, 3rd ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. MR 1878556, DOI 10.1007/978-1-4613-0041-0
- Lionel Levine, Parallel chip-firing on the complete graph: devil’s staircase and Poincaré rotation number, Ergodic Theory Dynam. Systems 31 (2011), no. 3, 891–910. MR 2794953, DOI 10.1017/S0143385710000088
- 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
- Dino J. Lorenzini, Arithmetical graphs, Math. Ann. 285 (1989), no. 3, 481–501. MR 1019714, DOI 10.1007/BF01455069
- Russell Lyons and Yuval Peres, Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016. MR 3616205, DOI 10.1017/9781316672815
- Cristopher Moore and Martin Nilsson, Parallel quantum computation and quantum codes, SIAM J. Comput. 31 (2001/02), no. 3, 799–815. MR 1896459, DOI 10.1137/S0097539799355053
- V. B. Priezzhev, D. Dhar, A. Dhar, and S. Krishnamurthy, Eulerian walkers as a model of self-organized criticality, Physical Review Letters 77 (1996), no. 25, 5079.
- Trung Van Pham, Orbits of rotor-router operation and stationary distribution of random walks on directed graphs, Adv. in Appl. Math. 70 (2015), 45–53. MR 3388864, DOI 10.1016/j.aam.2015.06.006
- J. Propp, Random walk and random aggregation, derandomized, https://www.microsoft.com/en-us/research/video/random-walk-and-random-aggregation-derandomized/, 2003, Online Lecture.
- Alexander Postnikov and Boris Shapiro, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3109–3142. MR 2052943, DOI 10.1090/S0002-9947-04-03547-0
- Eugene R. Speer, Asymmetric abelian sandpile models, J. Statist. Phys. 71 (1993), no. 1-2, 61–74. MR 1215850, DOI 10.1007/BF01048088
- Benjamin Steinberg, A theory of transformation monoids: combinatorics and representation theory, Electron. J. Combin. 17 (2010), no. 1, Research Paper 164, 56. MR 2745717, DOI 10.37236/436
- Lilla Tóthmérész, Algorithmic aspects of rotor-routing and the notion of linear equivalence, Discrete Appl. Math. 236 (2018), 428–437. MR 3739802, DOI 10.1016/j.dam.2017.11.008
- Israel A. Wagner, Michael Lindenbaum, and Alfred M. Bruckstein, Smell as a computational resource—a lesson we can learn from the ant, Israel Symposium on Theory of Computing and Systems (Jerusalem, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 219–230. MR 1436463