Maximum induced forests in random graphs (Q2235276)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Maximum induced forests in random graphs
scientific article

    Statements

    Maximum induced forests in random graphs (English)
    0 references
    0 references
    21 October 2021
    0 references
    The authors prove that the maximum size of an induced forest (i.e.\ a subgraph that is a forest) in an Erdős-Rényi graph \(G(n,p)\) is of size either \(\lfloor2\log_{1/(1-p)}(enp)+2+\varepsilon \rfloor\) or \(\lfloor2\log_{1/(1-p)}(enp)+3+\varepsilon \rfloor\) with high probability as \(n\to\infty\), when \(p\) is fixed, for some constant \(\varepsilon > 0\). The argument is a first moment computation for the higher bound, the lower bound being deduced from \textit{D. Kamaldinov} et al. [Discrete Math. 344, No. 2, Article ID 112205, 14 p. (2021; Zbl 1454.05111)], where the same concentration result is proven for the maximum size of an induced tree in \(G(n,p)\).
    0 references
    random graph
    0 references
    concentration
    0 references
    induced forest
    0 references
    induced tree
    0 references

    Identifiers

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