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

DOI10.1007/S00440-009-0200-3MaRDI QIDQ2380761zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Malwina Luczak

Publication date 12 April 2010

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

random graphpercolationHamming graphgiant componentsupercritical

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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=frac1+vep2(n-1)$ for some $vepinR$. 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 $vepleqLambda{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 $vepgg(logV{)}^{1/3}{V}^{-1/3}$, then the largest connected component has size close to $2vepV$ 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 $(logchsV{)}^{1/3}$, this identifies the size of the largest connected component all the way down to the critical $p$ window.

Recommendations

• The second largest component in the supercritical 2D Hamming graph
• Connectivity threshold for random subgraphs of the Hamming graph
• scientific article; zbMATH DE number 6327467
• Random subgraphs of finite graphs. III: The phase transition for the n-cube
• scientific article; zbMATH DE number 3874387

Cites work

• scientific article; zbMATH DE number 1246231 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1787234 (Why is no real title available?)
• scientific article; zbMATH DE number 1369842 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• A spectral lower bound for the treewidth of a graph and its consequences
• Asymptotic expansions inn−1 for percolation critical values on then-Cube and ℤn
• Expansion in ${\boldsymbol{n^{-1}}}$ for Percolation Critical Values on the $n$-cube and ${\boldsymbol{{\mathbb Z}^n}}$: the First Three Terms
• Mean-field conditions for percolation on finite graphs
• Moment of degeneration of a branching process and height of a random tree
• On-line routing of random calls in networks
• Random graph asymptotics on high-dimensional tori
• 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
• The Multiplicative Process
• The birth of the infinite cluster: Finite-size scaling in percolation
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The total progeny in a branching process and a related random walk

Cited in

(12)

• Hypercube percolation
• Critical random graphs: Diameter and mixing time
• Connectivity threshold for random subgraphs of the Hamming graph
• On the critical probability in percolation
• The phase transition in multitype binomial random graphs
• The second largest component in the supercritical 2D Hamming graph
• Phase transition for the interchange and quantum Heisenberg models on the Hamming graph
• Critical behavior in inhomogeneous random graphs
• Bootstrap percolation on the Hamming torus
• Expansion of Percolation Critical Points for Hamming Graphs
• Mean-field conditions for percolation on finite graphs
• A new approach to the giant component problem

This page was built for publication: Random subgraphs of the 2D Hamming graph: The supercritical phase

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380761)