Hamiltonicity of Random Subgraphs of the Hypercube
Padraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn, Deryk Osthus · Memoirs of the American Mathematical Society · 2024
We study Hamiltonicity in random subgraphs of the hypercube Q n \mathcal {Q}^n . Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of Q n \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 2 k 2k , it contains k k edge-disjoint Hamilton cycles, for any fixed k ∈ N k\in \mathbb {N} . Secondly, we obtain a perturbation result: if H ⊆ Q n H\subseteq \mathcal {Q}^n satisfies δ ( H ) ≥ α n \delta (H)\geq \alpha n with α > 0 \alpha >0 fixed and we consider a random binomial subgraph Q p n \mathcal {Q}^n_p of Q n \mathcal {Q}^n with p ∈ ( 0 , 1 ] p\in (0,1] fixed, then with high probability