Slightly subcritical hypercube percolation

Abstract

We study bond percolation on the hypercube $\{0,1{\}}^m$ in the slightly subcritical regime where $p=p_c(1-{\epsilon }_m)$ and ${\epsilon }_m=o(1)$ but ${\epsilon }_m\gg 2^{-m/3}$ and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality $\Theta \left({\epsilon }_m^{-2}\log ({\epsilon }_m^3{2}^m)\right)$, that the maximal diameter of all clusters is $(1+o(1)){\epsilon }_m^{-1}\log ({\epsilon }_m^3{2}^m)$, and that the maximal mixing time of all clusters is $\Theta \left({\epsilon }_m^{-3}{\log }^2({\epsilon }_m^3{2}^m)\right)$. These results hold in different levels of generality, and in particular, some of the estimates hold for various classes of graphs such as high-dimensional tori, expanders of high degree and girth, products of complete graphs, and infinite lattices in high dimensions.

38 pages

References in corpus (2)

• Critical random graphs: Diameter and mixing time
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition

Cited by in corpus (1)

• Preferential attachment without vertex growth: emergence of the giant component