Site Percolation on the<i>d</i>-Dimensional Hamming Torus

Abstract

The d -dimensional Hamming torus is the graph whose vertices are all of the integer points inside an a 1 n × a 2 n × ⋅⋅⋅ × a d n box in $\mathbb{R}^d$ (for constants a 1 , . . ., a d &gt; 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 = λ/ n , then there exists λ c &gt; 0, which is the positive root of a degree d polynomial whose coefficients depend on a 1 , . . ., a d , such that for λ &lt; λ c the largest component has O (log n ) vertices (w.h.p. as n → ∞), and for λ &gt; λ c the largest component has $(1-q) \lambda \bigl(\prod_i a_i \bigr) n^{d-1} + o (n^{d-1})$ vertices and the second largest component has O (log n ) vertices w.h.p. An implicit formula for q &lt; 1 is also given. The value of λ c that we find is distinct from the critical value for the emergence of a giant component in bond percolation on the Hamming torus.