Slightly subcritical hypercube percolation

Tim Hulshof (Corresponding author), Asaf Nachmias

Research output: Contribution to journalArticleAcademicpeer-review

5 Downloads (Pure)

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 2m 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 languageEnglish
Pages (from-to)557-593
Number of pages37
JournalRandom Structures and Algorithms
Volume56
Issue number2
DOIs
Publication statusPublished - 1 Mar 2020

    Fingerprint

Keywords

  • diameter
  • hypercube
  • mixing time
  • percolation
  • subcriticality

Cite this