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
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
0 references