For p = n^{-(e-2)/(3e-2)+ε}, the maximum induced tree size in G(n,p) is concentrated at two adjacent values.
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 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Concentration of the maximum size of an induced subtree in moderately sparse random graphs
For p = n^{-(e-2)/(3e-2)+ε}, the maximum induced tree size in G(n,p) is concentrated at two adjacent values.