Maximum induced trees and forests of bounded degree in random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929476660625408 |
|---|---|
| author | Akhmejanova, Margarita Kozhevnikov, Vladislav Zhukovskii, Maksim |
| author_facet | Akhmejanova, Margarita Kozhevnikov, Vladislav Zhukovskii, Maksim |
| contents | Asymptotic behaviour of maximum sizes of induced trees and forests has been studied extensively in last decades, though the overall picture is far from being complete. In this paper, we close several significant gaps: 1) We prove $2$-point concentration of the maximum sizes of an induced forest and an induced tree with maximum degree at most $Δ$ in dense binomial random graphs $G(n,p)$ with constant probability $p$. 2) We show concentration in an explicit interval of size $o(1/p)$ for the maximum size of an induced forest with maximum degree at most $Δ$ for $1/n\ll p=o(1)$. Our proofs rely on both the second moment approach, with the probabilistic part involving Talagrand's concentration inequality and the analytical part involving saddle-point analysis, and new results on enumeration of labelled trees and forests that might be of their own interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15215 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximum induced trees and forests of bounded degree in random graphs Akhmejanova, Margarita Kozhevnikov, Vladislav Zhukovskii, Maksim Combinatorics Asymptotic behaviour of maximum sizes of induced trees and forests has been studied extensively in last decades, though the overall picture is far from being complete. In this paper, we close several significant gaps: 1) We prove $2$-point concentration of the maximum sizes of an induced forest and an induced tree with maximum degree at most $Δ$ in dense binomial random graphs $G(n,p)$ with constant probability $p$. 2) We show concentration in an explicit interval of size $o(1/p)$ for the maximum size of an induced forest with maximum degree at most $Δ$ for $1/n\ll p=o(1)$. Our proofs rely on both the second moment approach, with the probabilistic part involving Talagrand's concentration inequality and the analytical part involving saddle-point analysis, and new results on enumeration of labelled trees and forests that might be of their own interest. |
| title | Maximum induced trees and forests of bounded degree in random graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.15215 |