The second largest component in the supercritical 2D Hamming graph

Remco van der Hofstad, Malwina J. Luczak, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

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/3 n « ε » 1, the largest component satisfies a law of large numbers with mean 2εn. Here we show that the second largest component has, with high probability, size bounded by 28ε-2 log(n2ε3), 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.

Original languageEnglish (US)
Pages (from-to)80-89
Number of pages10
JournalRandom Structures and Algorithms
Volume36
Issue number1
DOIs
StatePublished - Jan 2010

Keywords

  • Percolation
  • Phase transition
  • Random graphs
  • Scaling window

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The second largest component in the supercritical 2D Hamming graph'. Together they form a unique fingerprint.

Cite this