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)

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