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

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 for some . 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 , where ¿ > 0 is a constant and V = n 2 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 , then the largest connected component has size close to 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 , this identifies the size of the largest connected component all the way down to the critical p window