Large induced trees in dense random graphs

Abstract

Erdő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\le p\le 0.99$. This is asymptotically optimal.

12 pages

Cited by in corpus (1)

• Note on induced paths in sparse random graphs