Spanning trees with large maximum degrees
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909858686566400 |
|---|---|
| author | Yan, Jun |
| author_facet | Yan, Jun |
| contents | The celebrated result of Komlós, Sárközy, and Szemerédi states that for any $\varepsilon>0$, there exists $0<c<1$, such that for all sufficiently large $n$, every $n$-vertex graph $G$ with $δ(G)\geq(1/2+\varepsilon)n$ contains every $n$-vertex tree with maximum degree at most $cn/\log n$. This is best possible up to the value of $c$. In this paper, we extend this result to trees with higher maximum degrees, and prove that for $Δ\gg n/\log n$, roughly speaking, $δ(G)\geq n-n^{1-(1+o(1))Δ/n}$ is the asymptotically optimal minimum degree condition which guarantees that $G$ contains every $n$-vertex spanning tree with maximum degree at most $Δ$. We also prove the corresponding statements in the random graph setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17736 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spanning trees with large maximum degrees Yan, Jun Combinatorics 05C35, 05C05 The celebrated result of Komlós, Sárközy, and Szemerédi states that for any $\varepsilon>0$, there exists $0<c<1$, such that for all sufficiently large $n$, every $n$-vertex graph $G$ with $δ(G)\geq(1/2+\varepsilon)n$ contains every $n$-vertex tree with maximum degree at most $cn/\log n$. This is best possible up to the value of $c$. In this paper, we extend this result to trees with higher maximum degrees, and prove that for $Δ\gg n/\log n$, roughly speaking, $δ(G)\geq n-n^{1-(1+o(1))Δ/n}$ is the asymptotically optimal minimum degree condition which guarantees that $G$ contains every $n$-vertex spanning tree with maximum degree at most $Δ$. We also prove the corresponding statements in the random graph setting. |
| title | Spanning trees with large maximum degrees |
| topic | Combinatorics 05C35, 05C05 |
| url | https://arxiv.org/abs/2510.17736 |