Chip-Firing and Rotor-Routing on $\mathbb{Z}^d$ and on Trees

Abstract

The sandpile group of a graph $G$ is an abelian group whose order is the number of spanning trees of $G$. We find the decomposition of the sandpile group into cyclic subgroups when $G$ is a regular tree with the leaves are collapsed to a single vertex. This result can be used to understand the behavior of the rotor-router model, a deterministic analogue of random walk studied first by physicists and more recently rediscovered by combinatorialists. Several years ago, Jim Propp simulated a simple process called rotor-router aggregation and found that it produces a near perfect disk in the integer lattice $\mathbb{Z}^2$. We prove that this shape is close to circular, although it remains a challenge to explain the near perfect circularity produced by simulations. In the regular tree, we use the sandpile group to prove that rotor-router aggregation started from an acyclic initial condition yields a perfect ball.

Keywords

• abelian sandpile
• chip-firing game
• regular tree
• rotor-router model
• sandpile group
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [info.info-hc] computer science [cs]/human-computer interaction [cs.hc]