The range of a rotor walk

DOI10.4169/AMER.MATH.MONTHLY.123.7.627zbMATH Open1391.60019arXiv1408.5533OpenAlexW2963425489WikidataQ58122356 ScholiaQ58122356MaRDI QIDQ4576529FDOQ4576529

Authors: Laura Florescu, Lionel Levine, Yuval Peres 

Publication date: 12 July 2018

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

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.

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

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

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Cites Work

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

Cited In (9)

• Random walks with local memory
• Infinite-step stationarity of rotor walk and the wired spanning forest
• Local-to-global principles for the hitting sequence of a rotor walk
• Recurrence of horizontal-vertical walks
• Abelian networks. II: Halting on all inputs
• Transience and recurrence of rotor-router walks on directed covers of graphs
• The Range of a Rotor Walk
• Range and speed of rotor walks on trees
• Laplacian growth, sandpiles, and scaling limits

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)