Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box

MaRDI QIDQ1658747zbMATH OpenFDO

Authors Ivailo Hartarsky

Publication date 15 August 2018

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

Full work available at URL https://arxiv.org/abs/1707.09214, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p10

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

bootstrap percolationhypercubesnake-in-the-box

Mathematics Subject Classification ID

Extremal combinatorics (05D99) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: In $r$-neighbour bootstrap percolation, vertices (sites) of a graph $G$ are infected, round-by-round, if they have $r$ neighbours already infected. Once infected, they remain infected. An initial set of infected sites is said to percolate if every site is eventually infected. We determine the maximal percolation time for $r$-neighbour bootstrap percolation on the hypercube for all $rgeq3$ as the dimension $d$ goes to infinity up to a logarithmic factor. Surprisingly, it turns out to be $frac{2}^{d}d$, which is in great contrast with the value for $r=2$, which is quadratic in $d$, as established by Przykucki. Furthermore, we discover a link between this problem and a generalisation of the well-known Snake-in-the-Box problem.

Review text

Summary: In \(r\)-neighbour bootstrap percolation, vertices (sites) of a graph \(G\) become ``infected in each round of the process if they have \(r\) neighbours already infected. Once infected, they remain such. An initial set of infected sites is said to percolate if every site is eventually infected. We determine the maximal percolation time for \(r\)-neighbour bootstrap percolation on the hypercube for all \(r \geq 3\) as the dimension \(d\) goes to infinity up to a logarithmic factor. Surprisingly, it turns out to be \(\frac{2^{d}}{d}\), which is in great contrast with the value for \(r=2\), which is quadratic in \(d\), as established by \textit{M. Przykucki} [Electron. J. Comb. 19, No. 2, Research Paper P41, 13 p. (2012; Zbl 1254.82017)]. Furthermore, we discover a link between this problem and a generalisation of the well-known Snake-in-the-Box problem.

Recommendations

• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Maximal induced paths and minimal percolating sets in hypercubes
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation

Cites work

• Bootstrap percolation in high dimensions
• Bootstrap percolation on the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Finite size scaling in three-dimensional bootstrap percolation
• scientific article; zbMATH DE number 3368649 (Why is no real title available?)
• scientific article; zbMATH DE number 3394025 (Why is no real title available?)
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Maximal induced paths and minimal percolating sets in hypercubes
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• Metastability effects in bootstrap percolation
• Minimal percolating sets in bootstrap percolation
• Monotone cellular automata in a random environment
• On slowly percolating sets of minimal size in bootstrap percolation
• Saturation in the hypercube and bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Slow convergence in bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• The threshold regime of finite volume bootstrap percolation.

Cited in

(9)

• Kinetically constrained models with random constraints
• Universality for critical KCM: infinite number of stable directions
• Anisotropic bootstrap percolation in three dimensions
• Maximal induced paths and minimal percolating sets in hypercubes
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Maximal spanning time for neighborhood growth on the Hamming plane
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• On the running time of hypergraph bootstrap percolation
• The maximal running time of hypergraph bootstrap percolation

This page was built for publication: Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box

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