Maximum induced forests in random graphs (Q2235276)

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)\).