The second largest component in the supercritical 2D Hamming graph

2008/01/10 by Remco van der Hofstad, van der Hofstad, Remco, Malwina J. Luczak +3
Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80

paper · pdf · doi:10.48550/arxiv.0801.1608

9 pages, revised version

arxiv created 2009/01/05 · arxiv updated 2009/12/01

Abstract

The 2-dimensional Hamming graph H(2,n) consists of the n² 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, so that the average degree 2(n-1)p=1+ε. Previous work by van der Hofstad and Luczak had shown that in the barely supercritical region n^-2/3ln^1/3n≪ ε≪ 1 the largest component has size ∼ 2εn. Here we show that the second largest component has size close to ε^-2, so that the dominant component has emerged. This result also suggests that a \it discrete duality principle might hold, whereby, after removing the largest connected component in the supercritical regime, the remaining random subgraphs behave as in the subcritical regime.

Related

• Random subgraphs of the 2D Hamming graph: the supercritical phase
• Connectivity Threshold for random subgraphs of the Hamming graph
• On the largest component of subcritical random hyperbolic graphs
• Barely supercritical percolation on Poissonian scale-free networks
• Anatomy of the giant component: The strictly supercritical regime