The Range of a Rotor Walk

Laura Florescu, Lionel Levine, Yuval PeresAm. Math. mon 2016

TL;DR

This paper investigates the "range" of a rotor walk, a deterministic analogue of a random walk on graphs. The authors establish lower bounds on how much territory a rotor walk can explore on infinite Eulerian graphs and prove a shape theorem for the comb graph, showing it explores more efficiently than a standard random walk. They also demonstrate recurrence for rotor walks on specific lattices, connecting it to percolation theory.

What Problem Does This Paper Address?

The paper tackles fundamental questions about the exploration capabilities of rotor walks. Specifically, it asks:

  1. How much "territory" (distinct sites) does a rotor walk cover in a given time $t$?
  2. How long does it take for a rotor walk to completely explore a finite graph?

Rotor walks are deterministic processes where each vertex has a "rotor" that dictates the next exit edge. This deterministic nature makes them an interesting contrast to random walks, which are governed by probability. While random walks have been extensively studied in terms of their exploration properties (e.g., cover time, range), the analogous questions for rotor walks are less understood, especially concerning their efficiency and asymptotic behavior. The paper aims to provide theoretical bounds and insights into these exploration dynamics.

Methods

The paper employs a combination of techniques, drawing from graph theory, probability theory, and percolation theory:

  • Excursion Decomposition: A key technique is decomposing the rotor walk into a sequence of "excursions." An excursion is defined as a walk starting from a vertex until it returns to that vertex a specific number of times (equal to its degree). This decomposition simplifies the analysis of the walk's behavior.
  • Lower Bounds via Edge Usage: The authors derive lower bounds on the range by analyzing how many edges are traversed. They relate the number of visited sites to the total number of edge traversals and the graph's structure (degree of vertices, volume growth).
  • Shape Theorems: For specific graphs like the comb graph, they prove "shape theorems." These theorems describe the asymptotic shape of the set of visited sites as time goes to infinity, showing it approaches a specific geometric form (a diamond in this case).
  • Connection to Percolation Theory: For proving recurrence on certain lattices (Manhattan and F-lattices), the paper establishes a connection to critical bond percolation. This involves mapping the rotor walk's behavior to the presence or absence of cycles of "closed" edges in a related lattice, leveraging known results from percolation theory.
  • Mirror Model: The connection to percolation is further elaborated through the "mirror model," where the behavior of the rotor walk is related to how a "light ray" reflects off mirrors placed at vertices, determined by the percolation state of a dual lattice.
  • Cover Time Analysis: For finite graphs, the paper analyzes the "cover time" (time to visit all vertices or traverse all edges) by relating it to the number of excursions and the graph's diameter and number of edges.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Rotor Walks Explore Efficiently: On certain graphs, like the comb graph, rotor walks can explore territory significantly more efficiently than standard random walks. This is demonstrated by the $t^{2/3}$ range growth on the comb, compared to $t^{1/2} \log t$ for random walks.
  • Recurrence is Tied to Percolation: The recurrence of uniform rotor walks on specific lattices (Manhattan and F-lattices) is deeply linked to the existence of infinite cycles of closed edges in critical bond percolation. This provides a powerful tool for analyzing the long-term behavior of these deterministic walks.
  • Deterministic Nature Offers Structure: The deterministic nature of rotor walks, while complex, allows for structured analysis through excursion decomposition and connections to geometric properties like shape theorems.
  • Initial Conditions Matter: The paper highlights that the initial configuration of rotors can significantly impact the walk's behavior, leading to transient or recurrent behavior.

Key Results

  • Lower Bound on Range (Theorem 1.1): For any Eulerian graph embedded in $\mathbb{R}^d$, the number of distinct sites visited by a rotor walk in $t$ steps is at least $c t^{d/(d+1)}$. This provides a general lower bound on exploration.
  • Shape Theorem on Comb Graph (Theorem 1.4): For uniform rotor walks on the comb graph, the range has order $t^{2/3}$, and its asymptotic shape is a diamond.
  • Recurrence on Lattices (Theorem 1.5): Uniform rotor walks are recurrent on the F-lattice and the Manhattan lattice.
  • Cover Time Bounds (Theorem 6.1): For a finite Eulerian graph with diameter $D$ and $|E|$ edges, the vertex cover time is bounded by $D|E|$ and the edge cover time by $(D+1)|E|$.

Limitations and Future Work

  • Conjecture on $\mathbb{Z}^2$ Shape: The paper mentions the Kapri-Dhar conjecture that the range of a clockwise uniform rotor walk on $\mathbb{Z}^2$ is asymptotically a disk. Proving this remains an open problem, and the paper's results on the comb graph are a step towards understanding such shape theorems.
  • Upper Bounds Depend on Initial Configuration: While lower bounds on the range are established, precise upper bounds are more challenging and depend heavily on the initial rotor configuration. Theorem 1.2 shows that a specific initial configuration can lead to linear growth in the range.
  • Comparison of Lattices: The paper notes that while uniform rotor walks are recurrent on both the F-lattice and Manhattan lattice, their exploration behavior appears different, with the Manhattan lattice showing $t^{2/3}$ range growth and the F-lattice showing linear growth. Further investigation into these differences is suggested.
  • Random Walk vs. Rotor Walk Cover Time: The paper discusses the relationship between random walk cover times and rotor walk cover times, noting that the methods used for random walks are different and that rotor walk cover times can be significantly larger in some cases. The question of whether the bounds derived for rotor walk cover time are tight remains an area for further study.

Summary updated

BibTeX
@article{florescu2016range,
  author = {Laura Florescu and Lionel Levine and Yuval Peres},
  title = {{The Range of a Rotor Walk}},
  journal = {Am. Math. mon},
  year = {2016},
}

Loading related content...

Figure