Slightly subcritical hypercube percolation

2016/12/06 by Tim Hulshof, Hulshof, Tim, Asaf Nachmias +1 · 1 citation
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1612.01772

openalex publication_date 2016/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study bond percolation on the hypercube \0,1\^m in the slightly subcritical regime where p = p_c (1-ε_m) and ε_m = o(1) but ε_m ≫ 2^-m/3 and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality Θ(ε_m^-2 log(ε_m³ 2^m)), that the maximal diameter of all clusters is (1+o(1)) ε_m^-1 log(ε_m³ 2^m), and that the maximal mixing time of all clusters is Θ(ε_m^-3 log²(ε_m³ 2^m)). 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.

Citations

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition

Cited by

• Diameter and mixing time of the giant component in the percolated hypercube

Related

• Hypercube percolation
• Diameter and mixing time of the giant component in the percolated hypercube
• Maximum Cluster Diameter in Non-Critical Bond Percolation
• Supercritical Site Percolation on the Hypercube: Small Components are Small
• Subcritical Connectivity and Some Exact Tail Exponents in High Dimensional Percolation