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

Federico, Lorenzo; van der Hofstad, Remco; Hulshof, Tim

Electron. Commun. Probab. 21, Paper No. 27, 8 p. (2016).

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.

MSC:

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

Keywords:

connectivity threshold; percolation; random graph; critical window

Citations:

Zbl 1076.05071