UP - logo
Univerza na Primorskem Univerzitetna knjižnica - vsi oddelki (UPUK)
  • Transitive closure in a polluted environment
    Gravner, Janko ; Kolesnik, Brett
    We introduce and study a new percolation model, inspired by recent works on jigsaw percolation, graph bootstrap percolation, and percolation in polluted environments. Start with an oriented graph G0 ... of initially occupied edges on n vertices, and iteratively occupy additional (oriented) edges by transitivity, with the constraint that only open edges in a certain random set can ever be occupied. All other edges are closed, creating a set of obstacles for the spread of occupied edges. When G0 is an unoriented linear graph, and leftward and rightward edges are open independently with possibly different probabilities, we identify three regimes in which the set of eventually occupied edges is either all open edges, the majority of open edges in one direction, or only a very small proportion of all open edges. In the more general setting where G0 is a connected unoriented graph of bounded degree, we show that the transition between sparse and full occupation of open edges occurs when the probability of open edges is (log n) −1/2+o(1). We conclude with several conjectures and open problems.
    Vir: Annals of applied probability. - ISSN 1050-5164 (Vol. 33, iss. 1, 2023, str. 107–126)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 179142915

    Povezava(-e):

    https://projecteuclid.org/journals/annals-of-applied-probability/volume-33/issue-1/Transitive-closure-in-a-polluted-environment/10.1214/22-AAP1810.short
    https://doi.org/10.1214/22-AAP1810
    DOI

vir: Annals of applied probability. - ISSN 1050-5164 (Vol. 33, iss. 1, 2023, str. 107–126)

loading ...
loading ...
loading ...

Vnos na polico