Pith. sign in

Note on induced paths in sparse random graphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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\'c, Kang and Sudakov who studied the analogous problem for induced matchings.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2025 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

citing papers explorer

Showing 1 of 1 citing paper.