Itamar Landau ; Lionel Levine ; Yuval Peres - Chip-Firing and Rotor-Routing on $\mathbb{Z}^d$ and on Trees

dmtcs:3618 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3618
Chip-Firing and Rotor-Routing on $\mathbb{Z}^d$ and on TreesArticle

Authors: Itamar Landau 1; Lionel Levine 1; Yuval Peres 2

  • 1 Department of Mathematics [Berkeley]
  • 2 Theory Group - Microsoft Research

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.


Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
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]

Consultation statistics

This page has been seen 331 times.
This article's PDF has been downloaded 374 times.