We show that for $dge d_0(epsilon)$, with high probability, the random graph $G(n,d/n)$ contains an induced path of length $(3/2-epsilon)frac{n}{d}log d$. This improves a result obtained independently by Luczak and Suen in the early 90s, and answers a question of Fernandez de la Vega. Along the way, we generalize a recent result of Cooley, Draganic, Kang and Sudakov who studied the analogous problem for induced matchings.
تحميل البحث