Note on induced paths in sparse random graphs

Abstract

We show that for $d\ge 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, Draganić, Kang and Sudakov who studied the analogous problem for induced matchings.

12 pages

References in corpus (1)

• Large induced trees in dense random graphs

Cited by in corpus (1)

• Paths, cycles and sprinkling in random hypergraphs