2018/11/22 by Nenadov, Rajko, Trujić, Miloš · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1811.09209
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.