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

Research paper by **David Sivakoff**

Indexed on: **07 Apr '10**Published on: **07 Apr '10**Published in: **Mathematics - Probability**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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.