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

hypercubebootstrap percolationsnake-in-the-box

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 3368649 (Why is no real title available?)
• scientific article; zbMATH DE number 3394025 (Why is no real title available?)
• 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
• 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)

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