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

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ós, and Szemerédi, we prove that for every positive $\epsilon$, there exists a positive $\delta$ (depending only on $\epsilon$) such that the following holds: If $p\ge \frac{1+\epsilon }{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$.

15 pages, revised version

References in corpus (1)

• Long cycles in random subgraphs of graphs with large minimum degree

Cited by in corpus (1)

• Expansion, long cycles, and complete minors in supercritical random subgraphs of the hypercube