Hamiltonicity of random subgraphs of the hypercube

We study Hamiltonicity in random subgraphs of the hypercube Q n . Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of Q n according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree 2k, it contains k edge-disjoint Hamilton cycles, for any fixed k ∈ N. Secondly, we obtain a perturbation result: if H ⊆ Q n satisfies δ(H) ≥ αn with α > 0 fixed and we consider a random binomial subgraph Q n p of Q n with p ∈ (0, 1] fixed, then with high probability H ∪Q n p contains k edge-disjoint Hamilton cycles, for any fixed k ∈ N. In particular, both results resolve a long standing conjecture, posed e.g. by Bollobás, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals 1/2. Our techniques also show that, with high probability, for all fixed p ∈ (0, 1] the graph Q n p contains an almost spanning cycle. Our methods involve branching processes, the Rödl nibble, and absorption.