MIT Combinatorics Seminar

A whirling tour of chip-firing and rotor-routing

Jim Propp  (University of Massachusetts Lowell)

Wednesday, April 25, 2007    4:15 pm    Room 2-136


Dumitriu, Tetali and Winkler have described a "whirling tours" algorithm that computes the expected time for random walk on a tree to get from a designated starting vertex to a designated target vertex (and that incidentally always gives a whole number). I'll explain why their algorithm works by situating it in the context of the Eulerian walkers model (aka rotor-router walk) and the abelian sandpile model (aka chip-firing).

The slides are available at http://jamespropp.org/tour0.pdf.