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.
Original language | English |
---|---|
Pages (from-to) | 557-593 |
Number of pages | 37 |
Journal | Random Structures and Algorithms |
Volume | 56 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Mar 2020 |
Keywords
- diameter
- hypercube
- mixing time
- percolation
- subcriticality