## 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 → ˗∞ 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 [1]). Within the critical window, the connectivity probability does depend on d. We determine how.

Original language | English |
---|---|

Article number | 27 |

Pages (from-to) | 1-8 |

Number of pages | 8 |

Journal | Electronic Communications in Probability |

Volume | 21 |

DOIs | |

Publication status | Published - 2016 |

## Keywords

- Connectivity threshold
- Critical window
- Percolation
- Random graph