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 → ˗∞ the probability that the graph is connected tends to 0, while when np ˗ log n → +∞ it converges to 1. We also investigate the connectivity probability inside the critical window, namely when np ˗ log n → t ϵ ℞. We find that the threshold does not depend on d, unlike the phase transition of the giant connected component of the Hamming graph (see ). Within the critical window, the connectivity probability does depend on d. We determine how.
|Number of pages||8|
|Journal||Electronic Communications in Probability|
|Publication status||Published - 2016|
- Connectivity threshold
- Critical window
- Random graph