2008/01/10 by Remco van der Hofstad, van der Hofstad, Remco, Malwina Luczak +1
Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.0801.1607
openalex publication_date 2008/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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+\vep)/(2(n-1)) for some \vep∈ \R. In Borgs et al., Random subgraphs of finite graphs: I. The scaling window under the triangle condition, Rand. Struct. Alg. (2005), and in Borgs et al., Random subgraphs of finite graphs: II. The lace expansion and the triangle condition, Ann. Probab. (2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for \vep≤ Λ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 \vep≫ (logV)1/3 V-1/3, then the largest connected component has size close to 2\vep 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\chsV)1/3, this identifies the size of the largest connected component all the way down to the critical p window.