The second largest component in the supercritical 2D Hamming graph

DOI10.1002/RSA.20288zbMATH Open1208.05139arXiv0801.1608OpenAlexW2951948287MaRDI QIDQ3055879FDOQ3055879

Authors: Remco van der Hofstad, Malwina Luczak, Joel Spencer 

Publication date: 10 November 2010

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Hypercube percolation
• Title not available (Why is that?)
• 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)