Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.02801 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911035768700928 |
|---|---|
| author | Oropeza, Juan Carlos Buitrago |
| author_facet | Oropeza, Juan Carlos Buitrago |
| contents | Kamaldinov, Skorkin, and Zhukovskii proved that the maximum size of an induced subtree in the binomial random graph $G(n,p)$ is concentrated at two consecutive points, whenever $p\in(0,1)$ is a constant. Using improved bounds on the second moment of the number of induced subtrees, we show that the same result holds when $n^{-\frac{e-2}{3e-2}+\varepsilon}\leq p=o(1)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02801 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Concentration of the maximum size of an induced subtree in moderately sparse random graphs Oropeza, Juan Carlos Buitrago Combinatorics Kamaldinov, Skorkin, and Zhukovskii proved that the maximum size of an induced subtree in the binomial random graph $G(n,p)$ is concentrated at two consecutive points, whenever $p\in(0,1)$ is a constant. Using improved bounds on the second moment of the number of induced subtrees, we show that the same result holds when $n^{-\frac{e-2}{3e-2}+\varepsilon}\leq p=o(1)$. |
| title | Concentration of the maximum size of an induced subtree in moderately sparse random graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.02801 |