Connectivity threshold for random subgraphs of the hamming graph

Research output: Contribution to journalArticleAcademicpeer-review

72 Downloads (Pure)

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 languageEnglish
Article number27
Pages (from-to)1-8
Number of pages8
JournalElectronic Communications in Probability
Volume21
DOIs
Publication statusPublished - 2016

Keywords

  • Connectivity threshold
  • Critical window
  • Percolation
  • Random graph

Fingerprint Dive into the research topics of 'Connectivity threshold for random subgraphs of the hamming graph'. Together they form a unique fingerprint.

Cite this