Abstract:
We prove that the size of the maximum induced forest (of bounded and unbounded degree) in the binomial random graph $G(n, p)$ for $C_\varepsilon/n<p<1-\varepsilon$ with an arbitrary fixed $\varepsilon>0$ is concentrated in an interval of size $o(1/p)$. We also show 2-point concentration for the size of the maximum induced forest (and tree) of bounded degree in $G(n,p)$ for $p=\operatorname{const}$.
