On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs. Issue 1 (27th February 2020) - Johansson, Tony
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 .