Concentration of the largest induced tree size of $G_{n,p}$ around the standard expectation threshold

Abstract

Let $T(G)$ be the size of the largest induced tree of $G$, and let $G_{n,p}$ be the binomial random graph. Kamaldinov, Skorkin, and Zhukovskii proved that $T(G_{n,p})$ equals one of two consecutive values with high probability if $p$ is constant, and more recently, Oropeza extended this result to include all vanishing $p$ such that $p>n^{-\frac{e-2}{3e-2}+\epsilon }$, where $e$ is Euler's constant. We further extend this result to all vanishing $p$ such that $p\gg n^{-1/2}{\ln }^{3/2}n$, and furthermore, we show that, for $p$ such that $n^{-1}\ll p\ll n^{-1/2},T(G_{n,p})$ cannot be concentrated at the standard expectation threshold.

18 pages