Ramsey numbers of bounded degree trees versus general graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915496182415360 |
|---|---|
| author | Montgomery, Richard Pavez-Signé, Matías Yan, Jun |
| author_facet | Montgomery, Richard Pavez-Signé, Matías Yan, Jun |
| contents | For every $k\ge 2$ and $Δ$, we prove that there exists a constant $C_{Δ,k}$ such that the following holds. For every graph $H$ with $χ(H)=k$ and every tree with at least $C_{Δ,k}|H|$ vertices and maximum degree at most $Δ$, the Ramsey number $R(T,H)$ is $(k-1)(|T|-1)+σ(H)$, where $σ(H)$ is the size of a smallest colour class across all proper $k$-colourings of $H$. This is tight up to the value of $C_{Δ,k}$, and confirms a conjecture of Balla, Pokrovskiy, and Sudakov. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_20461 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Ramsey numbers of bounded degree trees versus general graphs Montgomery, Richard Pavez-Signé, Matías Yan, Jun Combinatorics For every $k\ge 2$ and $Δ$, we prove that there exists a constant $C_{Δ,k}$ such that the following holds. For every graph $H$ with $χ(H)=k$ and every tree with at least $C_{Δ,k}|H|$ vertices and maximum degree at most $Δ$, the Ramsey number $R(T,H)$ is $(k-1)(|T|-1)+σ(H)$, where $σ(H)$ is the size of a smallest colour class across all proper $k$-colourings of $H$. This is tight up to the value of $C_{Δ,k}$, and confirms a conjecture of Balla, Pokrovskiy, and Sudakov. |
| title | Ramsey numbers of bounded degree trees versus general graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.20461 |