Paperlane

no. 9 · Thursday 5 November 2026

Linear-length cycles in the supercritical percolated hypercube

Michael Anastos

math.CO

Abstract

Let $Q_p^d$ be the random subgraph of the $d$-dimensional binary hypercube obtained by retaining each edge independently with probability $p$. A long-standing folklore conjecture states that the emergence of the giant component in $Q_p^d$, at $p\approx 1/d$, is accompanied by the emergence of cycles of linear length. We confirm this conjecture and determine the order of the longest cycle near the phase transition. Specifically, for every sufficiently small constant $\varepsilon>0$, we show that if $p=(1+\varepsilon)/d$, then with high probability the longest cycle of $Q_p^d$ has length $Θ(\varepsilon^2 2^d)$. The dependence on $\varepsilon$ is optimal up to constant factors.

fields
Combinatorics, Probability
pdf ↗ page arXiv:2611.05634 ↗