Local resilience of an almost spanning <i>k</i>‐cycle in random graphs

Abstract

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 &gt; 0 such that if 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 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.