Mathematics – Probability
Scientific paper
2008-01-10
Mathematics
Probability
31 pages
Scientific paper
We 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 \Lambda V^{-1/3}$, where $\Lambda > 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.
der Hofstad Remco van
Luczak Malwina J.
No associations
LandOfFree
Random subgraphs of the 2D Hamming graph: the supercritical phase does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random subgraphs of the 2D Hamming graph: the supercritical phase, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random subgraphs of the 2D Hamming graph: the supercritical phase will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-436494