Nearly spanning cycle in the percolated hypercube

Abstract

Let $Q^d$ be the $d$-dimensional binary hypercube. We form a random subgraph $Q_p^d\subseteq Q^d$ by retaining each edge of $Q^d$ independently with probability $p$. We show that, for every constant $\epsilon >0$, there exists a constant $C=C(\epsilon )>0$ such that, if $p\ge C/d$, then with high probability $Q_p^d$ contains a cycle of length at least $(1-\epsilon )2^d$. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534].