Maximum Percolation Time in Two-Dimensional Bootstrap Percolation

DOI10.1137/130941584zbMATH Open1371.60169arXiv1310.4457OpenAlexW2007804480MaRDI QIDQ3453576FDOQ3453576

Authors: Michał Przykucki, F. S. Benevides 

Publication date: 27 November 2015

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

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)$.

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

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

zbMATH Keywords

bootstrappercolationbootstrap percolation

Mathematics Subject Classification ID

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

Cited In (35)

• Kinetically constrained models out of equilibrium
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• 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
• Long running times for hypergraph bootstrap percolation
• Nucleation and growth in two dimensions
• On the running time of hypergraph bootstrap percolation
• Computational Complexity of Biased Diffusion-Limited Aggregation
• Title not available (Why is that?)
• Complexity of determining the maximum infection time in the geodetic convexity
• The time of bootstrap percolation in two dimensions
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets
• 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 maximal running time of hypergraph bootstrap percolation
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• Line Percolation in Finite Projective Planes
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
• 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)