math.CO
Hamiltonicity of random subgraphs of the hypercube. We study Hamiltonicity in random subgraphs of the hypercube mathcal Q n . Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of mathcal 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 in mathbb N . Secondly, we obtain a perturbation result if H subseteq mathcal Q n satisfies delta(H) geq alpha n with alpha 0 fixed and we consider a random binomial subgraph mathcal Q n p of mathcal Q n with p in(0,1 fixed, then with high probability H cup mathcal Q n p contains k edge disjoint Hamilton cycles, for any fixed k in mathbb N . In particular, both results resolve a long standing conjecture, posed e.g. by Bollob 'as, 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 in(0,1 the graph mathcal Q n p contains an almost spanning cycle. Our methods involve branching processes, the R "odl nibble, and absorption.