The time of bootstrap percolation with dense initial sets for all thresholds

DOI10.1002/RSA.20529MaRDI QIDQ3192370zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Paul Smith, Andrew J. Uzzell

Publication date 12 October 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.4339

zbMATH Keywords

bootstrap percolationconcentration of measurepercolation time

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph theory (05C99)

Abstract: We study the percolation time of the $r$-neighbour bootstrap percolation model on the discrete torus $$. For $t$ at most a polylog function of $n$ and initial infection probabilities within certain ranges depending on $t$, we prove that the percolation time of a random subset of the torus is exactly equal to $t$ with high probability as $n$ tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understanding of the geometric behaviour of the $r$-neighbour bootstrap process in the dense setting. The special case $d-r=0$ of our result was proved recently by Bollob'as, Holmgren, Smith and Uzzell.

Recommendations

• The time of bootstrap percolation with dense initial sets
• The sharp threshold for bootstrap percolation in all dimensions
• The time of bootstrap percolation in two dimensions
• Threshold behavior of bootstrap percolation
• Sharp thresholds in bootstrap percolation
• The time of graph bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions
• A sharp threshold for bootstrap percolation in a random hypergraph
• An improved upper bound for bootstrap percolation in all dimensions

Cites work

• A simple model of global cascades on random networks
• Bootstrap percolation in high dimensions
• Bootstrap percolation in living neural networks
• Bootstrap percolation in three dimensions
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Dynamic monopolies in tori.
• Exact solution of a jamming transition: Closed equations for a bootstrap percolation problem
• Finite size scaling in three-dimensional bootstrap percolation
• Growth rates and explosions in sandpiles
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Metastability effects in bootstrap percolation
• Minimal percolating sets in bootstrap percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• Poisson approximation for dependent trials
• Poisson approximation for some statistics based on exchangeable trials
• Remarks on bootstrap percolation in metric networks
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• The threshold regime of finite volume bootstrap percolation.
• The time of bootstrap percolation with dense initial sets for all thresholds
• Threshold models of diffusion and collective behavior
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)

Cited in

(8)

• The time of bootstrap percolation with dense initial sets for all thresholds
• Slow graph bootstrap percolation. II: Accelerating properties
• The time of bootstrap percolation in two dimensions
• The time of bootstrap percolation with dense initial sets
• Polluted bootstrap percolation with threshold two in all dimensions
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• New ordering methods to construct contagious sets and induced degenerate subgraphs

This page was built for publication: The time of bootstrap percolation with dense initial sets for all thresholds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192370)