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

bootstrappercolationbootstrap percolation

Mathematics Subject Classification ID

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

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

(35)

• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Kinetically constrained models out of equilibrium
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• Maximal edge-traversal time in first-passage percolation
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Inapproximability results related to monophonic convexity
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• Nucleation and growth in two dimensions
• Long running times for hypergraph bootstrap percolation
• On the running time of hypergraph bootstrap percolation
• Computational Complexity of Biased Diffusion-Limited Aggregation
• Complexity of determining the maximum infection time in the geodetic convexity
• The time of bootstrap percolation in two dimensions
• scientific article; zbMATH DE number 6302977 (Why is no real title available?)
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• The maximum infection time in the geodesic and monophonic convexities
• Neighborhood growth dynamics on the Hamming plane
• Maximal spanning time for neighborhood growth on the Hamming plane
• Burning the plane. Densities of the infinite Cartesian grid
• Bootstrap Percolation on Degenerate Graphs
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• On the parameterized complexity of the geodesic hull number
• Smallest percolating sets in bootstrap percolation on grids
• Minimal contagious sets in random regular graphs
• Target set selection with maximum activation time
• The P3 infection time is W[1]-hard parameterized by the treewidth
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The maximal running time of hypergraph bootstrap percolation
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• Line Percolation in Finite Projective Planes
• On the maximum running time in graph bootstrap percolation

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)