2020/07/06 by Padraig Condon, Alberto Espuny Díaz, Condon, Padraig +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · doi:10.48550/arxiv.2007.02891
openalex publication_date 2020/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study Hamiltonicity in random subgraphs of the hypercube Qn. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of Qn 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∈ℕ. Secondly, we obtain a perturbation result: if H\subseteqQn satisfies δ(H)≥αn with α>0 fixed and we consider a random binomial subgraph Qnp of Qn with p∈(0,1] fixed, then with high probability H\cupQnp contains k edge-disjoint Hamilton cycles, for any fixed k∈ℕ. 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 Qnp contains an almost spanning cycle. Our methods involve branching processes, the Rödl nibble, and absorption.