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

zbMATH Open1409.60143arXiv1707.09214MaRDI QIDQ1658747FDOQ1658747

Authors: Ivailo Hartarsky 

Publication date: 15 August 2018

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

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.

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

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

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

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)

Cites Work

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

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
• Maximal spanning time for neighborhood growth on the Hamming plane
• Universality for critical KCM: infinite number of stable directions
• 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)