2024/06/19 by Kang, Mihyun, Missethan, Michael, Schmid, Dominik
#60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2406.13341
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∈ (0,1), and "healthy" vertices get infected in subsequent rounds if they have at least r infected neighbours. A graph G percolates if every vertex becomes eventually infected. A central problem in this process is to determine the critical probability pc(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 \squarei=1n Kk, which is the graph obtained by taking the Cartesian product of n copies of the complete graph Kk 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 pc(Qn,2) for random 2-neighbour bootstrap percolation on the n-dimensional hypercube Qn=\squarei=1n K2 to the n-dimensional Hamming graph \squarei=1n Kk, determining the asymptotic value of pc(\squarei=1n Kk,2), up to multiplicative constants (when n → ∞), for arbitrary k ∈ \mathbb N satisfying 2 ≤ k≤ 2√(n).