  On the complete graph ${\cal{K}}_M$ with $M \ge3$ vertices consider two
independent discrete time random walks $\mathbb{X}$ and $\mathbb{Y}$, choosing
their steps uniformly at random. A pair of trajectories $\mathbb{X} = \{ X_1,
X_2, \dots \}$ and $\mathbb{Y} = \{Y_1, Y_2, \dots \}$ is called
{\it{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
$\{\mathbb{X},\mathbb{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.
