Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T04:58:23.777Z Has data issue: false hasContentIssue false

Compatible Sequences and a Slow Winkler Percolation

Published online by Cambridge University Press:  03 November 2004

PETER GÁCS
Affiliation:
Computer Science Department, Boston University, 111 Cummington Street, Boston, MA 02215, USA (e-mail: gacs@bu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2004 Cambridge University Press