Ramsey numbers of trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908528040476672 |
|---|---|
| author | Montgomery, Richard Pavez-Signé, Matías Yan, Jun |
| author_facet | Montgomery, Richard Pavez-Signé, Matías Yan, Jun |
| contents | We show that there exists a constant $c>0$ such that every $n$-vertex tree $T$ with $Δ(T)\le cn$ has Ramsey number $R(T)=\max\{t_1+2t_2,2t_1\}-1$, where $t_1\ge t_2$ are the sizes of the bipartition classes of $T$. This improves an asymptotic result of Haxell, Łuczak, and Tingley from 2002, and shows that, though Burr's 1974 conjecture on the Ramsey numbers of trees has long been known to be false for certain `double stars', it is true for trees with up to small linear maximum degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07934 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Ramsey numbers of trees Montgomery, Richard Pavez-Signé, Matías Yan, Jun Combinatorics 05D10, 05C05 We show that there exists a constant $c>0$ such that every $n$-vertex tree $T$ with $Δ(T)\le cn$ has Ramsey number $R(T)=\max\{t_1+2t_2,2t_1\}-1$, where $t_1\ge t_2$ are the sizes of the bipartition classes of $T$. This improves an asymptotic result of Haxell, Łuczak, and Tingley from 2002, and shows that, though Burr's 1974 conjecture on the Ramsey numbers of trees has long been known to be false for certain `double stars', it is true for trees with up to small linear maximum degree. |
| title | Ramsey numbers of trees |
| topic | Combinatorics 05D10, 05C05 |
| url | https://arxiv.org/abs/2509.07934 |