Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs (Q405113)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
scientific article

    Statements

    Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs (English)
    0 references
    0 references
    0 references
    4 September 2014
    0 references
    Summary: 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 \textit{M. Ajtai} et al. [Combinatorica 1, 1--12 (1981; Zbl 0489.05052)], we prove that for every positive \(\epsilon\), there exists a positive \(\delta\) (depending only on \(\epsilon\)) such that the following holds: If \(p \geq \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\).
    0 references
    random graphs
    0 references
    forbidden subgraphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references