Maximum Induced Trees in Sparse Random Graphs
Juan Carlos Buitrago Oropeza · Doklady Mathematics · 2024
We prove that for any $$\varepsilon > 0$$ and $${{n}^{{ - \frac{{e - 2}}{{3e - 2}} + \varepsilon }}} \leqslant p = o(1)$$ the maximum size of an induced subtree of the binomial random graph $$G(n,p)$$ is concentrated asymptotically almost surely at two consecutive points.