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:

Comments are closed.