## Posts Tagged ‘이중범’

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

Friday, July 17th, 2009
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