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.
-
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 ... -
Size-resolved aerosol fluxes above a temperate broadleaf forest
(PERGAMON-ELSEVIER SCIENCE LTD, 2018-10-01)Aerosol fluxes were measured by eddy-correlation for 8 weeks of the summer and fall of 2011 above a temperate broadleaf forest in central Ontario, Canada. These size-resolved measurements apply to particles with optical ... -
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 ...
