Premium
Slightly subcritical hypercube percolation
Author(s) -
Hulshof Tim,
Nachmias Asaf
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20853
Subject(s) - hypercube , combinatorics , percolation (cognitive psychology) , mathematics , cardinality (data modeling) , mixing (physics) , component (thermodynamics) , discrete mathematics , physics , computer science , thermodynamics , quantum mechanics , neuroscience , biology , data mining
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 32 m ) , that the maximal diameter of all clusters is ( 1 + o ( 1 ) ) ε m − 1 log ( ε m 32 m ) , and that the maximal mixing time of all clusters is Θε m − 3log 2 ( ε m 32 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.