Slightly subcritical hypercube percolation. Issue 2 (16th April 2019)

• Record Type: Journal Article
• Authors: Hulshof, Tim; Nachmias, Asaf
• Is Part Of: Random structures & algorithms. Volume 56:Issue 2(2020)
• Page Start: 557
• Page End: 593
• Publication Date: 2019-04-16
• Subjects: diameter -- hypercube -- mixing time -- percolation -- subcriticality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20853
• Languages: English
• ISSNs: 1042-9832

Abstract

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 3 2 m ), that the maximal diameter of all clusters is ( 1 + o ( 1 ) ) ε m − 1 log ( ε m 3 2 m ), and that the maximal mixing time of all clusters is Θ ε m − 3 log 2 ( ε m 3 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.