이중범 Archives - Page 2 of 2 - KAIST Discrete Math Seminar KAIST Discrete Math Seminar

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.