Hamiltonicity of random subgraphs of the hypercube

Abstract

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)\ge \alpha n$ with $\alpha >0$ fixed and we consider a random binomial subgraph ${\mathcal{Q}}_p^n$ of ${\mathcal{Q}}^n$ with $p\in (0,1]$ fixed, then with high probability $H\cup {\mathcal{Q}}_p^n$ 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á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\in (0,1]$ the graph ${\mathcal{Q}}_p^n$ contains an almost spanning cycle. Our methods involve branching processes, the Rödl nibble, and absorption.

Final version, to appear in Memoirs of the AMS