Hamiltonicity of Random Subgraphs of the Hypercube

We study Hamiltonicity in random subgraphs of the hypercube Q n Q^n . Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of Q n 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 2 k 2k , it contains k k edge-disjoint Hamilton cycles, for any fixed k ∈ N k∈ N . Secondly, we obtain a perturbation result: if H ⊆ Q n H⊆ Q^n satisfies δ ( H ) ≥ α n δ (H)≥ α n with α > 0 α >0 fixed and we consider a random binomial subgraph Q p n Q^n_p of Q n Q^n with p ∈ ( 0 , 1 ] p∈ (0,1] fixed, then with high probability H ∪ Q p n H∪ Q^n_p contains k k edge-disjoint Hamilton cycles, for any fixed k ∈ N 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 1/2 . Our techniques also show that, with high probability, for all fixed p ∈ ( 0 , 1 ] p∈ (0,1] the graph Q p n Q^n_p contains an almost spanning cycle. Our methods involve branching processes, the Rödl nibble, and absorption.