Local resilience of an almost spanning k‐cycle in random graphs. Issue 4 (29th October 2018)

• Record Type: Journal Article
• Authors: Škorić, Nemanja; Steger, Angelika; Trujić, Miloš
• Is Part Of: Random structures & algorithms. Volume 53:Issue 4(2018)
• Page Start: 728
• Page End: 751
• Publication Date: 2018-10-29
• Subjects: local resilience -- powers of cycles -- random graphs -- sparse regularity lemma; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20817
• Languages: English
• ISSNs: 1042-9832

Abstract

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 > 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, 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.