The clairvoyant demon has a hard task
MetadataShow full item record
Citation (published version)P Gacs. 2000. "The clairvoyant demon has a hard task." Combinatorics Probability & Computing, Volume 9, Issue 5, pp. 421 - 424 (4).
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.
Showing items related by title, author, creator and subject.
Integrating archaeology and ancient DNA analysis to address invasive species colonization in the Gulf of Alaska West, Catherine; Hofman, Courtney A.; Ebbert, Steve; Martin, John; Shirazi, Sabrina; Dunning, Samantha; Maldonado, Jesus E. (WILEY, 2017-10-01)The intentional and unintentional movement of plants and animals by humans has transformed ecosystems and landscapes globally. Assessing when and how a species was introduced are central to managing these transformed ...
Contribution of leaf specular reflection to canopy reflectance under black soil case using stochastic radiative transfer model Yang, Bin; Knyazikhin, Yuri; Zhao, Haimeng; Ma, Yuzhong (Elsevier Science BV, 2018-12-15)Numerous canopy radiative transfer models have been proposed based on the assumption of “ideal bi-Lambertian leaves” with the aim of simplifying the interactions between photons and vegetation canopies. This assumption may ...
Inconsistencies of interannual variability and trends in long-term satellite leaf area index products Jiang, Chongya; Ryu, Youngryel; Fang, Hongliang; Myneni, Ranga; Claverie, Martin; Zhu, Zaichun (2017-07-06)Understanding the long-term performance of global satellite leaf area index (LAI) products is important for global change research. However, few effort has been devoted to evaluating the long-term time-series consistencies ...