On the order of the largest induced tree in a random graph (Q1088688): Difference between revisions

Let \(T_ n(p)\) be the order of the largest induced tree in a random graph on n vertices with edge-probability p. If \(p=cn^{-1}\log n\) where \(c\geq e\), then \[ (c^{-1}-\epsilon)n\frac{\log \log n}{\log n}<T_ n(p)<(2c^{-1}+\epsilon)n\frac{\log \log n}{\log n} \] almost surely, for all \(\epsilon >0\).