Choongbum Lee (이중범), Resilient pancyclicity of random graphs

A graph G on n vertices is pancyclic if it contains cycles of length t for all . We prove that for any fixed , the random graph G(n,p) with asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most then G-H is pancyclic. In fact, we prove a more general result which says that if for some integer then for any , asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than contains cycles of length t for all . 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.

Joint work with Michael Krivelevich and Benny Sudakov