2017/09/12 by Nemanja Škorić, Angelika Steger, Škorić, Nemanja +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1709.03901
openalex publication_date 2017/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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/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 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 ≥ 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.