Random Structures and Algorithms Applied Mathematics

Cycle Lengths in the Percolated Hypercube

Michael Anastos, Sahar Diskin, Joshua Erde, Mihyun Kang, Michael Krivelevich, Lyuben Lichev
Wiley · 2026-11-15 · DOI 10.1002/rsa.70108

Abstract

ABSTRACT Let be the random subgraph of the ‐dimensional binary hypercube obtained after edge‐percolation with probability . It was shown recently by the authors that, for every , there is some such that, if , then typically contains a cycle of length at least . We strengthen this result to show that, under the same assumptions, typically contains cycles of all even lengths between four and .

Read at publisher →