Bootstrap percolation on the high-dimensional Hamming graph

Abstract

In the random $r$-neighbour bootstrap percolation process on a graph $G$, a set of initially infected vertices is chosen at random by retaining each vertex of $G$ independently with probability $p\in (0,1)$, and "healthy" vertices get infected in subsequent rounds if they have at least $r$ infected neighbours. A graph $G$ \emph{percolates} if every vertex becomes eventually infected. A central problem in this process is to determine the critical probability $p_c(G,r)$, at which the probability that $G$ percolates passes through one half. In this paper, we study random $2$-neighbour bootstrap percolation on the $n$-dimensional Hamming graph ${\square }_{i=1}^n{K}_k$, which is the graph obtained by taking the Cartesian product of $n$ copies of the complete graph $K_k$ on $k$ vertices. We extend a result of Balogh and Bollobás [Bootstrap percolation on the hypercube, Probab. Theory Related Fields. 134 (2006), no. 4, 624-648. MR2214907] about the asymptotic value of the critical probability $p_c(Q^n,2)$ for random $2$-neighbour bootstrap percolation on the $n$-dimensional hypercube $Q^n={\square }_{i=1}^n{K}_2$ to the $n$-dimensional Hamming graph ${\square }_{i=1}^n{K}_k$, determining the asymptotic value of $p_c\left({\square }_{i=1}^n{K}_k,2\right)$, up to multiplicative constants (when $n\to \infty$), for arbitrary $k\in \mathbb{N}$ satisfying $2\le k\le 2^{\sqrt{n}}$.