TRANSITIVE CLOSURE IN A POLLUTED ENVIRONMENT

• 成果类型: Article
• 署名作者: Gravner, Janko; Kolesnik, Brett
• 署名单位: University of California System; University of California Davis; University of California System; University of California San Diego
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1810
• 发表日期: 2023
• 页码: 107-126
• 关键词: bootstrap percolation; jigsaw percolation; sharp threshold; inequalities

摘要

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 occu-pied 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 obsta-cles for the spread of occupied edges. When G0 is an unoriented linear graph, and leftward and rightward edges are open independently with possibly dif-ferent 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 gen-eral 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.