The Rotor-Router Model on Regular Trees
arXiv:0705.1562 · doi:10.1016/j.jcta.2008.05.012
Abstract
The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible "escape sequences" for the ternary tree, that is, binary words a_1 ... a_n for which there exists a rotor configuration so that the k-th chip escapes to infinity if and only if a_k=1.
v2 incorporates referee comments, clarifies that the results of section 2 apply also to multigraphs
References in corpus (2)
Cited by in corpus (16)
- Chip-Firing and Rotor-Routing on Directed Graphs
- The Sandpile Group of a Tree
- Transience and recurrence of rotor-router walks on directed covers of graphs
- Deterministic Random Walks on Regular Trees
- Discrete low-discrepancy sequences
- Rotor walks on transient graphs and the wired spanning forest
- A rotor configuration with maximum escape rate
- Local-to-global principles for rotor walk
- Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs
- Rotor walks on general trees
- Recurrence of horizontal-vertical walks
- Internal Aggregation Models on Comb Lattices
- Rotor-router aggregation on the layered square lattice
- Infinite excursions of rotor walks on regular trees
- A novel Recurrence-Transience transition and Tracy-Widom growth in a cellular automaton with quenched noise
- The rotor-router group of directed covers of graphs