Abstract for the talk at 10.12.2012 (16:00 h)Colloquium of the Max Planck Institute
Vladas Sidoravicius (IMPA, Rio de Janeiro, Brazil)
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.