Random subgraphs of the 2D Hamming graph: the supercritical phase

Research paper by Remco van der Hofstad, Malwina J. Luczak

Indexed on: 27 Jan '09Published on: 27 Jan '09Published in: Probability Theory and Related Fields

Abstract

We study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on n vertices. Let p be the edge probability, and write $${p={(1+\varepsilon)}/{(2(n-1))}}$$ for some $${\varepsilon \in \mathbb{R}}$$ . In Borgs et al. (Random Struct Alg 27:137–184, 2005; Ann Probab 33:1886–1944, 2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for $${\varepsilon \leq \Lambda V^{-1/3}}$$ , where Λ >  0 is a constant and V = n2 denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained. In this paper we prove that, when $${\varepsilon \gg (\log{V})^{1/3} V^{-1/3}}$$ , then the largest connected component has size close to $${2 \varepsilon V}$$ with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of p are supercritical. Barring the factor $${(\log{V})^{1/3}}$$, this identifies the size of the largest connected component all the way down to the critical p window.