Local resilience of an almost spanning k‐cycle in random graphs.

The famous Pósa‐Seymour conjecture, confirmed in 1998 by Komlós, Sárközy, and Szemerédi, states that for any k ≥ 2, every graph on n vertices with minimum degree kn/(k + 1) contains the kth power of a Hamilton cycle. We extend this result to a sparse random setting. We show that for every k ≥ 2 there exists C > 0 such that if p≥C(logn/n)1/k then w.h.p. every subgraph of a random graph Gn,p with minimum degree at least (k/(k + 1) + o(1))np, contains the kth power of a cycle on at least (1 − o(1))n vertices, improving upon the recent results of Noever and Steger for k = 2, as well as Allen, Böttcher, Ehrenmüller, and Taraz for k ≥ 3. Our result is almost best possible in three ways: for p ≪ n−1/k the random graph Gn,p w.h.p. does not contain the kth power of any long cycle; there exist subgraphs of Gn,p with minimum degree (k/(k + 1) + o(1))np and Ω(p−2) vertices not belonging to triangles; there exist subgraphs of Gn,p with minimum degree (k/(k + 1) − o(1))np which do not contain the kth power of a cycle on (1 − o(1))n vertices. [ABSTRACT FROM AUTHOR]