The time of graph bootstrap percolation

DOI10.1002/RSA.20660MaRDI QIDQ5360872zbMATH OpenOpenAlexFDO

Authors Karen Gunderson, Sebastian Koch, Michał Przykucki

Publication date 26 September 2017

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

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

zbMATH Keywords

bootstrap percolationrandom graphsweak saturation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: Graph bootstrap percolation, introduced by Bollob'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G=G_{0}subseteq{K}_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_{t}cupe$ contains a new copy of $H$. We say that $G$ percolates if for some $tgeq0$, we have $G_t=K_n$. For $H=K_r$, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollob'as and Morris considered graph bootstrap percolation for $G=G(n,p)$ and studied the critical probability $p_c(n,K_r)$, for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time $t$ for all $1leqtleqCloglogn$.

Recommendations

• Graph bootstrap percolation
• On the maximum running time in graph bootstrap percolation
• \(K_{r,s}\) graph bootstrap percolation
• On \(K_{2, t}\)-bootstrap percolation
• The time of bootstrap percolation in two dimensions

Cited in

(14)

• A sharp threshold for bootstrap percolation in a random hypergraph
• On \(K_{2, t}\)-bootstrap percolation
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Graph bootstrap percolation
• The time of bootstrap percolation with dense initial sets for all thresholds
• Line Percolation in Finite Projective Planes
• On the maximum running time in graph bootstrap percolation
• scientific article; zbMATH DE number 6302977 (Why is no real title available?)
• Long running times for hypergraph bootstrap percolation
• Transitive closure in a polluted environment
• On the running time of hypergraph bootstrap percolation
• \(H\)-percolation with a random \(H\)
• The maximum length of K_r-bootstrap percolation
• Slow graph bootstrap percolation. II: Accelerating properties

This page was built for publication: The time of graph bootstrap percolation

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