Chip-Firing and Rotor-Routing on Directed Graphs
arXiv:0801.3306 · doi:10.1007/978-3-7643-8786-0_17
Abstract
We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing open problems.
34 pages, 11 figures. v2 has additional references, v3 corrects figure 9, v4 corrects several typos
References in corpus (5)
Cited by in corpus (51)
- Chip-firing games, potential theory on graphs, and spanning trees
- Sandpile groups and spanning trees of directed line graphs
- On the Sandpile group of the cone of a graph
- The Sandpile Group of a Tree
- The distribution of sandpile groups of random regular graphs
- Minimal configurations and sandpile measures
- Multiple and inverse topplings in the Abelian Sandpile Model
- Sandpiles on the square lattice
- Indistinguishability of Trees in Uniform Spanning Forests
- Conservation laws for strings in the Abelian Sandpile Model
- Orientations, semiorders, arrangements, and parking functions
- A sandpile model for proportionate growth
- Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
- Directed nonabelian sandpile models on trees
- Rotor-routing and spanning trees on planar graphs
- A Loop Reversibility and Subdiffusion of the Rotor-Router Walk
- Critical groups for Hopf algebra modules
- On the complexity of the chip-firing reachability problem
- Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields
- Abelian sandpiles: an overview and results on certain transitive graphs
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- A family of matrix-tree multijections
- Convergence of the random Abelian sandpile
- Spiral Structures in the Rotor-Router Walk
- Anchored burning bijections on finite and infinite graphs
- Rotor-Router Walk on a Semi-infinite Cylinder
- Abelian networks IV. Dynamics of nonhalting networks
- Rotor walks on transient graphs and the wired spanning forest
- Discrete analogue computing with rotor-routers
- Proportionate growth in patterns formed in the rotor-router model
- Solution manifold and Its Statistical Applications
- Local-to-global principles for rotor walk
- A Recurrent Rotor-Router Configuration in Z^3
- Sandpiles and unicycles on random planar maps
- Random walks with local memory
- Chip-Firing Games, -Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem
- Escape rates for rotor walk in Z^d
- Reachability Switching Games
- Abelian logic gates
- Homomesy in products of two chains
- Euler tours and unicycles in the rotor-router model
- Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs
- Tight contact structures on Seifert surface complements
- Recurrence of horizontal-vertical walks
- Determining Genus From Sandpile Torsor Algorithms
- A novel Recurrence-Transience transition and Tracy-Widom growth in a cellular automaton with quenched noise
- Multi-Eulerian tours of directed graphs
- Perfect boundaries in rotor-router aggregation on cylinders
- On the Classification of Universal Rotor-Routers
- A Greedy Chip-firing Game
- Sandpiles, spanning trees, and plane duality