The range of a rotor walk

DOI10.4169/AMER.MATH.MONTHLY.123.7.627MaRDI QIDQ4576529zbMATHOpenAlexWikidataFDO

Authors Laura Florescu, Lionel Levine, Yuval Peres

Publication date 12 July 2018

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.5533

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: In a emph{rotor walk} the exits from each vertex follow a prescribed periodic sequence. On an infinite Eulerian graph embedded periodically in $R^d$, we show that any simple rotor walk, regardless of rotor mechanism or initial rotor configuration, visits at least on the order of $t^{d/(d+1)}$ distinct sites in $t$ steps. We prove a shape theorem for the rotor walk on the comb graph with i.i.d. uniform initial rotors, showing that the range is of order $t^{2/3}$ and the asymptotic shape of the range is a diamond. Using a connection to the mirror model and critical percolation, we show that rotor walk with i.i.d. uniform initial rotors is recurrent on two different directed graphs obtained by orienting the edges of the square grid, the Manhattan lattice and the $F$-lattice. We end with a short discussion of the time it takes for rotor walk to cover a finite Eulerian graph.

Recommendations

• Range and speed of rotor walks on trees
• Rotor walks on general trees
• Transience and recurrence of rotor-router walks on directed covers of graphs
• Escape rates for rotor walks in \(\mathbb{Z}^d\)
• A law of large numbers for the range of rotor walks on periodic trees

Cites work

• scientific article; zbMATH DE number 5764860 (Why is no real title available?)
• scientific article; zbMATH DE number 928733 (Why is no real title available?)
• A distributed ant algorithm for efficiently patrolling a network
• Chip-Firing and Rotor-Routing on Directed Graphs
• Efficiently searching a graph by a smell-oriented vertex process
• Escape rates for rotor walks in \(\mathbb{Z}^d\)
• Euler Tour Lock-In Problem in the Rotor-Router Model
• Honest bernoulli excursions
• Percolation
• Recurrent rotor-router configurations
• Rotor walks and Markov chains
• Rotor walks on general trees
• Rotor-router aggregation on the comb
• Rotor-router aggregation on the layered square lattice
• Simulating a Random Walk with Constant Error
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The range of a random walk on a comb
• The range of a rotor walk
• Tight bounds for quasirandom rumor spreading
• Traversing Directed Eulerian Mazes

Cited in

(18)

• Infinite-step stationarity of rotor walk and the wired spanning forest
• A law of large numbers for the range of rotor walks on periodic trees
• A loop reversibility and subdiffusion of the rotor-router walk
• Spiral structures in the rotor-router walk
• Local-to-global principles for the hitting sequence of a rotor walk
• Escape rates for rotor walks in \(\mathbb{Z}^d\)
• Range and speed of rotor walks on trees
• Erratum to: ``Transience and recurrence of rotor-router walks on directed covers of graphs
• Abelian networks. II: Halting on all inputs
• The range of a rotor walk
• Laplacian growth, sandpiles, and scaling limits
• Interpolating between random walk and rotor walk
• Rotor walks on transient graphs and the wired spanning forest
• Recurrence of horizontal-vertical walks
• Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
• Random walks with local memory
• Transience and recurrence of rotor-router walks on directed covers of graphs
• A rotor configuration with maximum escape rate

This page was built for publication: The range of a rotor walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4576529)