Show simple item record

dc.contributor.authorGacs, Peteren_US
dc.date.accessioned2018-06-19T13:47:39Z
dc.date.available2018-06-19T13:47:39Z
dc.date.issued2004-11-01
dc.identifierhttp://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.citationP 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.issn0963-5483
dc.identifier.urihttps://hdl.handle.net/2144/29414
dc.description.abstractTwo 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.extentp. 815 - 856en_US
dc.languageEnglish
dc.publisherCambridge University Pressen_US
dc.relation.ispartofCombinatorics, Probability and Computing
dc.subjectScience & technologyen_US
dc.subjectTechnologyen_US
dc.subjectPhysical sciencesen_US
dc.subjectComputer science, theory & methodsen_US
dc.subjectMathematicsen_US
dc.subjectStatistics & probabilityen_US
dc.subjectComputer scienceen_US
dc.subjectDependent percolationen_US
dc.subjectMathematical sciencesen_US
dc.subjectInformation and computing sciencesen_US
dc.subjectComputation theory & mathematicsen_US
dc.titleCompatible sequences and a slow Winkler percolationen_US
dc.typeArticleen_US
dc.identifier.doi10.1017/S0963548304006340
pubs.elements-sourceweb-of-scienceen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US


This item appears in the following Collection(s)

Show simple item record