On Hamilton cycles in Erdős-Rényi subgraphs of large graphs

Abstract

Given a graph $\Gamma =(V,E)$ on $n$ vertices and $m$ edges, we define the Erdős-Rényi graph process with host $\Gamma$ as follows. A permutation $e_1,\dots ,e_m$ of $E$ is chosen uniformly at random, and for $t\le m$ we let ${\Gamma }_t=(V,\{e_1,\dots ,e_t\})$. Suppose the minimum degree of $\Gamma$ is $\delta (\Gamma )\ge (1/2+\epsilon )n$ for some constant $\epsilon >0$. Then with high probability, ${\Gamma }_t$ becomes Hamiltonian at the same moment that its minimum degree becomes at least two. Given $0\le p\le 1$ we let ${\Gamma }_p$ be the Erdős-Rényi subgraph of $\Gamma$, obtained by retaining each edge independently with probability $p$. When $\delta (\Gamma )\ge (1/2+\epsilon )n$, we provide a threshold function $p_0$ for Hamiltonicity, such that if $(p-p_0)n\to -\infty$ then ${\Gamma }_p$ is not Hamiltonian whp, and if $(p-p_0)n\to \infty$ then ${\Gamma }_p$ is Hamiltonian whp.