On the complete graph @math with @math vertices consider two independent discrete time random walks @math and @math , choosing their steps uniformly at random. A pair of trajectories @math and @math 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 @math the set of pairs of non-colliding trajectories @math 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 @math . In this paper we establish the conjecture.
In @cite_17 a multi-scale structure was developed to tackle random embedding problems which can be recast in co-ordinate percolation framework. As a corollary of a general embedding theorem, it was proved there that an i.i.d. Bernoulli sequence can almost surely be embedded into another in a Lipschitz manner provided that the Lipschitz constant is sufficiently large. It also led to a proof of rough isometry of two one-dimensional Poisson processes as well as a new proof of Winkler's compatible sequence problem. In this work we build upon the methods of @cite_17 , using a similar multi-scale structure, but with crucial adaptations. An earlier proof of Theorem 1 appeared in @cite_12 with a very difficult multi-scale argument. Our proof is different and we believe gives a clearer inductive structure. We also believe that our proof can be adapted to deal with this problem on several other graphs, as well as in the case where there are multiple random walks.
@cite_12 @cite_17
1971206237 2146896147 2109426593 2951102908
We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. (Random Str Algorithm 37(1):85–99, 2010) asked whether there exists an increasing (M )-Lipschitz embedding from one i.i.d. Bernoulli sequence into an independent copy with positive probability. We give a positive answer for large enough (M ). A closely related problem is to show that two independent Poisson processes on ( R ) are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled (Ann Appl Probab 20:462–494, 2010). Our theorem also gives a new proof to Winkler’s compatible sequences problem. Our approach does not explicitly depend on the particular geometry of the problems and we believe it will be applicable to a range of multi-scale and random embedding problems. Does there exist a Lipschitz injection of ℤd into the open set of a site percolation process on ℤD, if the percolation parameter p is sufficiently close to 1? We prove a negative answer when d = D and also when d ≥ 2 if the Lipschitz constant M is required to be 1. Earlier work of Dirr, Dondl, Grimmett, Holroyd and Scheutzow yields a positive answer for d < D and M = 2. As a result, the above question is answered for all d, D and M. Our proof in the case d = D uses Tucker’s lemma from topological combinatorics, together with the aforementioned result for d < D. One application is an affirmative answer to a question of Peled concerning embeddings of random patterns in two and more dimensions. A proof is provided of a strong law of large numbers for a one-dimensional random walk in a dynamic random environment given by a supercritical contact process in equilibrium. The proof is based on a coupling argument that traces the space-time cones containing the infection clusters generated by single infections and uses that the random walk eventually gets trapped inside the union of these cones. For the case where the local drifts of the random walk are smaller than the speed at which infection clusters grow, the random walk eventually gets trapped inside a single cone. This in turn leads to the existence of regeneration times at which the random walk forgets its past. The latter are used to prove a functional central limit theorem and a large deviation principle. The qualitative dependence of the speed, the volatility and the rate function on the infection parameter is investigated, and some open problems are mentioned. There exists a Lipschitz embedding of a d-dimensional comb graph (consisting of infinitely many parallel copies of Z^ d-1 joined by a perpendicular copy) into the open set of site percolation on Z^d, whenever the parameter p is close enough to 1 or the Lipschitz constant is sufficiently large. This is proved using several new results and techniques involving stochastic domination, in contexts that include a process of independent overlapping intervals on Z, and first-passage percolation on general graphs.