Scheduling of non-colliding random walks

2014/11/14 by Basu, Riddhipratim, Sidoravicius, Vladas, Sly, Allan
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1411.4041

Abstract

On the complete graph \calK_M with M ≥3 vertices consider two independent discrete time random walks \mathbbX and \mathbbY, choosing their steps uniformly at random. A pair of trajectories \mathbbX = \ X₁, X₂, … \ and \mathbbY = \Y₁, Y₂, … \ is called \itnon-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 \\mathbbX,\mathbbY \ 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.

Related

• Clairvoyant scheduling of random walks
• Recurrent graphs where two independent random walks collide finitely often
• Meeting Times of Non-atomic Random Walks
• Transience and recurrence of random walks on percolation clusters in an ultrametric space
• Mixing time for random walk on supercritical dynamical percolation