dc.contributor.author Gacs, Peter en_US dc.date.accessioned 2018-06-19T13:47:39Z dc.date.available 2018-06-19T13:47:39Z dc.date.issued 2004-11-01 dc.identifier http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000225633300003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e74115fe3da270499c3d65c9b17d654 dc.identifier.citation 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/S0963548304006340 dc.identifier.issn 0963-5483 dc.identifier.uri https://hdl.handle.net/2144/29414 dc.description.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. en_US dc.format.extent p. 815 - 856 en_US dc.language English dc.publisher Cambridge University Press en_US dc.relation.ispartof Combinatorics, Probability and Computing dc.subject Science & technology en_US dc.subject Technology en_US dc.subject Physical sciences en_US dc.subject Computer science, theory & methods en_US dc.subject Mathematics en_US dc.subject Statistics & probability en_US dc.subject Computer science en_US dc.subject Dependent percolation en_US dc.subject Mathematical sciences en_US dc.subject Information and computing sciences en_US dc.subject Computation theory & mathematics en_US dc.title Compatible sequences and a slow Winkler percolation en_US dc.type Article en_US dc.identifier.doi 10.1017/S0963548304006340 pubs.elements-source web-of-science en_US pubs.notes Embargo: Not known en_US pubs.organisational-group Boston University en_US pubs.organisational-group Boston University, College of Arts & Sciences en_US pubs.organisational-group Boston University, College of Arts & Sciences, Department of Computer Science en_US pubs.publication-status Published en_US
﻿