Erd\H{ o}s and Palka initiated the study of the maximal size of induced trees in random graphs in 1983. They proved that for every fixed $0<p<1$ the size of a largest induced tree in $G_{ n,p}$ is concentrated around $2\log_q (np)$ with high probability, where $q=(1-p)^{ -1}$. De la Vega showed concentration around the same value for $p=C/n$ where $C$ is a large constant, and his proof also works for all larger $p$. We show that for any given tree $T$ with bounded maximum degree and of size $(2-o(1))\log_q(np)$, $G_{ n,p}$ contains an induced copy of $T$ with high probability for $n^{ -1/2}\ln^{ 10/9}n\leq p\leq 0.99$. This is asymptotically optimal.
Categories: math.CO