Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus

Details Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus

2010-01-06

arxiv.org/abs/1001.1007v2

Mathematics

Probability

37 pages, 1 figure

Scientific paper

The d-dimensional Hamming torus is the graph whose vertices are all of the integer points inside an a_1 n X a_2 n X ... X a_d n box in R^d (for constants a_1, ..., a_d > 0), and whose edges connect all vertices within Hamming distance one. We study the size of the largest connected component of the subgraph generated by independently removing each vertex of the Hamming torus with probability 1-p. We show that if p=\lambda / n, then there exists \lambda_c > 0, which is the positive root of a degree d polynomial whose coefficients depend on a_1, ..., a_d, such that for \lambda < \lambda_c the largest component has O(log n) vertices (a.a.s. as n \to \infty), and for \lambda > \lambda_c the largest component has (1-q) \lambda (\prod_i a_i) n^{d-1} + o(n^{d-1}) vertices and the second largest component has O(log n) vertices (a.a.s.). An implicit formula for q < 1 is also given. Surprisingly, the value of \lambda_c that we find is distinct from the critical value for the emergence of a giant component in the random edge subgraph of the Hamming torus. Additionally, we show that if p = c log n / n, then when c < (d-1) / (\sum a_i) the site subgraph of the Hamming torus is not connected, and when c > (d-1) / (\sum a_i) the subgraph is connected (a.a.s.). We also show that the subgraph is connected precisely when it contains no isolated vertices.

Affiliated with

Also associated with

No associations

Rating

Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-373062