Scheduling of Random Walks, Quasi-Isometries and Coordinate Percolation

In the late eighties Peter Winkler introduced the following problem: consider two independent discrete time random walks, X and Y, on the complete graph with N vertices. If the trajectories of X and Y are given, would it be possible, knowing all future steps of the walks, and just changing jump times only, keep X and Y apart forever, with positive probability? It became well known as Clairvoyant Demon Problem.

Soon after Noga Alon observed that this question is equivalent to the existence of a phase transition in a planar dependent percolation process. Remarkably, several other interesting questions such as Lipschitz embeddings of binary sequences and quasi-isometries between one dimensional random objects also could be reduced to a similar type of percolation.

During the lecture I will explain deep conceptual differences between N.Alon's percolation process and "usual" dependent percolation models, and difficulties to which it leads. At the second half of the talk I will present a proof of affirmative answer to the original Winkler question.