Independent sets in random subgraphs of the hypercube

Abstract

Let $Q_{d,p}$ be the random subgraph of the $d$-dimensional hypercube $\{0,1{\}}^d$, where each edge is retained independently with probability $p$. We study the asymptotic number of independent sets in $Q_{d,p}$ as $d\to \infty$ for a wide range of parameters $p$, including values of $p$ tending to zero as fast as $\frac{C\log d}{d^{1/3}}$, constant values of $p$, and values of $p$ tending to one. The results extend to the hardcore model on $Q_{d,p}$, and are obtained by studying the closely related antiferromagnetic Ising model on the hypercube, which can be viewed as a positive-temperature hardcore model on the hypercube. These results generalize previous results by Galvin, Jenssen and Perkins on the hard-core model on the hypercube, corresponding to the case $p=1$, which extended Korshunov and Sapozhenko's classical result on the asymptotic number of independent sets in the hypercube.

44 pages