Cores of random graphs are born Hamiltonian. Issue 1 (3rd March 2014) - Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
Abstract : Let{ G t } t ⩾ 0 be the random graph process (G 0 is edgeless andG t is obtained by adding a uniformly distributed new edge toG t − 1 ), and letτ k denote the minimum timet such that thek ‐core ofG t (its unique maximal subgraph with minimum degree at leastk ) is nonempty. For any fixedk ⩾ 3, thek ‐core is known to emerge via a discontinuous phase transition, where at timet = τ k its size jumps from 0 to linear in the number of vertices with high probability (w.h.p.). It is believed that for anyk ⩾ 3, the core is Hamiltonian upon creation w.h.p., and Bollobás, Cooper, Fenner and Frieze further conjectured that it in fact admits⌊ ( k − 1 ) / 2 ⌋ edge‐disjoint Hamilton cycles. However, even the asymptotic threshold for Hamiltonicity of thek ‐core inG ( n, p ) was unknown for anyk . We show here that for any fixedk ⩾ 15, thek ‐core ofG t is w.h.p. Hamiltonian for allt ⩾ τ k, that is, immediately as thek ‐core appears and indefinitely afterwards. Moreover, we prove that for large enough fixedk thek ‐core contains⌊ ( k − 3 ) / 2 ⌋ edge‐disjoint Hamilton cycles w.h.p. for allt ⩾ τ k .