## Abstract

The two-dimensional Hamming graph H(2,n) consists of the n^{2} 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} ln^{1/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 2^{8}ε^{-2} log(n^{2}ε^{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 language | English (US) |
---|---|

Pages (from-to) | 80-89 |

Number of pages | 10 |

Journal | Random Structures and Algorithms |

Volume | 36 |

Issue number | 1 |

DOIs | |

State | Published - 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