Note on induced paths in sparse random graphs

2021/02/18 by Glock, Stefan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2102.09289

Abstract

We show that for d≥ d₀(ε), with high probability, the random graph G(n,d/n) contains an induced path of length (3/2-ε)(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.

Related

• Short proofs for long induced paths
• Packing and finding paths in sparse random graphs
• Long induced paths in a configuration model
• Large induced matchings in random graphs
• A quasi-optimal upper bound for induced paths in sparse graphs