Connectivity Threshold for random subgraphs of the Hamming graph

2015/04/21 by Federico, Lorenzo, van der Hofstad, Remco, Hulshof, Tim
#05C40 #60K35 #82B43 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1504.05350

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 goes 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 the Hamming graph (see [Bor et al, 2005]). Within the critical window, the connectivity probability does depend on d. We determine how.

Related

• Random subgraphs of the 2D Hamming graph: the supercritical phase
• The connectivity and phase transition in inhomogeneous random graphs of finite types
• k-connectivity threshold for superpositions of Bernoulli random graphs
• Exploring connectivity of random subgraphs of a graph
• The second largest component in the supercritical 2D Hamming graph