Compatible sequences and a slow Winkler percolation
Permanent Link
https://hdl.handle.net/2144/29414Citation (published version)
P Gacs. 2004. "Compatible sequences and a slow Winkler percolation." Combinatorics, Probability and Computing, Volume 13, Issue 6, pp. 815 - 856 (42). https://doi.org/10.1017/S0963548304006340Abstract
Two infinite 0–1 sequences are called compatible when it is possible to cast out $0\,$s from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two 0–1 sequences are random i.i.d. and independent from each other, with probability $p$ of $1\,$s, then if $p$ is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behaviour: the probability that the origin is blocked at distance $n$ but not closer decreases only polynomially fast and not, as usual, exponentially.
Collections
Related items
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
(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
(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
(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 ...
