Cores of random graphs are born Hamiltonian. Issue 1 (3rd March 2014)

• Record Type: Journal Article
• Authors: Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
• Is Part Of: Proceedings of the London Mathematical Society. Volume 109:Issue 1(2014:Jul.)
• Page Start: 161
• Page End: 188
• Publication Date: 2014-03-03
• Subjects: Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms/pdu003
• Languages: English
• ISSNs: 0024-6115

Abstract

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 .