Rutgers Discrete Mathematics Seminar

Title: Range of a Rotor Walk and Recurrence of Directed Lattices

Speaker: Laura Florescu, NYU

Date: Monday, February 16, 2015 11:00 am

Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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 td/(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 t2/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.

Joint work with Lionel Levine and Yuval Peres.