Sprinkling a few random edges doubles the power

Abstract

A seminal result by Komlós, Sarközy, and Szemerédi states that if a graph $G$ with $n$ vertices has minimum degree at least $kn/(k+1)$, for some $k\in \mathbb{N}$ and $n$ sufficiently large, then it contains the $k$-th power of a Hamilton cycle. This is easily seen to be the largest power of a Hamilton cycle one can guarantee, given such a minimum degree assumption. Following a recent trend of studying effects of adding random edges to a dense graph, the model known as the randomly perturbed graph, Dudek, Reiher, Ruciński, and Schacht showed that if the minimum degree is at least $kn/(k+1)+\alpha n$, for any constant $\alpha >0$, then adding $O(n)$ random edges on top almost surely results in a graph which contains the $(k+1)$-st power of a Hamilton cycle. We show that the effect of these random edges is significantly stronger, namely that one can almost surely find the $(2k+1)$-st power. This is the largest power one can guarantee in such a setting.

arXiv comment18 pages; 6 figures; published version