The second largest component in the supercritical 2D Hamming graph

DOI10.1002/RSA.20288MaRDI QIDQ3055879zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Malwina Luczak, Joel Spencer

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.1608

zbMATH Keywords

phase transitionpercolationrandom graphsscaling window

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: The 2-dimensional Hamming graph H(2,n) consists of the $n^2$ vertices $(i,j)$, $1leqi,jleqn$, 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+epsilon$. Previous work by van der Hofstad and Luczak had shown that in the barely supercritical region $n^{-2/3}l{n}^{1/3}nllepsilonll1$ the largest component has size $sim2epsilonn$. Here we show that the second largest component has size close to $epsilo{n}^{-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.

Recommendations

• Random subgraphs of the 2D Hamming graph: The supercritical phase
• Connectivity threshold for random subgraphs of the Hamming graph
• Site Percolation on the d-Dimensional Hamming Torus
• scientific article; zbMATH DE number 3874387
• Hypercube percolation

Cites work

• Component behavior near the critical point of the random graph process
• Mean-field conditions for percolation on finite graphs
• Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
• Random subgraphs of finite graphs. III: The phase transition for the n-cube
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random subgraphs of the 2D Hamming graph: The supercritical phase

Cited in

(4)

• Hypercube percolation
• scientific article; zbMATH DE number 7731163 (Why is no real title available?)
• Random subgraphs of the 2D Hamming graph: The supercritical phase
• Expansion of Percolation Critical Points for Hamming Graphs

This page was built for publication: The second largest component in the supercritical 2D Hamming graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055879)