# Long paths and cycles in random subgraphs of H-free graphs

Research paper by **Michael Krivelevich, Wojciech Samotij**

Indexed on: **16 Jan '14**Published on: **16 Jan '14**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $\mathcal{H}$ be a given finite (possibly empty) family of connected
graphs, each containing a cycle, and let $G$ be an arbitrary finite
$\mathcal{H}$-free graph with minimum degree at least $k$. For $p \in [0,1]$,
we form a $p$-random subgraph $G_p$ of $G$ by independently keeping each edge
of $G$ with probability $p$. Extending a classical result of Ajtai, Koml\'os,
and Szemer\'edi, we prove that for every positive $\varepsilon$, there exists a
positive $\delta$ (depending only on $\varepsilon$) such that the following
holds: If $p \ge \frac{1+\varepsilon}{k}$, then with probability tending to $1$
as $k \to \infty$, the random graph $G_p$ contains a cycle of length at least
$n_{\mathcal{H}}(\delta k)$, where $n_{\mathcal{H}}(k)>k$ is the minimum number
of vertices in an $\mathcal{H}$-free graph of average degree at least $k$. Thus
in particular $G_p$ as above typically contains a cycle of length at least
linear in $k$.