Importance: Medium ✭✭
 Author(s): Morrison, Natasha Noel, Jonathan A.
 Subject: Combinatorics
 Keywords: bootstrap percolation extremal combinatorics hypercube percolation
 Posted by: Jon Noel on: September 20th, 2015
Problem   Determine the smallest percolating set for the -neighbour bootstrap process in the hypercube.

The -neighbour bootstrap process starts with an initial set of "infected" vertices in a graph and, at each step, a healthy vertex becomes infected if it has at least infected neighbours. Say that the initial set of infected vertices percolates if every vertex of is eventually infected. Let denote the smallest percolating set in under the -neighbour process.

Let denote the hypercube of dimension . Balogh and Bollobás [BB] proved the following.

Theorem  (Balogh and Bollobás)   for all .

They also conjectured that for fixed and . This conjecture was proved by Morrison and Noel [MN], who also showed the following.

Theorem  (Morrison and Noel)   for all .

It seems possible that one could obtain a general formula for for all and . However, the precise formula for (in terms of ) is not known for any fixed . A solution to this problem may have applications in proving probabilistic results for bootstrap percolation in the hypercube; see [BBM].

## Bibliography

[BB] J. Balogh and B. Bollobás, Bootstrap percolation on the hypercube, Probab. Theory Related Fields 134 (2006), no. 4, 624–648.

[BBM] J. Balogh, B. Bollobás and R. Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 5-6, 643–692.

[MN] N. Morrison and J. A. Noel, Extremal Bounds for Bootstrap Percolation in the Hypercube, preprint, arXiv:1506.04686v1.

* indicates original appearance(s) of problem.