Maximum Percolation Time in Two-Dimensional Bootstrap Percolation

DOI10.1137/130941584MaRDI QIDQ3453576zbMATH OpenOpenAlexFDO

Authors Michał Przykucki, F. S. Benevides

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bootstrapbootstrap percolationpercolation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We consider a classic model known as bootstrap percolation on the $nimesn$ square grid. To each vertex of the grid we assign an initial state, infected or healthy, and then in consecutive rounds we infect every healthy vertex that has at least $2$ already infected neighbours. We say that percolation occurs if the whole grid is eventually infected. In this paper, contributing to a recent series of extremal results in this field, we prove that the maximum time a bootstrap percolation process can take to eventually infect the entire vertex set of the grid is $13n^2/18+O(n)$.

Recommendations

• The time of bootstrap percolation in two dimensions
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• scientific article; zbMATH DE number 6302977
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• The time of bootstrap percolation with dense initial sets
• On the maximum running time in graph bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions

Cited in

(41)

• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• Neighborhood growth dynamics on the Hamming plane
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• The P3 infection time is W[1]-hard parameterized by the treewidth
• Maximal edge-traversal time in first-passage percolation
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Smallest percolating sets in bootstrap percolation on grids
• Burning the plane. Densities of the infinite Cartesian grid
• On the parameterized complexity of the geodesic hull number
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• Minimal contagious sets in random regular graphs
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Complexity of determining the maximum infection time in the geodetic convexity
• The time of bootstrap percolation in two dimensions
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Line Percolation in Finite Projective Planes
• Bootstrap Percolation on Degenerate Graphs
• Inapproximability results related to monophonic convexity
• Computational Complexity of Biased Diffusion-Limited Aggregation
• Nucleation and growth in two dimensions
• Maximal spanning time for neighborhood growth on the Hamming plane
• 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
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
• On the running time of hypergraph bootstrap percolation
• Target set selection with maximum activation time
• The maximal running time of hypergraph bootstrap percolation
• Kinetically constrained models out of equilibrium
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• The maximum length of K_r-bootstrap percolation
• Bootstrap percolation on the high-dimensional Hamming graph
• On the size of immune sets in the k-PULL infection model
• 3-neighbor bootstrap percolation on grids
• Slow graph bootstrap percolation. II: Accelerating properties
• Bootstrap percolation, connectivity, and graph distance
• The maximum infection time in the geodesic and monophonic convexities

This page was built for publication: Maximum Percolation Time in Two-Dimensional Bootstrap Percolation

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