Long-cycle conjecture for the percolated hypercube above the supercritical threshold

Let $Q^d$ be the $d$-dimensional hypercube, and let $Q^d_p$ be the graph obtained by retaining each edge independently with probability $p$. Let $\text{whp}$ mean with high probability as $d\to\infty$.

Long-cycle conjecture. Let $\varepsilon>0$ be a constant, and let

$$p=p(d)=\frac{1+\varepsilon}{d}.$$

Then there is a constant $c=c(\varepsilon)>0$ such that, whp, $Q^d_p$ contains a cycle of length at least

$$c\,2^d.$$

This asks for a cycle of linear size in the supercritical regime. Before this paper, the known lower bound in this regime was only $\Omega(2^d/(d\log d))$; the paper confirms the earlier long-cycle conjecture for the sparser regime $pd\to\infty$ and leaves this fixed-supercritical case open.