Maximal percolation time in hypercubes under 2-bootstrap percolation

MaRDI QIDQ456290zbMATH OpenFDO

Authors Michał Przykucki

Publication date 24 October 2012

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

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p41

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(n\)-dimensional hypercubepercolation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80) Percolation (82B43)

Review text

Summary: Bootstrap percolation is one of the simplest cellular automata. In \(r\)-bootstrap percolation on a graph \(G\), an infection spreads according to the following deterministic rule: infected vertices of \(G\) remain infected forever and in consecutive rounds healthy vertices with at least \(r\) already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. In this paper we prove that in the case of 2-bootstrap percolation on the \(n\)-dimensional hypercube the maximal time the process can take to eventually infect the entire vertex set is \(\lfloor \frac{n^2}{3} \rfloor\).

Recommendations

• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• Maximal induced paths and minimal percolating sets in hypercubes

Cited in

(31)

• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• A cube dismantling problem related to bootstrap percolation
• On the \(P_3\)-hull number of Kneser graphs
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Burning the plane. Densities of the infinite Cartesian grid
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Maximal induced paths and minimal percolating sets in hypercubes
• The time of bootstrap percolation with dense initial sets for all thresholds
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets
• Bootstrap Percolation on Degenerate Graphs
• 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
• On the running time of hypergraph bootstrap percolation
• Target set selection with maximum activation time
• The maximal running time of hypergraph bootstrap percolation
• Bootstrap percolation in strong products of graphs
• The maximum length of K_r-bootstrap percolation
• Bootstrap percolation on the high-dimensional Hamming graph
• 3-neighbor bootstrap percolation on grids
• Slow graph bootstrap percolation. II: Accelerating properties
• Bootstrap percolation, connectivity, and graph distance
• Slow graph bootstrap percolation. I: Cycles
• Bootstrap percolation on the hypercube
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation

This page was built for publication: Maximal percolation time in hypercubes under 2-bootstrap percolation

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