Cores of random graphs are born Hamiltonian (Q2874667)

The fundamental problem of establishing the threshold for Hamiltonicity in the Erdős-Rényi random graph has attracted a lot of attention over the years. It is believed that in a typical random graph process \(\{G_t\}_{t\geq 0}\) on \(n\) vertices (\(G_0\) is edgeless and \(G_t\) is obtained by adding a uniformly distributed new edge to \(G_{t-1}\)), for any fixed \(k\geq 3\) the \(k\)-core of \(G_t\) (its unique maximal subgraph with minimum degree at least \(k\)) is Hamiltonian upon creation with high probability (w.h.p.) and admits \(\lfloor (k-1)/2\rfloor\) edge-disjoint Hamilton cycles (plus a perfect matching when \(k\) is even). The first appearance of a \(k\)-core involves a discontinuous first-order phase transition and its size jumps from zero to linear in the number of vertices w.h.p. However, even the asymptotic threshold for the core to contain a (single) Hamilton cycle remained open. This threshold is believed to fall roughly between \(k/n\) and \(2k^3/n\).NEWLINENEWLINENEWLINE The authors establish that for any fixed \(k\geq 15\), w.h.p. the \(k\)-core of \(G_t\) is Hamiltonian upon creation by applying a novel sprinkling recipe, hinging on conditioning on the future before creation of any \(k\)-core, and combining this method with the classical rotation-extension technique, thereby reducing Hamiltonicity to the task of verifying certain graph properties. Having settled the issue of Hamiltonicity in \(k\)-cores for \(k\geq 15\), they then turn their attention to packing Hamilton cycles and prove that for large enough fixed \(k\), w.h.p. the \(k\)-core gives rise to \(\lfloor (k-3)/2\rfloor\) edge-disjoint Hamilton cycles.