Boston University Libraries OpenBU
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item

    Compatible sequences and a slow Winkler percolation

    Thumbnail
    Date Issued
    2004-11-01
    Publisher Version
    10.1017/S0963548304006340
    Author(s)
    Gacs, Peter
    Share to FacebookShare to TwitterShare by Email
    Export Citation
    Download to BibTex
    Download to EndNote/RefMan (RIS)
    Metadata
    Show full item record
    Permanent Link
    https://hdl.handle.net/2144/29414
    Citation (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/S0963548304006340
    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.
    Collections
    • BU Open Access Articles [3664]
    • CAS: Computer Science: Scholarly Papers [186]

    Related items

    Showing items related by title, author, creator and subject.

    • Thumbnail

      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 ...
    • Thumbnail

      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 ...
    • Thumbnail

      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 ...

    Boston University
    Contact Us | Send Feedback | Help
     

     

    Browse

    All of OpenBUCommunities & CollectionsIssue DateAuthorsTitlesSubjectsThis CollectionIssue DateAuthorsTitlesSubjects

    Deposit Materials

    LoginNon-BU Registration

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Boston University
    Contact Us | Send Feedback | Help