Dirac's theorem for random graphs

A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\left\lceil n/2 \right\rceil\end{align*} \end{document} is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if p ≫ log n / n , then a.a.s. every subgraph of G ( n , p ) with minimum degree at least (1/2 + o (1)) n p is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability p and the value of the constant 1/2 are asymptotically best possible. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012