Source-linked AI summary
Chip-Firing and Rotor-Routing on Directed Graphs
Alexander E. Holroyd, Lionel Levine, Karola Meszaros, Yuval Peres, James Propp, David B. Wilson
TL;DR
The paper addresses the need for a rigorous, self-contained account of abelian sandpiles and rotor-routing on finite directed graphs and their connections. It develops their core theories, algebraic structures, and interactions, including results for Eulerian graphs and stacks. The survey organizes established results alongside open questions about limiting shapes and rotor-router periods.
Problem
The paper surveys abelian sandpile and rotor-router models on finite directed graphs, focusing on their connections and unresolved questions.
Method
The paper develops the models' basic theories and algebraic structures, including recurrent configurations, sandpile-group actions, cluster-firing, and cycle-popping.
Results
Recurrent chip configurations form an abelian group isomorphic to the sandpile group, while the survey derives stronger connections between the models and related graph-theoretic results.
Takeaways & Limitations
The survey provides a unified framework for studying chip-firing and rotor-routing on directed graphs while identifying several intriguing open problems.
Takeaways & Limitations
For H > −2, even the existence of a limiting shape for S_n,H has not been proved.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper surveys the abelian sandpile and rotor-router models on finite directed graphs, developing their basic theories and emphasizing their algebraic and combinatorial connections.
- Related work: The models were discovered independently across several communities, including statistical physics, pedagogy, arithmetic geometry, and graph-based rotor-routing research.The height arrow model is presented as a common generalization of rotor-routing and chip-firing.
- Models: The abelian sandpile model evolves chips by firing vertices with sufficiently many chips, and the final firing order does not affect the result.A vertex fires by sending one chip along each outgoing edge; stabilization occurs when no positive-outdegree vertex can fire.
- Models: The rotor-router model fixes a cyclic ordering of outgoing edges and routes each chip by advancing the rotor before traversing the selected edge.A chip stops at a sink or continues walking indefinitely if it never reaches one.
- Paper scope: The paper develops sandpile groups and recurrent chip configurations, then characterizes recurrent rotor configurations using oriented spanning trees.It also studies the sandpile-group action on recurrent rotor configurations and derives bijections between recurrent configurations of the two models.
- Paper scope: The survey uses these connections to give proofs of the Matrix-Tree Theorem and the enumeration of Eulerian tours by oriented spanning trees.These results arise from the sandpile-group action and recurrent rotor configurations.
2. Chip-Firing
This section defines chip-firing on directed graphs, establishes order-independent stabilization and commuting chip additions under a global sink, and connects recurrent configurations with the sandpile group.
- Definitions: Directed graphs may include self-loops and multiple edges, and a global sink is reachable by a directed path from every other vertex.A global sink is the unique sink when one exists.
- Definitions: A chip configuration assigns nonnegative integers to non-sink vertices; firing an active vertex sends one chip along each outgoing edge.Stability means every non-sink vertex has fewer chips than its out-degree.
- Stabilization: If two firing histories start from the same configuration and both stabilize, they have equal lengths, the same final configuration, and identical firing counts at every vertex.If one history stabilizes, no vertex fires more often in another permissible history.
- Stabilization: Every chip configuration stabilizes on a digraph with a global sink.The proof bounds firings by tracing directed paths to the sink, while a sharper bound may be available in special connected graphs.
- Abelian property: Chip addition operators add one chip at a vertex and stabilize; on graphs with a global sink, these operators commute.Consequently, sequential chip additions equal simultaneous addition followed by stabilization.
- Sandpile group: The reduced Laplacian records non-sink firing operations, while recurrent configurations provide canonical representatives of sandpile-group equivalence classes.Each equivalence class contains at most one recurrent configuration, and recurrent configurations form an abelian group isomorphic to the sandpile group.
- Recurrent configurations: Recurrent configurations are equivalently characterized by reachability properties and a condition involving every strongly connected component after removing the sink.The supplied statement introduces four equivalent conditions, including reachability from every configuration.
3. Rotor-Routing
Rotor-routing replaces chip-firing’s waiting step with deterministic rotor updates, yielding nearly equal edge usage and an abelian stopping process. The survey characterizes recurrent states, connects them to spanning trees and the sandpile group, and relates rotor-router walks to random-walk hitting estimates.
- Rotor-router dynamics: Rotor-routing cycles each vertex’s outgoing edges to route successive chips, avoiding chip-firing’s waiting requirement while achieving nearly equal edge usage.At a vertex, the rotor advances to its successor before the chip traverses that edge.
- Rotor-router dynamics: On sink-free digraphs, the rotor-router operation preserves unicycles and permutes their finite state space.A unicycle has one directed rotor cycle containing the chip; every step produces another unicycle.
- Recurrent states: For strongly connected digraphs, recurrent single-chip-and-rotor states are exactly the unicycles.The characterization combines reachability to a globally reachable vertex with the converse implication that recurrent states must be unicycles.
- Rotor-router and sandpile groups: With a global sink, recurrent rotor configurations are precisely acyclic configurations, equivalently oriented spanning trees rooted at the sink.Chip addition operators act as permutations on these configurations, and the sandpile group action is transitive and free.
- Rotor-router and sandpile groups: The rotor-router group on oriented spanning trees is isomorphic to the sandpile group, whose action depends only on chip configurations modulo the reduced Laplacian.The number of rooted oriented spanning trees is also the determinant of the reduced Laplacian.
- Random-walk comparison: Rotor-router walks approximate independent random-walk hitting counts with a bound independent of the initial rotor configuration and chip configuration.The result applies to walks stopped upon first hitting a specified vertex set, and analogous bounds extend to some infinite directed graphs.
4. Eulerian Graphs
For Eulerian digraphs with a sink, the paper characterizes recurrent and superstable sandpiles, proves abelian cluster-firing, and derives connections among rotor-routing, spanning trees, Eulerian tours, and sandpile groups.
- Eulerian graphs: Eulerian digraphs are strongly connected with equal in-degree and out-degree at every vertex; deleting one vertex’s outgoing edges produces an Eulerian digraph with sink.The section develops results that need not hold for general digraphs.
- Recurrent configurations: The burning algorithm tests recurrence by adding the sink’s contribution β and checking whether every non-sink vertex fires during stabilization.For recurrent σ, stabilization of σ + β fires each vertex exactly once.
- Recurrent configurations: A stable configuration is recurrent exactly when every nonempty induced subgraph excluding the sink is ample for that configuration.A subgraph is ample when one of its vertices has at least as many chips as its in-degree within the subgraph.
- Superstable configurations: Superstable configurations are defined by the impossibility of allowed cluster-firings and satisfy δ − 1 − σ recurrent.Here δ gives each vertex its out-degree chips, while 1 gives one chip to each vertex.
- Superstable configurations: Every equivalence class modulo the reduced Laplacian contains a unique superstable configuration, making cluster-firing abelian on Eulerian digraphs.Any terminating cluster-firing sequence from the same initial configuration reaches the same superstable state.
- Rotor-routing and spanning trees: Iterating rotor-routing m times from a unicycle on an Eulerian digraph with m edges traverses an Eulerian tour and returns the full system to its initial state.This yields a bijective route to the classical relation between Eulerian tours and oriented spanning trees.
- Sandpile groups: The sandpile group is independent of the chosen sink in Eulerian digraphs, and dual undirected planar graphs have isomorphic sandpile groups.The sink-independence result supports the planar duality theorem.
5. Stacks and Cycle-Popping
The paper generalizes rotor-routing to infinitive stacks and uses cycle-popping to analyze acyclicity, chip addition, and constructive invertibility.
- Stack configurations: Each non-sink vertex receives a bi-infinite stack of outgoing edges; popping shifts a stack forward, while reverse popping shifts it backward.Infinitivity guarantees that every edge appears arbitrarily far in both stack directions and that rotor-router walks eventually reach the sink.
- Stack configurations: A stack configuration is acyclic when its zeroth stack elements contain no directed cycle; reverse popping a directed cycle shifts every stack on that cycle backward.The zeroth elements define the associated rotor configuration.
- Cycle-popping: Any infinitive stack configuration with a global sink can be transformed by finitely many cycle-poppings into an acyclic configuration.The resulting acyclic configuration is independent of the chosen cycle-popping sequence.
- Chip addition: The chip addition operator E_v adds a chip at v and routes it to the sink, and these operators commute with cycle-popping.This compatibility enables cycle-popping arguments for stack dynamics.
- Chip addition: For every acyclic infinitive stack configuration ρ and non-sink vertex v, there is an acyclic ρ′ satisfying E_vρ′ = ρ.The construction reverse-pops along a path and then removes any resulting cycles.
- Chip addition: When E_vρ′ = ρ for acyclic configurations, the path from v to the sink in the inverse configuration is the loop-erasure of the corresponding rotor-router path.This identifies the inverse construction with loop-erased rotor-router behavior.
6. Conjectures and Open Problems
The section surveys unresolved questions about sandpile aggregate shapes, sandpile identity limits, and rotor-router dynamics. It combines rigorous results with conjectures and simulations while emphasizing substantial unproved boundaries.
- Sandpile aggregation: Theorem 6.1 proves that the aggregate S_n,2−2d in Z^d is a discrete cube C(r_n) for some integer r_n.In two dimensions, this specializes to S_n,−2 being a square.
- Sandpile aggregation: Question 6.2 asks whether the Z^2 limiting shape is a regular (4H + 12)-gon or at least has dihedral symmetry D_4H+12.The rounded corners seen in simulations may or may not become negligible as n grows.
- Sandpile aggregation: Even the existence of a limiting shape for S_n,H has not been proved when H > −2, although the limiting shape becomes a ball as H → ∞ in all dimensions.The section also cites quantitative asymptotic results for stabilization with holes, including constants depending only on d and bounds for H ≥ 1 − d.
- Sandpile identities: For wired n × n grid graphs, identity configurations appear extremely similar across n and are conjectured to converge to a locally constant function almost everywhere.The conjecture states convergence of the rescaled functions f_n at every continuity point of a limiting function f; its apparent fractal structure remains intriguing.
- Rotor-router dynamics: Rotor-router questions ask whether non-Eulerian strongly connected graph families can have one unicycle orbit and what edge-traversal sequence periods can occur.In Eulerian digraphs, recurrent orbits have size equal to the number of edges and the two-edge record alternates 0, 1, whereas general periods remain open.