Local resilience of an almost spanning $k$-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\ge 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\ge 2$ there exists $C>0$ such that if $p\ge C(\log n/n{)}^{1/k}$ then w.h.p. every subgraph of a random graph $G_{n,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 et al. for $k\ge 3$. Our result is almost best possible in three ways: for $p\ll n^{-1/k}$ the random graph $G_{n,p}$ w.h.p. does not contain the $k$-th power of any long cycle; there exist subgraphs of $G_{n,p}$ with minimum degree $(k/(k+1)+o(1))np$ and $\Omega (p^{-2})$ vertices not belonging to triangles; there exist subgraphs of $G_{n,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.

24 pages; small updates to the paper after anonymous reviewers' reports

References in corpus (1)

• Upper Tails for Cliques