On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs. Issue 1 (27th February 2020)

• Record Type: Journal Article
• Authors: Johansson, Tony
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 132
• Page End: 149
• Publication Date: 2020-02-27
• Subjects: Erdős‐Rényi graph -- Hamilton cycle -- hitting time -- minimum degree; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20916
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Given a graph Γ n =( V, E ) on n vertices and m edges, we define the Erdős‐Rényi graph process with host Γ n as follows. A permutation e 1, …, e m of E is chosen uniformly at random, and for t ≤ m we let Γ n, t =( V, { e 1, …, e t }). Suppose the minimum degree of Γ n is δ (Γ n ) ≥ (1/2+ ε ) n for some constant ε >0. Then with high probability (An event ℰ n holds with high probability (whp) if Pr ℰ n → 1 as n → ∞ .), Γ n, t becomes Hamiltonian at the same moment that its minimum degree reaches 2. Given 0 ≤ p ≤ 1 let Γ n, p be the Erdős‐Rényi subgraph of Γ n, obtained by retaining each edge independently with probability p . When δ (Γ n ) ≥ (1/2+ ε ) n, we provide a threshold for Hamiltonicity in Γ n, p .