Loading [MathJax]/jax/output/HTML-CSS/jax.js

Itamar Landau ; Lionel Levine ; Yuval Peres - Chip-Firing and Rotor-Routing on Zd 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 Zd and on TreesConference paper

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 Z2. 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 417 times.
This article's PDF has been downloaded 443 times.