Large induced trees in dense random graphs

Abstract: ErdH{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 l o g_{q} (n p)

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)) l o g_{q} (n p)

,

G_{n, p}

contains an induced copy of

T

with high probability for

n^{- 1 / 2} l n^{10 / 9} n l e q p l e q 0.99

. This is asymptotically optimal.

This page was built for publication: Large induced trees in dense random graphs