Critical probability conjecture for bootstrap percolation on Hamming graphs

Let i=1nKk\square_{i=1}^n K_k be the Cartesian product of nn copies of the complete graph KkK_k, and let pc(G,r)p_c(G,r) denote the critical probability for rr-neighbor bootstrap percolation on a graph GG. For arbitrary r3r\geq 3 and k2k\geq 2, the critical probability conjecture asserts that

logkpc(i=1nKk,r)=Θ(n1/2r1).-\log_k p_c\left(\square_{i=1}^n K_k,r\right)=\Theta\left(n^{1/2^{r-1}}\right).

This generalizes the conjecture of Balogh, Bollobás and Morris for the hypercube, corresponding to k=2k=2. The statement remains open, including the previously open hypercube case for arbitrary r3r\geq 3.

Sources & referencesView supporting material

Primary source

Mihyun Kang, Michael Missethan and Dominik Schmid, “Bootstrap percolation on the high-dimensional Hamming graph”, arXiv:2406.13341 (2024).

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.