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∈ℕ 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)+αn, for any constant α>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.