# Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube

**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.