Compatible sequences and a slow Winkler percolation

Date Issued
2004-11-01Publisher Version
10.1017/S0963548304006340Author(s)
Gacs, Peter
Metadata
Show full item recordPermanent 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
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 ... -
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 ... -
Size-resolved aerosol fluxes above a temperate broadleaf forest
Petroff, A.; Murphy, J.G.; Thomas, S.C.; Geddes, Jeffrey A. (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 ...