Local resilience of an almost spanning $k$-cycle in random graphs

Nemanja Škorić, Angelika Steger, Miloš Trujić

Published 2017-09-12Version 1

The famous P\'{o}sa-Seymour conjecture states that for any $k \geq 2$, a graph $G = (V, E)$ with minimum degree $kn/(k + 1)$ contains the $k$-th power of a Hamilton cycle. The conjecture was confirmed a couple of decades later by Koml\'{o}s, S\'{a}rk\"{o}zy, and Szemer\'{e}di. We extend this result to a sparse setting. We show that for all $k \geq 2$ and $\varepsilon, \alpha > 0$, if $p \geq C(\log{N}/N)^{1/k}$ then any subgraph of a random graph $G_{N, p}$ with minimum degree at least $(k/(k + 1) + \alpha)Np$, w.h.p.\ contains the $k$-th power of a cycle on at least $(1 - \varepsilon)N$ vertices, improving upon the recent results of Noever and Steger for $k = 2$, as well as Allen, B\"{o}ttcher, Ehrenm\"{u}ller, and Taraz for $k \geq 3$. Our result is almost best possible in three ways: $(1)$ for $p \ll N^{-1/k}$ the random graph $G_{N, p}$ almost surely does not contain the $k$-th power of any long cycle; $(2)$ there exist subgraphs of $G_{N, p}$ with minimum degree $(k/(k + 1) + \alpha)Np$ and $\Omega(p^{-2})$ vertices not belonging to any triangles; $(3)$ there exist subgraphs of $G_{N, p}$ with minimum degree $(k/(k + 1) - \alpha)Np$ which do not contain the $k$-th power of a cycle on $(1 - \varepsilon)N$ vertices.