Connectivity threshold for random subgraphs of the Hamming graph

被引:3
作者
Federico, Lorenzo [1 ]
van der Hofstad, Remco [1 ]
Hulshof, Tim [1 ]
机构
[1] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands
关键词
connectivity threshold; percolation; random graph; critical window;
D O I
10.1214/16-ECP4479
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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 -> -infinity the probability that the graph is connected tends to 0, while when np - log n -> +infinity it converges to 1. We also investigate the connectivity probability inside the critical window, namely when np - log n -> t is an element of 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 [1]). Within the critical window, the connectivity probability does depend on d. We determine how.
引用
收藏
页数:8
相关论文
共 12 条
  • [1] [Anonymous], 2000, WIL INT S D, DOI 10.1002/9781118032718
  • [2] Random subgraphs of finite graphs: I. The scaling window under the triangle condition
    Borgs, C
    Chayes, JT
    van der Hofstad, R
    Slade, G
    Spencer, J
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2005, 27 (02) : 137 - 184
  • [3] CLARK L., 2002, INT J MATH MATH SCI, V32, P285
  • [4] Erdos P., 1979, Computers & Mathematics with Applications, V5, P33, DOI 10.1016/0898-1221(81)90137-1
  • [5] Erds P., 1959, Publ. math. debrecen, V6, P290, DOI 10.5486/PMD.1959.6.3-4.12
  • [6] Hofstad R. v. d., RANDOM GRAPHS UNPUB, VI
  • [7] Hofstad R. v. d., 2012, ARXIV12013953
  • [8] Joos F, 2012, ELECTRON J COMB, V19
  • [9] Sivakoff D. J., 2010, THESIS
  • [10] Site Percolation on the d-Dimensional Hamming Torus
    Sivakoff, David
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2014, 23 (02) : 290 - 315