Connectivity Threshold for random subgraphs of the Hamming graph

Abstract

We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d,n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $np-\log n\to -\infty$ the probability that the graph is connected goes to $0$, while when $np-\log n\to +\infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $np-\log n\to t\in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Within the critical window, the connectivity probability does depend on d. We determine how.

10 pages, no figures

References in corpus (2)

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random Subgraphs in Sparse Graphs