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 k th 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 ( log n / n ) 1 / kthen w.h.p. every subgraph of a random graph Gn , p with minimum degree at least ( k /( k  + 1) +  o (1)) np , contains the k th 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 k th 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 k th power of a cycle on (1 −  o (1)) n vertices.