Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.13341 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 \rightarrow \infty$), for arbitrary $k \in \mathbb N$ satisfying $2 \leq k\leq 2^{\sqrt{n}}$.