Concentration of the maximum size of an induced subtree in moderately sparse random graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |