Seminars in July 2009

  • 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:

Monthly Archives