TY - JOUR

T1 - The second largest component in the supercritical 2D Hamming graph

AU - Hofstad, van der, R.W.

AU - Luczak, M.J.

AU - Spencer, J.

PY - 2010

Y1 - 2010

N2 - The two-dimensional Hamming graph H(2,n) consists of the n2 vertices (i,j), 1 i,j n, two vertices being adjacent when they share a common coordinate. We examine random subgraphs of H(2,n) in percolation with edge probability p, in such a way that the average degree satisfies 2(n - 1)p = 1 + . Previous work [8] has shown that in the barely supercritical region n-2/3 ln1/3n 1, the largest component satisfies a law of large numbers with mean 2n. Here we show that the second largest component has, with high probability, size bounded by 28-2 log(n23), so that the dominant component has emerged. This result also suggests that a discrete duality principle holds, where, after removing the largest connected component in the supercritical regime, the remaining random subgraphs behave as in the subcritical regime.

AB - The two-dimensional Hamming graph H(2,n) consists of the n2 vertices (i,j), 1 i,j n, two vertices being adjacent when they share a common coordinate. We examine random subgraphs of H(2,n) in percolation with edge probability p, in such a way that the average degree satisfies 2(n - 1)p = 1 + . Previous work [8] has shown that in the barely supercritical region n-2/3 ln1/3n 1, the largest component satisfies a law of large numbers with mean 2n. Here we show that the second largest component has, with high probability, size bounded by 28-2 log(n23), so that the dominant component has emerged. This result also suggests that a discrete duality principle holds, where, after removing the largest connected component in the supercritical regime, the remaining random subgraphs behave as in the subcritical regime.

U2 - 10.1002/rsa.20288

DO - 10.1002/rsa.20288

M3 - Article

VL - 36

SP - 80

EP - 89

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 1

ER -