Expansion in supercritical random subgraphs of the hypercube and its consequences

Joshua Erde, Mihyun Kang, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review


It is well known that the behaviour of a random subgraph of a ddimensional hypercube, where we include each edge independently with probability p, undergoes a phase transition when p is around 1 d. More precisely, standard arguments show that just below this value of p all components of this graph have order O(d) with probability tending to one as d→∞ (whp for short), whereas Ajtai, Komlós and Szemerédi (Combinatorica 2 (1982) 1–7) showed that just above this value, in the supercritical regime, whp there is a unique “giant” component of order (Formula Presented). We show that whp the vertex expansion of the giant component is inverse polynomial in d. As a consequence, we obtain polynomial in d bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component, answering questions of Bollobás, Kohayakawa and Łuczak (Random Structures and Algorithms 5 (1994) 627–648) and of Pete (Electron. Commun. Probab. 13 (2008) 377–392). Furthermore, our results imply lower bounds on the circumference and Hadwiger number of a random subgraph of the hypercube in this regime of p, which are tight up to polynomial factors in d.

Original languageEnglish
Pages (from-to)127-156
Number of pages30
JournalThe Annals of Probability
Issue number1
Publication statusPublished - 2023


  • math.CO
  • math.PR
  • Hypercube percolation
  • Graph expansion

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Expansion in supercritical random subgraphs of the hypercube and its consequences'. Together they form a unique fingerprint.

Cite this