# zbMATH — the first resource for mathematics

The clairvoyant demon has a hard task. (English) Zbl 0974.60091
Summary: Consider the integer lattice $$L= \mathbb{Z}^2$$. For some $$m\geq 4$$, let us colour each column of this lattice independently and uniformly with one of $$m$$ colours. We do the same for the rows, independently of the columns. A point of $$L$$ will be called blocked if its row and column have the same colour. We say that this random configuration percolates if there is a path in $$L$$ starting at the origin, consisting of rightward and upward unit steps, avoiding the blocked points. As a problem arising in distributed computing, it has been conjectured that for $$m\geq 4$$ the configuration percolates with positive probability. This question remains open, but we prove that the probability that there is percolation to distance $$n$$ but not to infinity is not exponentially small in $$n$$. This narrows the range of methods available for proving the conjecture.

##### MSC:
 60K35 Interacting random processes; statistical mechanics type models; percolation theory 60C05 Combinatorial probability
Full Text: