TY - GEN

T1 - Scheduling of Non-Colliding Random Walks

AU - Basu, Riddhipratim

AU - Sidoravicius, Vladas

AU - Sly, Allan

N1 - Publisher Copyright:
© Springer Nature Singapore Pte Ltd. 2019.

PY - 2019

Y1 - 2019

N2 - On the complete graph KM with M ≥ 3 vertices consider two independent discrete time random walks X and Y, choosing their steps uniformly at random. A pair of trajectories X = {X1, X2, ...} and Y = {Y1, Y2, ...} is called non-colliding, if by delaying their jump times one can keep both walks at distinct vertices forever. It was conjectured by P. Winkler that for large enough M the set of pairs of non-colliding trajectories {X, Y} has positive measure. N. Alon translated this problem to the language of coordinate percolation, a class of dependent percolation models, which in most situations is not tractable by methods of Bernoulli percolation. In this representation Winkler’s conjecture is equivalent to the existence of an infinite open cluster for large enough M. In this paper we establish the conjecture building upon the renormalization techniques developed in [4].

AB - On the complete graph KM with M ≥ 3 vertices consider two independent discrete time random walks X and Y, choosing their steps uniformly at random. A pair of trajectories X = {X1, X2, ...} and Y = {Y1, Y2, ...} is called non-colliding, if by delaying their jump times one can keep both walks at distinct vertices forever. It was conjectured by P. Winkler that for large enough M the set of pairs of non-colliding trajectories {X, Y} has positive measure. N. Alon translated this problem to the language of coordinate percolation, a class of dependent percolation models, which in most situations is not tractable by methods of Bernoulli percolation. In this representation Winkler’s conjecture is equivalent to the existence of an infinite open cluster for large enough M. In this paper we establish the conjecture building upon the renormalization techniques developed in [4].

KW - Dependent percolation

KW - Renormalization

UR - http://www.scopus.com/inward/record.url?scp=85085735663&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85085735663&partnerID=8YFLogxK

U2 - 10.1007/978-981-15-0302-3_4

DO - 10.1007/978-981-15-0302-3_4

M3 - Conference contribution

AN - SCOPUS:85085735663

SN - 9789811503016

T3 - Springer Proceedings in Mathematics and Statistics

SP - 90

EP - 137

BT - Sojourns in Probability Theory and Statistical Physics - III - Interacting Particle Systems and Random Walks, A Festschrift for Charles M. Newman

A2 - Sidoravicius, Vladas

PB - Springer

T2 - International Conference on Probability Theory and Statistical Physics, 2016

Y2 - 25 March 2016 through 27 March 2016

ER -