Chip-Firing and Rotor-Routing on 𝕫d and on Trees
Itamar Landau, Lionel Levine, Yuval Peres
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
𝕫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.
Full Text: GZIP Compressed PostScript PostScript PDF