Graph theory seminar - Peter Nelson

Cyclicity of a random subgraph

Abstract:

Let $G$ be a simple graph of average degree $d$, and let $H$ be a spanning subgraph of $G$ chosen by including each edge of $G$ independently with fixed probability $p$. Alon and Bachmat showed that if $p > 1/(d-1)$ and $G$ is sufficiently large and regular, then $H$ contains a cycle with high probability. I will discuss a recent result that generalizes this to arbitrary $G$.