Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T04:15:25.272Z 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: [email protected])

Abstract

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.

Type
Paper
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)