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

• 成果类型: Article
• 署名作者: van der Hofstad, Remco; Luczak, Malwina J.
• 署名单位: University of London; London School Economics & Political Science; Eindhoven University of Technology
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-009-0200-3
• 发表日期: 2010
• 页码: 1-41
• 关键词: percolation critical-values; finite graphs; n-cube; expansion; n(-1)

摘要

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 + epsilon)/(2(n - 1)) for some epsilon is an element of 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 e <= Lambda V-1/3, where Lambda > 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 epsilon >> (log V)(1/3) V-1/3, then the largest connected component has size close to 2 epsilon 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.