2010/05/31 by Choongbum Lee, Lee, Choongbum, Wojciech Samotij +1 · 2 citations
Computer Science · Mathematics · #05C35 #05C45 #05C80 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C35 #msc:05C45 #msc:05C80 #msc:05D40
paper · pdf · doi:10.48550/arxiv.1005.5716
19 pages, 4 figures
openalex publication_date 2010/05/31 · arxiv created 2011/07/07 · arxiv updated 2015/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An n-vertex graph is called pancyclic if it contains a cycle of length t for all 3 ≤ t ≤ n. In this paper, we study pancyclicity of random graphs in the context of resilience, and prove that if p ≫ n-1/2, then the random graph G(n,p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n,p) with more than (1/2 + o(1))n \choose 2p edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion 1/2 of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich, Lee, and Sudakov. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers).