Hypercube percolation

Remco van der Hofstad; Asaf Nachmias

doi:10.4171/jems/679

JournalsjemsVol. 19, No. 3pp. 725–814

Hypercube percolation

Remco van der Hofstad
TU Eindhoven, The Netherlands
Asaf Nachmias
University of British Columbia, Vancouver, Canada

Download PDF

Abstract

We study bond percolation on the Hamming hypercube {0,1} $^{m}$ around the critical probability $p_{c}$ . It is known that if $p = p_{c} (1 + O (2^{- m /3}))$ , then with high probability the largest connected component $C_{1}$ is of size $Θ (2^{2 m /3})$ . Here we show that for any sequence $ϵ (m)$ such that $ϵ (m) = o (1)$ but $ϵ (m) ≫ 2^{- m /3}$ percolation on the hypercube at $p_{c} (1 + ϵ (m))$ has

∣ C_{1} ∣ = (2 + o (1)) ϵ (m) 2^{m} and ∣ C_{2} ∣ = o (ϵ (m) 2^{m}),

with high probability, where $C_{2}$ is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [18].

Cite this article

Remco van der Hofstad, Asaf Nachmias, Hypercube percolation. J. Eur. Math. Soc. 19 (2017), no. 3, pp. 725–814

DOI 10.4171/JEMS/679