University of Georgia
Mathematics and Computer Science Colloquium
Peter Winkler
Bell Labs
February 5, 1999
Percolation and Collision
Abstract:
Two tokens take simple random walks on the same graph G. The
"clairvoyant demon" conjecture says that (with positive probability)
if the walks are known in advance, they can be scheduled so as to
avoid collision forever. This conjecture remains open.
We show that if the tokens can be moved backward as well as forward,
then (on most graphs) they can indeed be advanced arbitrarily far
without colliding. By restating the problem in terms of dependent
percolation and proving a curious diamond lemma, we can completely
characterize the Markov chains which have this "collision avoidance"
property.