Journal of Combinatorics

Volume 3 (2012)

Number 2

Recurrent rotor-router configurations

Pages: 185 – 194

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n2.a3

Authors

Omer Angel (Department of Mathematics, University of British Columbia, Vancouver, B.C., Canada)

Alexander E. Holroyd (Microsoft Research, Redmond, Wash., U.S.A.)

Abstract

We prove the existence of recurrent initial configurations for therotor walk on many graphs, including $Z^d$, and planar graphs withlocally finite embeddings. We also prove that recurrence andtransience of rotor walks are invariant under changes in the startingvertex and finite changes in the initial configuration.

Keywords

rotor walk, rotor-router, quasi-random, recurrence

2010 Mathematics Subject Classification

05C25, 82C20

Published 28 September 2012