Connectivity threshold for random subgraphs of the Hamming graph

Research output: Book/ReportReportAcademic

172 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 \to - \infty$ the probability that the graph is connected goes 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 the Hamming graph (see [Bor et al, 2005]). Keywords: connectivity threshold, percolation, random graph, critical window
Original languageEnglish
Publishers.n.
Number of pages9
Publication statusPublished - 2015

Publication series

NamearXiv
Volume1504.05350 [math.PR]

Fingerprint

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

Cite this