Random subgraphs of the 2D Hamming graph: the supercritical phase

Simple item page
dc.creatorvan der Hofstad, Remco
dc.creatorLuczak, Malwina J.
dc.date2008-01-10
dc.date2008-12-15
dc.date.accessioned2026-07-07T12:12:15Z
dc.date.available2026-07-07T12:12:15Z
dc.descriptionWe study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on $n$ vertices. Let $p$ be the edge probability, and write $p=\frac{1+\vep}{2(n-1)}$ for some $\vep\in \R$. In Borgs et al., Random subgraphs of finite graphs: I. The scaling window under the triangle condition, Rand. Struct. Alg. (2005), and in Borgs et al., Random subgraphs of finite graphs: II. The lace expansion and the triangle condition, Ann. Probab. (2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for $\vep\leq ΛV^{-1/3}$, where $Λ> 0$ is a constant and $V=n^2$ denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained. In this paper we prove that, when $\vep\gg (\log{V})^{1/3} V^{-1/3}$, then the largest connected component has size close to $2\vep V$ with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of $p$ are supercritical. Barring the factor $(\log{\chs{V}})^{1/3}$, this identifies the size of the largest connected component all the way down to the critical $p$ window.
dc.description31 pages
dc.identifierhttps://arxiv.org/abs/0801.1607
dc.identifierhttp://arxiv.org/abs/0801.1607
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210483
dc.subjectProbability
dc.subjectCombinatorics
dc.subject05C80
dc.titleRandom subgraphs of the 2D Hamming graph: the supercritical phase
dc.typetext

Files

Collections

arXiv