Abelian networks IV. Dynamics of nonhalting networks
arXiv:1804.03322 · doi:10.1090/memo/1358
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 \emph{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 is the number of recurrent chip-and-rotor configurations with chips; is the diagonal matrix of outdegrees, and is the adjacency matrix. A consequence is that the sequence completely determines the spectrum of the simple random walk on the network.
arXiv comment97 pages, 21 figures, to appear in Mem. Amer. Math. Soc
References in corpus (15)
- Eulerian Walkers as a model of Self-Organised Criticality
- Chip-Firing and Rotor-Routing on Directed Graphs
- Spanning forests and the vector bundle Laplacian
- Growth Rates and Explosions in Sandpiles
- Short period attractors and non-ergodic behavior in the deterministic fixed energy sandpile model
- Exact solution of the one-dimensional deterministic Fixed-Energy Sandpile
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- Counting Arithmetical Structures on Paths and Cycles
- Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
- Parallel Chip-Firing on the Complete Graph: Devil's Staircase and Poincare Rotation Number
- On the complexity of the chip-firing reachability problem
- Some halting problems for abelian sandpiles are undecidable in dimension three
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- Abelian logic gates
- Motors and Impossible Firing Patterns in the Parallel Chip-Firing Game