On the maximum running time in graph bootstrap percolation

zbMath1361.05135arXiv1510.07096MaRDI QIDQ528995

Julian Sahasrabudhe, Béla Bollobás, Oliver Riordan, Michał Przykucki

Publication date: 18 May 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

cellular automataextremal combinatoricsweak saturationbootstrap percolationmonotone cellular automata

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Extremal combinatorics (05D99)

Related Items (6)

Long running times for hypergraph bootstrap percolation ⋮ Transitive closure in a polluted environment ⋮ On the running time of hypergraph bootstrap percolation ⋮ Line Percolation in Finite Projective Planes ⋮ On \(K_{2, t}\)-bootstrap percolation ⋮ Maximal Spanning Time for Neighborhood Growth on the Hamming Plane

Cites Work

• Unnamed Item
• Unnamed Item
• On slowly percolating sets of minimal size in bootstrap percolation
• Linear algebra and bootstrap percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Minimal percolating sets in bootstrap percolation
• An extremal problem for sets with applications to graph theory
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• An extremal problem for two families of sets
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Proof of Straley's argument for bootstrap percolation.
• Bootstrap percolation on Galton-Watson trees
• Graph bootstrap percolation
• Bootstrap percolation on the random regular graph
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Random disease on the square grid
• The time of graph bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• Extremal bounds for bootstrap percolation in the hypercube

This page was built for publication: On the maximum running time in graph bootstrap percolation