Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2025-01-06T04:09:31.106Z Has data issue: false hasContentIssue false
  • English
  • Français

The Clairvoyant Demon Has a Hard Task

Published online by Cambridge University Press:  14 February 2001

PETER GÁCS
PETER GÁCS
Affiliation:
Computer Science Department, Boston University, Boston, MA 02215-2411, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider the integer lattice L = ℤ2. For some m [ges ] 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 [ges ] 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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 9 , Issue 5 , September 2000 , pp. 421 - 424
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)