Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185153
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 19, 2015 - 11:42:08 AM
Last modification on : Wednesday, August 7, 2019 - 12:19:22 PM
Long-term archiving on: : Friday, November 20, 2015 - 10:32:00 AM

File

dmAJ0151.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185153, version 1

Collections

Citation

Itamar Landau, Lionel Levine, Yuval Peres. Chip-Firing and Rotor-Routing on $\mathbb{Z}^d$ and on Trees. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. pp.587-598. ⟨hal-01185153⟩

Share

Metrics

Record views

503

Files downloads

1090