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

Resilient pancyclicity of random graphs

Choongbum Lee (이중범)
Department of Mathematics, UCLA, Los Angeles, USA

2009/7/31 Thursday 4PM-5PM

A graph G on n vertices is pancyclic if it contains cycles of length t for all $3 \leq t \leq n$ . We prove that for any fixed $\epsilon>0$ , the random graph G(n,p) with $p(n)\gg 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 - \epsilon)np$ then G-H is pancyclic. In fact, we prove a more general result which says that if $p \gg n^{-1+1/(l-1)}$ for some integer $l \geq 3$ then for any $\epsilon>0$ , asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than $(1/2+\epsilon)np$ contains cycles of length t for all $l \leq t \leq 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.

Joint work with Michael Krivelevich and Benny Sudakov

Tags: 이중범

This entry was posted on Friday, July 17th, 2009 at 6:45 pm and is filed under 2009, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.