Connectivity threshold for random subgraphs of the Hamming graph. (English) Zbl 1336.05074

Summary: 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 tends 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 of the Hamming graph (see [C. Borgs et al., Random Struct. Algorithms 27, No. 2, 137–184 (2005; Zbl 1076.05071)]). Within the critical window, the connectivity probability does depend on \(d\). We determine how.


05C40 Connectivity
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation


Zbl 1076.05071
Full Text: DOI arXiv Euclid