2009/06/07 by Michael Krivelevich, Krivelevich, Michael, Choongbum Lee +3 · 1 citation
Mathematics · #05C35 #05C38 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C38 #msc:05C80
paper · pdf · doi:10.48550/arxiv.0906.1397
17 pages
arxiv created 2009/06/07 · arxiv updated 2009/12/01
A graph G on n vertices is pancyclic if it contains cycles of length t for all 3 ≤ t ≤ n. In this paper we prove that for any fixed ε>0, the random graph G(n,p) with p(n)≫ n-1/2 asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most (1/2 - ε)np then G-H is pancyclic. In fact, we prove a more general result which says that if p ≫ n-1+1/(l-1) for some integer l ≥ 3 then for any ε>0, asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than (1/2+ε)np contains cycles of length t for all l ≤ t ≤ n. These results are tight in two ways. First, the condition on p essentially cannot be relaxed. Second, it is impossible to improve the constant 1/2 in the assumption for the minimum degree. We also prove corresponding results for pseudo-random graphs.