Mathias Schacht, Yale University

Abstract

We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every $k$ and sufficiently large $n$ already the minimum degree $geq frac{k}{k-1}n$ for an $n$-vertex graph $G$ alone suffices to ensure the existence of a $k$-th power of a Hamiltonian cycle. We show that under essentially the same degree assumption the addition of just $O(n)$ random edges ensures the presence of the $(k+1)$-st power of a Hamiltonian cycle with probability close to one