← All problems

Balogh–Bollobás asymptotic conjecture for bootstrap percolation in the hypercube

14 years old · documented by

Let r≥3r\geq 3 be fixed, and let QdQ_d be the graph with vertex set {0,1}d\{0,1\}^d in which two vertices are adjacent when they differ in exactly one coordinate. For the rr-neighbour bootstrap process on QdQ_d, let m(Qd,r)m(Q_d,r) denote the minimum cardinality of an initial set that percolates. Balogh–Bollobás conjecture. As d→∞d\to\infty,

m(Qd,r)=1+o(1)r(dr−1).m(Q_d,r)=\frac{1+o(1)}{r}\binom{d}{r-1}.

The conjecture gives the asymptotic minimum size of a percolating set in the high-dimensional hypercube. The source paper states that it proves this conjecture, so its status is solved.

References

2 papers in this index state this conjecture (2011–2015). The statement above is taken from the most recent of them; the others are arXiv:1107.1410.

Status

  • Solved: Natasha Morrison and Jonathan A. Noel. Extremal Bounds for Bootstrap Percolation in the Hypercube (Journal of Combinatorial Theory, Series A, 2018) https://arxiv.org/html/1506.04686v2

Source: Natasha Morrison and Jonathan A. Noel, “Extremal Bounds for Bootstrap Percolation in the Hypercube”, arXiv:1506.04686 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.